YJ_Scribbles

★ 최근점 점의 쌍 찾기 - 차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 ☆ 간단한 방법 - 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾기 - 5개의 점이 아래의 [그림]처럼 주어지면, 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5 사이의 거리를 각각 계산하여 그 중에 최소 거리를 가진 쌍이 최근접 점의 쌍이 됨. ㅇ 비교해야 할 쌍은 몇 개인가? - nC₂ = n(n-1)/2 - n=5이면, 5(5-1)/2 = 10 - n(n-1)/2 = O(n²) - 한 쌍의 거리 계산 : O(1) - 시간복잡도 : O(n²)xO(1) = O(n²) ☆시간복잡도가 O(n²)보다 효율적인 방법..

★ 분할-정복 알고리즘 - 주어진 문제를 분할하여 해결(정복)하는 방식의 알고리즘 -> 문제 분할 -> 분할한 입력에 대해 동일한 알고리즘 적용 -> 해 계산 -> 계산된 해 취합 -> 문제의 해 구함 ☆ 부분문제와 부분해 • 부분문제 (subproblem) : 분할된 입력에 대한 문제 (부분문제는 더 이상 분할할 수 없을 때가지 계속 분할) • 부분해 : 부분문제의 해 ★ 퀵정렬 - Partition()으로 큰 문제를 2개의 작은 문제로 분할(절반으로 나누지 않을 수 있음) - 분할할 때 작은 부분, 큰 부분으로 분할함으로써 정복(해결)과정이 따로 필요없음 ★ 합병정렬 - 무조건 절반으로 분할 - 분할된 문제를 Merge()로 정복 ★ 분할정복의 효과 ex)O(n²) 알고리즘 - N = 100일 때, ..