Remember Your Place

1. 문제 링크https://www.acmicpc.net/problem/92022. 문제 풀이 생각보다 플래티넘 V 정도의 문제들은 정석적인 풀이가 아닌 다른 방식으로도 풀리는 경우가 있는 것 같습니다. 이번 문제도 [BOJ] 14942 개미 문제와 같이 DFS로 풀렸습니다. 입력으로 단어들이 300,000 미만 정도의 개수로 주어지는데, 솔직히 시간제한과 메모리 제한이 각각 10초와 512 MB로 매우 널널합니다. 저는 트라이(Trie)와 DFS를 사용한 풀이보다는 Set을 활용한 DFS를 채택하였습니다. HashSet에 모든 단어를 저장한 후, DFS를 통해 단어의 존재 여부를 확인하며 문제를 해결했습니다. 이렇게 구현한 이유는 HashSet의 탐색 속도가 평균적으로 O(1)에 가깝고, 단어 길이가 ..

1. 문제 링크https://www.acmicpc.net/problem/149422. 문제 풀이 이 문제에서는 방의 개수 최댓값이 100,000으로 주어집니다. 보통 input 값으로 10만 이상의 단위가 나오게 된다면 단순 구현으로는 못 푸는 경우가 많죠. 그래서 원래라면 희소 배열(Sparse Table)이라는 개념을 적용해서 풀어야 하는 문제이긴 합니다만. 이 문제는 단순 DFS로 풀립니다! 물론 아직 푼 사람이 그렇게 많은 편이 아닌 데다가 추가 테스트 케이스가 있어야 플래티넘다운 문제라고 할 수 있겠는데 ..   static void dfs(int node, int parentNode) { parent[node] = parentNode; for (Edge edge : g..

제 블로그는 대체로 즉흥적으로 글 쓰는 용도라 이전 포스트에 이어서 시리즈가 연재가 되지 않는다 싶으면 다른 관심사가 생긴 것입니다. 그래도 이렇게 지나가면서 이어나가니까 기다려주시면 감사하겠습니다. 꼼꼼하게 준비하려다 보니 늦어질 때도 있어요. 2024.09.14 - [Study/Java] - [Java] HashSet과 HashMap 성능 차이 [Java] HashSet과 HashMap 성능 차이몇 달 전에 알고리즘 문제를 풀었는데 이상하게 시간이 오래 걸렸습니다. 분명 로직은 맞는데 HashMap을 쓴 코드와 HashSet을 쓴 코드의 성능 차이가 많이 났습니다. 왜 Why? 지금부터 여기에 대해서claris.tistory.com 예전 게시글에서 HashSet과 HashMap의 성능 차이에 대해서 ..

Java에서 직렬화(Serialization)와 역직렬화(Deserialization)는 객체 데이터를 효율적으로 저장하거나 네트워크를 통해 전송하기 위한 중요한 메커니즘입니다. 직렬화와 역직렬화를 왜 사용해야 하는지, 그 동작 원리와 실질적인 활용 사례를 다루겠습니다. 그리고 직렬화 과정에서 사용하는 transient 키워드와 serialVersionUID의 역할 및 설정 방법까지 알아보겠습니다. Serialization?직렬화(Serialization)란 Java 객체를 바이트 스트림으로 변환하는 과정입니다. 이 과정을 통해 객체를 파일에 저장하거나 네트워크로 전송할 수 있습니다. 다시 말해, 객체의 상태를 영구적으로 저장하거나 전송 가능한 형식으로 변환하는 것입니다. 직렬화의 목적1. 데이터 영속성..

최근 Java로 문자열을 처리하던 도중에 골머리를 앓았습니다. 대체 왜 자바에서는 charAt과 substring 메서드에 long 타입 인덱스를 사용할 수 없는가? 물론 문자열을 여기까지 끌고 온 코드 설계의 문제 이긴 하지만요.  charAt 그리고 substring의 구조일단 charAt 메서드의 구조는 이런 식으로 짜여있습니다. 매개변수 자체가 int형이죠. 범위 역시 0부터 Integer.MAX_VALUE 값입니다. substring 메서드 역시 인덱스의 타입을 int 타입으로 받고 있습니다. 아니 그냥 int 타입을 long으로 바꿔서 메서드를 구현하면 안 되냐고 생각할 수도 있겠습니다만. 자바는 굳이 배열이나 문자열과 같은 데이터 구조에서 인덱스를 int 타입으로 제한합니다. 왜why? 자..

