프로그래밍 잡동사니

정렬(Sorting) 알고리즘 내부(Internal) 정렬 입력의 크기가 주기억 장치의 공간보다 작은 경우 (빠름) 버블 정렬, 선택 정렬, 삽입 정렬 합병 정렬, 퀵 정렬, 힙 정렬, 쉘 정렬 기수 정렬 (입력이 제한된 크기 이내의 숫자로 구성될 때) 외부(External) 정렬: 입력의 크기가 주기억 장치의 공간보다 큰 경우 (느림) 보조 기억 장치에 있는 입력을 나누어 주기억 장치에 읽어 들인 후, 다시 보조 기억 장치에 저장 다방향(p-way) 합병, 다단계(Polyphase) 합병 1. 버블(Bubble) 정렬 이웃하는 숫자를 비교해 작은 수를 앞(위)쪽으로 이동시키는 과정을 반복해 정렬하는 알고리즘 * 작은 수가 앞으로 올라오는 과정이 마치 거품 같아 붙은 이름이다 이중 for문 n(n-1)/..

보호되어 있는 글입니다.

5. 집합 커버(Set Cover) 문제 집합 커버 문제: n개의 원소를 가진 집합 U가 있고, U의 부분집합들을 원소로 하는 집합 F가 주어질 때, F의 원소들인 집합들 중에서 어떻게 선택하여 합하면 선택하는 집합의 수를 최소화하면서 U와 같게 되는가? 신도시 학교 배치 문제 (응용): 10개의 마을이 있을 때, 등교 거리가 15분 이내가 되도록 학교들의 위치를 선정할 때, 어느 마을에 학교를 신설해야 학교의 수가 최소가 되는가? 그렇다면 집합 커버 문제의 최적해는 어떻게 찾아야 할까? n이 커질 때, 2n-1개를 다 검사하는 것이 비효율적이기 때문에 최적해가 아닌 근사해(approximation solution)를 찾는다 while 루프 수행 최대 n번 / Line 2 O(1) / Line 3 O(n..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

그리디(Greedy) 알고리즘 그리디(= 탐욕) 알고리즘: 가능한 해들 중에서 가장 좋은 해를 찾는 최적화(optimization) 문제를 해결하는 알고리즘, 앞뒤 데이터 간 관계를 고려하지 않고 수행 과정에서 최소 or 최대값을 가진 데이터만 근시안적으로 선택 * 한 번 데이터를 선택하면 번복하지 않아서, 알고리즘이 단순하고 제한적인 문제 해결에 적합 1. 동전 거스름돈 문제 남은 액수를 초과하지 않는 조건 하에 가장 큰 액면의 동전을 취하는 방법? (500, 100, 50, 10, 1) 2. 최소 신장 트리(Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클 없이 모든 점을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 (입력: 1개의 연결요소(connected compo..

보호되어 있는 글입니다.

선택(Selection) 문제 선택 문제: n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제 간단한 방법 최소 숫자를 찾고 제거하는 과정을 k번 반복하고 최소 숫자를 찾는다 ~ 최악의 경우 O(kn) 숫자들을 정렬하고 k번째 숫자를 찾는다 ~ 최악의 경우 O(nlogn) 선택 문제 알고리즘 * 각 그룹의 크기를 알면, k번째 작은 숫자가 어느 그룹에 있는지 알 수 있고, 그 그룹에서 몇 번째 작은 숫자를 찾아야 하는지 알 수 있다! Small group에 k번째 작은 숫자가 속한 경우: k번째 작은 숫자를 해당 그룹에서 찾는다 Large group에 k번째 작은 숫자가 속한 경우: (k – Small group의 숫자 개수 – 1) 번째로 작은 숫자를 해당 그룹에서 찾는다 선택 문제 알고리즘 과정 선..

보호되어 있는 글입니다.

분할 정복 알고리즘(Divide-and-Conquer) 분할 정복: 아우스터리츠 전투에서 유래된 용어로, 대상을 작게 분할해 각각 정복한다는 의미 분할 정복 알고리즘: 알고리즘 문제를 나눌 수 없을 때까지 쪼개고 각각 풂으로써 전체 답을 구하는 방식 분할된 입력에 대한 문제를 부분문제(subproblem), 부분문제의 해를 부분해라고 한다 부분 문제의 수와 크기에 따라 다음과 같은 분류가 있다 문제가 a개로 분할되고, 부분 문제의 크기가 1/b로 감소하는 알고리즘 a = b = 2인 경우: 합병 정렬, 최근접 점의 쌍 찾기 a = 3, b = 2인 경우: 큰 정수의 곱셈 a = 4, b = 2인 경우: 큰 정수의 곱셈 a = 7, b =2인 경우: 스트라센(Strassen)의 행렬 곱셈 문제가 2개로 분..