기수 정렬 (Radix Sort) 비교 정렬이 아닌 정렬 방식 숫자를 비교적으로 정렬 제한적인 범위 내에 있는 숫자에 대해 자리수 별로 정렬 어느 비교 정렬 알고리즘보다 빠름 기 (Radix) 특정 진수를 나타내는 숫자 예시 10진수 → 0, 1, 2, 3, …, 9 2진수 → 0, 1 정렬 알고리즘의 안정성(Stability) 입력에 중복된 숫자가 있을 때, 정렬된 후에도 중복된 숫자의 순서가 입력에서의 순서와 동일한 경우 Pseudo code RadixSort Input: n개의 r진수의 k자리 숫자 Output: 정렬된 숫자 1. for i = 1 to k 2. 각 숫자의 i자리 숫자에 대해 안정한 정렬을 수행한다 3. return 배열 A stableSort(A, n, e) for i = 0 to..
Software/Algorithm
힙 정렬 (Heap Sort) 힙 자료 구조를 이용하는 정렬 알고리즘 오름차순의 정렬을 위해 최대힙(maximum heap)을 구성 힙의 루트에는 가장 큰수가 저장됨 Pseudo code HeapSort Input: 입력이 A[1] .. A[n]까지 저장된 배열 A Output: 정렬된 배열 A 1. 배열 A의 숫자에 대해서 힙 자료 구조를 만든다. 2. heapSize = n // 힙의 크기를 조절하는 변수 3. for i = 1 to n - 1 4. A[1] ↔ A[heapSize] // 루트와 힙의 마지막 노드 교환 5. heapSize = heapSize - 1 // 힙의 크기를 1 감소 6. DownHeap() 7. return 배열 A Example Code private class HeapS..
쉘 정렬 (Shell sort) 삽입 정렬의 경우 맨 마지막 원소가 가장 작은 원소면 모든 숫자를 옮겨야함 이러한 단점을 보완 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게 이동 동시에 앞부분의 큰 숫자는 뒷부분으로 이동 마지막에는 삽입 정렬 각 간격 별로 그룹을 설정하여 정렬 마지막에는 무조건 간격을 1로 설정하고 정렬 Pseudo code ShellSort Input: 크기가 n인 배열 A Output: 정렬된 배열 A 1. for gap h = [h0 > h1 >... > hk = 1] // 큰 gap부터 차례로 2. for i = h to n - 1 { 3. CurrentElement = A[i] 4. j = i 5. while (j >= h) and (A[j - h] > CurrentElement..
삽입 정렬 (Insertion Sort) 배열을 정렬된 부분 (앞부분)과 정렬 안 된 부분 (뒷부분)으로 나눔 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복 Pseudo code InsertionSort Input: 크기가 n인 배열 A Output: 정렬된 배열 A 1. for i = 1 to n - 1 { 2. CurrentElement = A[i] // 정렬 안된 부분의 가장 왼쪽원소 3. j = i – 1 // 정렬된 부분의 가장 오른쪽 원소로부터 왼쪽 방향으로 삽입할 곳을 탐색하기 위하여 4. while (j >= 0) and (A[j] > CurrentElement) { 5. A[j + 1] = A[j] // 자리 이동 6. j = j ..
선택 정렬 (Selection Sort) Input 배열의 원소 중 최솟값을 선택하여 0번 자리로, 0번 원소를 제외한 나머지 중 최솟값을 선택하여 배열의 1번 자리로 이동시키며 정렬 Pseudo code SelectionSort Input: 크기가 n인 배열 A Output: 정렬된 배열 A 1. for i = 0 to n - 2 { 2. min = i 3. for j = i + 1 to n - 1 { // A[i]~A[n-1]에서 최솟값을 찾기 4. if (A[j] < A[min]) 5. min = j 6. } 7. swap(A[i], A[min]) // min이 최솟값이 있는 원소의 인덱스 8. } 9. return 배열 A Example code private class SelectionSortE..
버블 정렬 (Bubble Sort) 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하여 정렬 Pseudo code BubbleSort Input: 크기 n 배열 A Output: 정렬된 배열 A 1. for pass = 1 to n - 1 2. for i = 1 to n - pass 3. if (A[i - 1] > A[i]) // 위의 원소가 아래의 원소보다 크면 4. swap(A[i - 1], A[i]) // 서로 자리를 스왑 5. return 배열 A Example code private class BubbleSortExample { fun solution(a: IntArray) { val sortedA = bubbleSort(a) println(sortedA.toList()) }..
동전 거스름돈 문제 (Coin Change Problem) 정해진 동전 d1, d2, …, dk, 거스름돈 n원 단, d1 > d2 > … > dk = 1 부분 문제 w원을 거슬러 줄 때 i번째 동전을 1개 추가할 때 동전 개수 w-di 원을 거슬러 줄 때 필요한 최소 동전의 개수 + 1개 1원씩 증가시켜서 문제 해결 C[j] = min1≤i≤k { C[j - di] + 1 }, if j ≥ di Pseudo code DPCoinChange Input 거스름돈 n원 k개의 동전 액면 d1 > d2 > … > k = 1 Output: C[n] 1. for i = 1 to n C[i] = ∞ 2. C[0] = 0 3. for j = 1 to n { // j는 1원부터 증가하는 (임시) 거스름돈 액수이고, j..
배낭 문제 (Knapsack Problem) 물건 n개 각 물건 i, 무게 wi, 가치 vi 배낭 용량 C 위 조건에서 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제 단, 배낭에 담을 물건의 무게 합이 C를 초과하지 않고 각 물건은 1개씩만 존재 이러한 문제를 0-1 배낭이라고 명칭 부분 문제 K[i, w] 물건의 1 ~ i 까지만 고려하고, 배낭의 용량이 w일 때의 최대 가치 최적해 - K[n, C] C의 값이 매우 크면 알고리즘 수행시간이 매우 길어짐 Pseudo code Knapsack Input 배낭의 용량 C n개의 물건 각 물건 i의 무게 w 와 가치 v Output - K[n, C] 1. for i = 0 to n K[i, 0] = 0 // 배낭의 용량이 0일 때 2. for w = 0..
편집 거리 문제 (Edit Distance Problem) 문자열 S를 수정하여 문자열 T로 변환하려고 할 때 쓰이는 연산 삽입 - insert 삭제 - delete 대체 - substitude 편집 거리 - S를 T로 변환시키는데 필요한 최소 편집 횟수 편집 거리 예시 S - strong T - stone stong - r 삭제 stone - g → e 대체 총 2회 Idea 각 문자열의 접두부의 편집거리를 미리 알고있으면 부분 문제를 통해 현재를 알 수 있음 stro → sto, ng → ne를 알고 있으면 strong → stone을 알 수 있음 Pseudo code EditDistance Input S: String, T: String 단, S와 T의 길이는 m 과 n Output S를 T로 변환..
연속 행렬 곱셈 (Chained Matrix Multiplications) 문제 연속된 행렬들의 곱셈에 필요한 원소간의 최소 곱셈 횟수를 찾는 문제 문제 예시 행렬 A가 10x20, 행렬 B가 20x5, 행렬 C가 5x15 (A x B) x C의 경우 A x B 계산 → 10 x 20 x 5 = 1,000번 AB x C 계산 → 10 x 5 x 15 = 750번 총 1,750번 A x (B x C)의 경우 B x C 계산 → 20 x 5 x 15 = 1,500번 A x BC 계산 → 10 x 20 x 15 = 3,000번 총 4,500번 Idea 동일한 결과값 이지만 곱셈 연산 횟수는 2,800번의 차이가 생김 곱셈 횟수를 최소화 시키기 위한 곱셈 순서를 찾아야함 주어진 행렬의 순서를 지켜서 이웃하는 행..