That easy 늘 그렇듯이 새로운 프로젝트 설정을 맞춰주는 건 번거로운 일입니다. 서론은 이만 줄이고 바로 본론으로 들어가겠습니다. JDK를 아직 안 받았다? IntelliJ를 통해 JDK를 손쉽게 설치할 수 있습니다. File -> Project Structure  Platform Settings -> SDKs -> (+ 버튼) -> Download JDK를 통해 원하는 버전의 JDK를 다운로드합니다.  그 후, 같은 창에서 Project Settings -> Project를 통해 다운로드한 SDK로 설정합니다.  IntelliJ IDEA -> Settings...  Build, Execution, Deployment -> Build Tools -> Gradle -> Gradle JVM에서 해당 ..

1. 문제 링크https://www.acmicpc.net/problem/232892. 문제 풀이 이제 곧 기다리던 삼성 코딩 테스트죠? 구현만큼은 자신 있었던 (과거형) 저도 이번만큼은 긴장되네요. 그야 자소서 문항이 바뀌고 난 후 첫 시험이라 .. 코딩테스트도 변동이 있을 가능성도 없진 않을 테니까요. 그래서 예전 같았으면 그냥 배열 돌리기랑 bfs만 돌리고 갔을 텐데 이번엔 다릅니다. 몇 달 전에 큐빙을 풀긴 했지만 좀 제대로 된 플래티넘 구현 문제를 풀고 싶었습니다.  가장 중요한 건 설계. 코드를 구현하기 전에 꼼꼼하게 조건을 숙지한 후 구현을 해야 합니다. 그래도 나름 짧은 코드로 만들어보고 싶었으나 코드가 좀 길게 나왔습니다. 1. 모든 온풍기에서 바람 나옴2. 온도 조절3. 온도 1 이상인 ..

몇 달 전에 알고리즘 문제를 풀었는데 이상하게 시간이 오래 걸렸습니다. 분명 로직은 맞는데 HashMap을 쓴 코드와 HashSet을 쓴 코드의 성능 차이가 많이 났습니다. 왜 Why? 지금부터 여기에 대해서 파보려고 합니다. 1. HashMap과 HashSet의 차이점?HashMap: 키-값(key-value) 쌍을 저장하는 자료구조입니다. 키는 고유하며 값은 중복될 수 있습니다. 주로 put(key, value), get(key), remove(key) 같은 작업이 이루어집니다. HashSet: 중복되지 않는 고유한 요소들의 집합을 저장하는 자료구조입니다. 내부적으로 HashMap을 사용하여, 각 원소를 HashMap의 키로 저장하고, 값은 고정된 더미 객체(PRESENT)를 사용합니다. 잠시만요. ..

String? Java의 String 클래스, 많이 사용하는 클래스 중 하나죠? 이번 글에서는 String을 String Pool과 함께 살펴보려고 합니다.String 객체 생성법 String 클래스는 문자열을 표현하는 데 사용됩니다. String 객체는 불변(immutable)이며, 한번 생성된 문자열은 변경할 수 없습니다. String 객체의 생성은 두 가지 방식, 문자열 리터럴(literal) 방식과 new 키워드 방식으로 나뉩니다.String str1 = "Hello, World!";String str2 = new String("Hello, World!");뭐가 더 효율적일까요? 문자열 리터럴 방식이 더 효율적이고 일반적으로 사용됩니다. 무슨 이유에서 일까요? 첫번째 방법이 더 효율적인 이유는 S..

Java Stream API? 저번 시간에는 Java 8에서 도입된 람다식에 대해서 알아보았습니다.2024.08.25 - [Study/Java] - [Java] Lambda 훑어보기 [Java] Lambda 훑어보기Lambda Expressions? 람다 표현식은 Java 8에서 도입되었습니다. 함수형 프로그래밍 스타일을 Java에 도입하면서 코드를 간결, 명확하게 작성할 수 있도록 한 것이죠. 익명 함수(anonymous function)를 정의하claris.tistory.com 이번 시간에는 람다 표현식과 함께 도입된 Stream API에 대해서 훑어보겠습니다. 스트림(Stream)은 말 그대로 데이터의 연속된 흐름이라 볼 수 있습니다. 이 API는 컬렉션(List, Set 등), 배열과 같은 데이터..