나의 경험이 나를 구성한다

문제 : [start, end] 형태의 여러 개의 interval이 주어졌을 때, 그 interval 들의 합집합을 계산하라. 아이디어 1. 주어진 순서대로 자신 이후의 interval들과 비교하여 (정확히는 자신의 end와 비교대상의 start, end가 더 크면 겹치는 부분 존재) 합집합을 계산. 예상 시간복잡도 : (n-1)+(n-2)+...+1 = n(n-1)/2, O(n^2) 아이디어 2. 주어진 interval들을 start에 대해 정렬한다. 이후 위 아이디어처럼 하나씩 비교하다가 겹치지 않는 interval (K)이 발견되는 K 이후 interval들의 start가 최소 K의 start보다 크므로 더 이상 비교할 필요 없어지고, K 이하의 interval 들은 건너뛰고 비교 기준을 바로 K로..

알고리즘 2024. 3. 7. 12:30