Software/Algorithm

최근접 점의 쌍 찾기 (Closest Pair of Points Problem) 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 간단한 idea 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는다 example 1, 2, 3, 4, 5 총 5개의 점이 주어진 경우 비교해야 할 쌍의 개수 = nC2 = n(n-1)/2 시간 복잡도는 O(n^2) O(n^2)보다 효율적인 분할 정복 이용 n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 찾는다 2개의 부분해를 취합할 때 아래와 같이 양쪽을 비교해서 짧은 해라고 답으로 정할 수 없다. 거리가 짧은 해 이내..

선택 문제 (Selection Problem) n 개의 숫자들 중 k 번째로 작은 숫자를 찾는 문제 간단한 idea 최소 숫자를 k번 찾는다 O(kn) 숫자들을 정렬한 후 k번째 숫자를 찾는다 O(nlogn) Idea 이진 탐색 (Binary Search) 정렬된 입력인 경우, 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 반으로 나눈 두 부분 중 한 부분만을 검색 선택 문제 입력이 정렬되지 않는 형태, 입력 숫자 중 피봇을 선택하여 분할 Pseudo code Selection(A, left, right, k) Input: A[left] ~ A[right]와 k, 단 1 ≤ k ≤ |A|, |A| = right - left + 1 Output: A[left] ~ A[right]에서 k 번째..

Quick Sort 문제를 2개의 부분 문제로 분할 각 부분 문제의 크기가 일정하지 않음 Idea 피봇 (pivot)을 임의로 설정하여 피봇보다 작은 숫자는 피봇 기준 왼쪽편으로, 피봇보다 큰 숫자는 피봇 기준 오른쪽으로 위치하도록 분할하고 피봇을 그 사이에 놓는다. 분할된 부분 문제들에서도 재귀적으로 수행 문제가 2개로 분할되고, 부분 문제의 크기가 1/2로 감소하는 알고리즘 Pseudo code QuickSort(A, left, right) Input: Array A[left] ~ A[right] Output: Sorted Array A[left] ~ A[right] if (left < right) { p := partition(A, left, right) QuickSort(A, left, p) //..

합병정렬 (Merge Sort) 문제가 2개로 분할되고, 부분 문제의 크기가 1/2로 감소하는 알고리즘 합병 (Merge) 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자로 합치는 것 Example Array A: 6, 14, 18, 20, 29 Array B: 1, 2, 15, 25, 30, 45 Array C: 1, 2, 6, 14, 15, 18, 20, 25, 29, 30, 45 Pseudo code MergeSort(A, start, end) Input: A[start] ~ A[end] Output: Sorted A[start] ~ A[end] if (start < end) { // 배열의 원소의 수가 2개 이상이면 k = (start + end) / 2 // k는 반으로 나누기 위한 중간 원소의..