mondegreen

분할정복의 개념 1) 분할: 해결할 문제를 여러 개의 작은 부분으로 나누기 2) 정복: 나눈 작은 문제를 각각 해결하기 => 이 때 나눈 작은 문제가 더 나눠질 수 있다면 다시 나눈다. 3) 통합: 해결한 해답을 모으기 분할정복의 응용 1) 병합 정렬(top-down 방식) - 안정 정렬 (1) 데이터 집합의 크기가 0 또는 1인지 확인 => true면 정렬 (2) 데이터 집합을 반으로 분할 (3) 나눈 집합을 하나의 집합으로 병합 (4) 최소 크기가 될 때까지 분할 (5) 조각난 데이터 집합을 정렬하며 병합(재귀 호출 이용) 시간 복잡도 공간 복잡도 O(nlogn) O(n) 2) 퀵정렬 - 불안정 정렬 (1) 데이터 집합의 크기가 0 또는 1인지 확인 => true면 정렬 (2) 데이터 집합을 반으로 ..