성장하고 개발하는 계란의 이야기

트라이(Trie)개념 문자열을 탐색 및 저장을 효율적으로 할 수 있는 트리 기반의 자료 구조 단어 검색, 자동 완성, 사전 구현 등의 작업에 유리하다. 문자열 저장 방식 각 노드는 공통된 접두사를 공유중볻된 부분을 제거하여 공간을 절약 시간 복잡도트리 생성: O(n * L), n은 문자열의 개수, L은 문자열의 길이   문자열 탐색: O(L), L은 문자열의 길이  공간 복잡도: 각 문자마다 노드를 생성하므로 공간을 많이 차지하지만 접두사를 공유하는 문자가 많을 수록 단어를 효율적으로 저장 가능풀이 방식 삽입루트 노드에서 시작하여 문자열의 첫 번째 문자부터 시작문자별로 노드를 추가하며, 해당 문자가 이미 존재하는 경우 기존 노드를 재사용문자열의 끝에 도달하면, 해당 노드에 단어의 끝임을 표시삭제 문자열의..

문제 풀이고려해야할 점더보기타일은 위와 아래로 존재하고 있다. 이 문제는 위와 아래 타일에 각각의 경우에 따른 계산이 필요하다.  n의 최대 개수는 100,000 이므로 모든 경우의 수를 완전 탐색할 경우 시간 초과 문제가 발생한다.  풀이 아이디어 더보기다이나믹 프로그래밍타일의 개수에 따른 점화식을 세워 계산한다. 이때 점화식은 위 타일 아래 타일 분리하여 계산하여야 한다.  점화식 계산 DP 배열은 2차원으로 생성. int[][] dp = new int[n+1][2]; 형식으로 선언하였다. 이때 배열의 첫 번째 인덱스는 몇 번째 타일인지를 나타내고 두 번째 인덱스는 위 타일인지 아래타일인지를 나타낸다. 이 코드에서는 위의 인덱스를 0으로 아래를 1로 표시한다. 아래 타일 점화식아래 타일(dp[n][1..

문제  풀이고려해야할 점더보기 순서 관계 변경:주어진 순서에 대해 여러 쌍의 순서 관계를 변경해야 하므로, 현재 상태의 순서와 이후에 주어지는 관계 변경이 어떻게 영향을 미치는지 추적해야 한다. currentPosition 배열에서 순서를 변경할 때, 중복된 위치나 범위 밖의 위치가 발생하지 않도록 해야 한다. 유효성 검사:변경된 순서가 유효한지 검증하는 과정에서 resultMap에 중복된 위치가 없도록 해야 한다.위치가 배열 범위를 벗어나는지, 중복된 노드가 있는지 체크하여 잘못된 순서인 경우 “IMPOSSIBLE”을 출력한다. "?"인 경우는 존재하지 않는다. 올바른 순위를 결정할 수 없으면 모두 "IMPOSSIBLE"이다. 최적화 고려:많은 쌍의 관계 변경이 있을 수 있으므로 효율적으로 현재 순서를..

문제  풀이 고려해야할 점더보기 선분의 겹침 처리: 여러 개의 선분이 주어졌을 때, 겹치는 부분을 제외하고 전체 선분의 총 길이를 구해야 합니다.입력 순서: 선분들이 입력되는 순서가 정렬되어 있지 않을 수 있으므로, 시작점 기준으로 선분들을 정렬할 필요가 있습니다.데이터 타입: 좌표의 범위가 매우 크거나 작을 수 있으므로, 오버플로우를 방지하기 위해 적절한 데이터 타입(long)을 사용해야 합니다.  문제 풀이 아이디어 더보기 선분 정렬: 시작점 기준으로 선분들을 정렬하여 겹치는 부분을 효율적으로 처리할 수 있도록 합니다.현재 선분의 범위 추적:변수 l과 r을 사용하여 현재까지의 유효한 선분의 시작점과 끝점을 추적합니다.초기값으로 l은 가장 작은 값(Integer.MIN_VALUE)으로 설정하고, r은 ..

LIS(Longest Increasing Subsequence )개념  주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 코드. DP 방식이나 이분 탐색을 이용하여 풀 수 있다.  예를 들어, 배열 [10, 20, 10, 30, 20, 50]가 주어졌을 때, 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]로 길이는 4가 된다. 문제 풀이 방식동적 프로그래밍(DP) 방식 - 시간 복잡도: O(n^2)이분 탐색을 이용한 최적화 방식 - 시간 복잡도: O(n log n) 풀이 방식(DP)배열을 순서대로 탐색하면서 dp 배열을 갱신해나가는 방식. 각 위치에서 해당 위치까지의 가장 긴 증가하는 부분 수열의 길이를 저장한다.점화식: dp[i]는 i번째 요소까지의 가장 긴 증가하는 부분 수열의..

문제  풀이고려해야할 점더보기친구의 친구의 친구도 친구로 칠 수 있다. 즉 어떤 친구 집단 트리 A가 있을 때 그 중 한 명만 친해도 그 집단 전체와 친구가 되었다고 할 수 있다. 이를 계산하기 위해 서로 연결되어 있는 친구 집단을 구해야 한다. 이 결과를 바탕으로 친구비를 최소로 하는 경우의 수를 찾아야 한다. 중복되는 친구 관계, 혹은 자기 자신과 친구인 경우를 확인해야 한다. 모두 친구를 만들 수 없는 경우 "oh no"를 출력해야 한다.  알고리즘 분류(백준 기준) 더보기자료구조그래프 이론 그래프 탐색분리 집합유니온 파인드  풀이 아이디어 더보기집합 관계를 효율적으로 판별하기 위해 유니온 파인드를 사용하였다. 두 집합을 합칠 때는 친구비의 값이 더 싼 쪽이 부모가 되도록 결합하였다. 각 집합의 최..

풀이 고려해야할 점더보기여러 개의 테스트 케이스가 존재하며 각 테스트 케이스는 최대 100000개의 도미노가 주어진다. 시간 복잡도를 고려하면 O(n)이나 O(nlogn) 사이로 구현해야 한다.도미노는 순서대로 넘어지므로 이 순서를 바탕으로 처음 넘어뜨려야 하는 도미노를 찾아야 한다. 보통 도미노의 시작 지점을 찾아서 넘어뜨릴 것이나, 도미노가 루프 형태를 가질 경우 시작 지점이 존재하지 않을 수도 있다. (예외 케이스)예외 1: 루프 형태 예외 2: 올가미 형태   문제 풀이 아이디어 더보기먼저 모든 도미노의 연결 관계를 저장한다. (자신을 넘어뜨릴 수 있는 도미노는 부모, 자신이 넘어뜨리는 도미노는 자식으로 설정하여 연관관계를 저장)부모가 없는 도미노의 경우 사람이 직접 넘어뜨려야 하므로 해당 도미노..

문제 풀이 고려해야할 점더보기입력 데이터의 수는 100000개 이하로 최악의 경우를 생각하면 O(nlogn)의 시간 복잡도로 문제를 해결해야 한다. 길이만 출력하는 것이 아닌 제거해야 하는 전깃줄의 번호도 출력해야 하기 때문에 각 경우에 제거되는 혹은 남는 전깃줄의 번호를 저장하고 추적해야 한다. 출력하는 것은 A 기둥의 번호이다. 실수로 B기둥의 번호나 임의로 부여한 인덱스를 출력하지 않도록 주의해야 한다.  문제  해결 아이디어더보기겹치지 않는 경우를 찾으려면 왼쪽과 오른쪽 인덱스가 서로 교차하지 않도록 전깃줄을 선택하면 된다. 즉 왼쪽과 오른쪽 모두 증가하는 전깃줄의 경우의 수 중 가장 많은 수의 전깃줄이 배치된 것을 찾으면 된자. (LIS 문제)가장 긴 증가하는 부분수열은 DP와 이분 탐색으로 풀..