알고리즘
탐욕법
그리디 알고리즘은 최적화 문제를 해결하는 알고리즘이라고 할 수 있다.
최적화(optimization) 문제란 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제이다.
욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불린다.
그리디 알고리즘은 수행 과정에서 탐욕적으로 일단 한 번 선택하면, 이를 절대로 번복하지 않는다.
즉, 선택한 데이터를 버리고 다른 것을 취하지 않는다.
이러한 선택을 근시안적인 선택이라고 말하기도 한다. 이 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서 최종적으로 문제의 최적해를 얻는 것이다.
이러한 특성 때문에 대부분의 그리디 알고리즘들은 매우 단순하며, 또한 제한적인 문제들만이 그리디 알고리즘으로 해결된다.
대표적으로 알려진 그리디 알고리즘의 예로는
- 동전 거스름돈 문제
- 최소 스패닝 트리 (MST)
- 최단 경로 찾기
- 부분 배낭 문제
- 집합 커버 문제
- 작업 스케줄링 문제
등이 존재한다.
1. 동전 거스름돈 문제
주어진 동전 단위와 거스름돈을 가지고 최소 동전 수를 찾는 가장 간단하고 효율적인 방법이다.
간단한 문제이므로 간략히 설명하자면, 남아 있는 거스름돈에 대해 가장 높은 액면의 동전을 거스르며 최소 동전 수를 추가하는 방법이다.
큰 화폐를 처리할 수 있을 때, 작은 화폐에 대해서는 전혀 고려하지 않기 때문에 그리디 알고리즘이라고 할 수 있다.
이 동전 거스름돈 문제에서 주의 할 점은, 모든 화폐 단위에서 이 그리디 알고리즘을 적용할 수 없다는 것이다.
만약 200원을 거스르는 문제에서 160원짜리 동전이 존재한다면 어떻게 될까?
그리디 알고리즘에서는 100원보다 160원이 더 크니까, 160원을 거스르고 그 다음 남은 10원짜리 4개를 거스르면 총 5개가 된다.
하지만 100원 짜리 2개가 최적의 해이므로, 이와 같은 경우가 존재할 수 있기 떄문에 그리디한 방법이 항상 최적의 답을 주지는 못한다.
그래서 실제로 거스름돈에 대한 그리디 알고리즘이 적용되도록 화폐 단위가 발행된다고 한다.
위 같이 160원 동전같은 문제는 DP로 해결이 가능하다.
2. 최소 스패닝 트리 (MST)
최소 스패닝 트리는 주어진 가중치 그래프에서 사이클이 없이 모든 Vertex들을 연결시킨 트리들 중 Edge들의 가중치 합이 최소인 트리를 말한다.
주어진 그래프의 스패닝 트리를 찾는 방법은 사이클이 없도록 모든 Vertex들을 연결시키는 것이다.
그래프의 Vertex의 수가 V개가 있다면, 스패닝 트리에는 반드시 V-1개의 Edge가 존재한다.
위 이미지는 6개의 Vertex를 5개의 Edge로 연결시킨 스패닝 트리가 있고,
스패닝 트리에 Edge를 하나 더 추가시킨다면, 반드시 사이클이 만들어 진다는 것을 보여준다.
최소 스패닝 트리를 찾는 그리디 알고리즘으로는 2가지가 존재한다.
- 크루스칼의 최소 스패닝 트리 알고리즘
- 프림의 최소 스패닝 트리 알고리즘
위 최소 스패닝 트리 알고리즘들은 최소 비용으로 선로 또는 파이프 네트워크 (인터넷 광 케이블 선로, 케이블 TV선로, 전화선로, 송유관로, 가스관로, 배수로 등)를 설치하는데 활용된다.
3. 최단 경로 찾기
최단 경로 문제는 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제이다.
최단 경로 알고리즘를 찾는 그리디 알고리즘으로는 2가지가 존재한다.
- 다익스트라
- 벨만-포드
최단 경로를 찾는 알고리즘은 위 2가지 말고도 플로이드의 모든 쌍 최단 거리 알고리즘이 존재하지만,
위 알고리즘은 그리디 알고리즘이 아니라, DP 알고리즘 문제이다.
4. 부분 배낭 문제
부분 배낭 문제에 대해 알아보기 위해서는, 먼저 배낭(Knapsack) 문제를 알아야 한다.
배낭 문제란,
- N개의 물건이 있다.
- 각 물건은 무게와 가치를 가지고 있다.
- 배낭이 한정된 무게의 물건들을 담을 수 있다.
이 때, 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제이다.
이 배낭 문제는 2가지로 구분 할 수 있다.
- 부분 배낭 문제
- 0/1 배낭 문제
먼저 1. 부분 배낭(Fractional Knapsack)문제는 물건을 부분적으로 담는 것을 허용한다.
이 문제는 그리디 알고리즘으로 해결가능하다.
그 다음 2. 0/1 배낭 문제는 부분 배낭 문제의 원형으로 물건을 부분적으로 담는 것을 허용하지 않고, 물건을 통째로 배낭에 넣어야 한다.
이 문제는 DP 알고리즘, 백트래킹, 분기 한정 기법으로 해결 가능하므로 지금 여기서는 다루지 않도록 하겠다.
부분 배낭 문제에서는 물건을 부분적으로 배낭에 담을 수 있으므로,
최적해를 위해서 그리디하게 단위 무게 당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣는다.
그런데 만일 그 다음으로 값나가는 물건을 통째로 배낭에 넣을 수 없게 되면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다.
부분 배낭 문제의 대표적인 문제는 아래와 같다.
40그램의 용량을 담을 수 있는 주머니가 존재하고, 4개의 금속 분말과 각 물건의 총 무게와 총 가격이 주어진다.
이 때, 총 가격이 가장 많이 나갈 수 있도록 주머니에 금속을 담아라.
물건 총 무게 총 가격 | 단위 그램당 가격
백금 10그램 60만원 | 6만원
금 15그램 75만원 | 5만원
은 25그램 10만원 | 5천원
주석 50그램 5만원 | 1천원
이 문제도 간단하기 때문에 간략하게 설명하자면, 가장 먼저 그리디 알고리즘을 적용시킬 수 있게
세팅이 필요한데, 각 물건의 단위 그램당 가격을 각각 산출하는 것이다.
단위 그램당 가격을 구하면 해당 가격으로 내림차순으로 정렬하여, 단위 그램당 가격이 제일 많이 나가는 백금을 주머니에 담는다.
이 때, 백금보다 단위 그램당 가격이 작은 다른 물건들은 현재 상황에서 전혀 고려하지 않기 때문에 그리디 알고리즘이라고 할 수 있다.
이제 40-10 = 30 그램을 주머니에 더 담을 수 있고, 주머니의 가치는 6*10 = 60만원이다.
그 다음 가격이 가장 많이 나가는 금을 주머니에 담는다.
이제는 30-15 = 15 그램을 주머니에 더 담을 수 있고, 주머니의 가치는 60 + 5*15 = 135만원이다.
그 다음 마지막으로 배낭에 넣을 수 있는 15그램을 모두 은으로 주머니를 채운다. 이 때, 주머니의 총 가치는 135 + 0.4*15 = 141만원이 된다.
n개의 물건이 존재할 때 부분 배낭 알고리즘의 시간복잡도는,
- O(n) (무게당 가격계산)
- O(n log n) (내림차순 정렬)
- O(n) (물건 개수 반복)
- O(1) (물건넣기)
로 시간 복잡도를 구분할 수 있다.
이 중 내림차순 정렬이 가장 시간이 오래걸리므로 이 알고리즘의 시간복잡도는 O(n log n) 이라고 할 수 있다.
5. 집합 커버 문제
집합 커버 문제는 아래와 같은 문제이다.
n개의 원소를 가진 집합 U가 있다.
U의 부분집합들을 원소로 하는 집합 F가 주어진다.
F의 원소들인 집합들 중에서 어떤 집합들을 선택하여 합집합하면 U와 같게 되는가?
**된다면, 집합 F에서 선택하는 집합들의 수의 최솟값은?
집합 커버 문제의 최적해는 어떻게 찾아야 할까?
F에 n개의 집합들이 있다고 가정해보자.
가장 단순한 방법으로는 F에 있는 집합들의 모든 조합을 1개씩 합집합하여 U가 되는지 확인하고, U가 되는 조합의 집합 수가 최소인 것을 찾는 것이다.
그러면 F={S1, S2, S3}일 경우 모든 조합을 구해야 한다.
- 집합이 1개인 경우 3개 = 3C1
- 집합이 2개인 경우 3개 = 3C2
- 집합이 3개인 경우 1개 = 3C3
- 총합은 3+3+1= 7 == 2^3-1 개
즉, O(2^n)의 시간복잡도가 걸리고 이는 exponential time이므로, NP문제가 된다.
n이 커지면 최적해를 찾는 것은 실질적으로 불가능하다는 뜻이고 그럼에도 불구하고 이런 문제가 주어지고 최적해를 찾으라고 한다면
아마 n이 최대 30을 넘진 않을 것이다.
그래서 이를 극복하기 위한 방법으로는 최적해를 찾는 대신에 최적해에 근접한 근사해를 그리디 알고리즘으로 찾는 것이다.
// 수도코드
Set U = U; // 커버를 해야하는 전체 집합 U
Set F = {S1, S2,,,Sn}; // U의 부분집합들을 원소로 하는 집합 F
setCover(U, F){
Set C = (); // 빈 집합
while(!U.isEmpty()){
Set temp;
for(Set s : F){
// 남은 것 중가장 많이 커버하기만 하면 일단 선택하기 때문에 그리디 알고리즘이다.
if(s가 U의 남은 원소를 가장 많이 커버하면){
temp = s;
}
}
U.remove(temp); // U에서 제거
C.add(temp); // C에 추가
}
return C;
}
실제로 위 처럼 짜면 remove에서 런타임 에러가 발생하겠지만 대략적인 논리의 수도코드를 적어보았다.
위 집합 커버 문제의 근사해 알고리즘의 시간복잡도는 전체 집합 U의 사이즈가 n이라고 할 때
루프가 n번 반복되고, 각 루프당 F의 원소 Si의 수가 최대 n이라면 F와 U의 비교는 총 n^2이 걸리므로
시간복잡도는 O(n^3) 이라고 할 수 있다.
6. 작업 스케줄링 문제
보통 작업 스케줄링 문제는 2가지 유형이 있다.
- 모든 작업을 최소 기계로 완료하는 문제
- 기계 1대로 최대한 많은 작업하는 문제
일단 1. 모든 작업을 최소 기계로 완료하는 문제부터 설명하자면,
이 문제는 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제라고 할 수 있다.
작업 스케줄링 문제에는 여러가지 문제 요소들이 주어지는데,
- 작업 수 // 그냥 입력의 크기라 중요한 요소는 아님
- 각 작업의 시작과 종료시간
이 문제를 해결할 수 있는 작업 스케줄링 알고리즘은 4가지로 구분할 수 있다.
- 빠른 시작시간 작업 우선 배정
- 빠른 종료시간 작업 우선 배정
- 짧은 작업 우선 배정
- 긴 작업 우선 배정
위 4가지 알고리즘 중 1. 빠른 시작시간 작업 우선 배정 알고리즘을 제외하고 나머지 3가지 알고리즘은 항상 최적해를 찾아주는 것은 아니다.
빠른 시작시간 작업 우선 배정 은 작업을 시작할 때, 기계를 사용 가능하면 빈기계에서 작업을 수행하고 만약 빈기계가 없다면 기계를 새로 추가함으로 써 문제를 해결할 수 있다.
// 수도코드
job[N]; // N개의 작업 j1, j2, j...
pq = pq(job); // 이른 시작시간을 기준으로 한 minHeap
result = job_Scheduling(pq);
job_Scheduling(pq){
cnt = 0;
while(!pq.isEmpty()){
j = pq.dequeue();
if(j를 수행할 기계가 존재){
기계에 작업 배정;
}
else{
cnt;
}
}
return cnt;
}
위 수도코드에서 작업을 수행할 기계가 존재하는지, 그리고 존재하면 기계에 작업배정하여 스케줄링하는 부분은 간단히 표현하였다.
전체 작업 시간의 사이즈의 boolean배열의 리스트를 선언하고, 기계가 추가되면 리스트에 배열을 추가하는 식으로 구현하면 된다.
위 알고리즘의 시간 복잡도는 먼저 n개의 작업을 정렬하는데 O(n log n) 이 걸린다.
그리고 n번의 while 루프에서 작업 수행이 가능 한 기계를 탐색하는데 O(nm) 이 걸린다. // m은 사용된 기계의 수
m이 log n보다 큰지 작은지 구분이 안되기 때문에, O(n log n) 와 O(nm) 중 어느것이 해당 알고리즘의 시간 복잡도인지 알 수 없기 때문에,
해당 알고리즘의 시간복잡도는 O(n log n) + O(nm) 이다.
그 다음 2. 기계 1대로 최대한 많은 작업하는 문제도 마찬가지로 작업의 수가 주어지고, 각 작업의 시작시간과 종료시간이 주어진다.
여기서 1개의 기계로 최대한 많은 작업을 스케줄링하는 문제인데, 이 문제는 시작시간을 기준으로 정렬해도 되고, 종료시간을 기준으로 정렬해도 된다.
만약 종료시간을 우선적으로 기준으로 정렬을 했을 때는 종료시간이 같다면 일찍 시작하는 작업순으로 정렬하면 되고,
만약 시작시간을 우선적으로 기준으로 정렬을 했을 때는 시작시간이 같다면 일찍 종료하는 작업순으로 정렬하면 된다.
이른 종료시간을 우선적으로 정렬하였을 때의 수도코드는 이래와 같다.
// 수도코드
job[N]; // N개의 작업 j1, j2, j...
pq = pq(job); // 이른 종료시간을 기준으로 한 minHeap
result = job_Scheduling(pq);
job_Scheduling(pq){
start = 0;
cnt = 0;
while(!pq.isEmpty){
j = pq.dequeue();
if(start <= j.start){
start = j.end;
cnt++
}
}
return cnt;
}
모든 작업을 수행하기 위해 최소 기계수를 카운트하는 1번 문제와 그리디하게 접근하는 것이 비슷해 보이지만,
이 문제는 1대의 기계로 최대의 작업수를 카운트한다는 것에서 다르다고 할 수 있다.
위 알고리즘의 시간 복잡도는 n개의 작업을 종료시간 기준으로 오름차순 정렬하는 O(n log n) 이다.
관련문제
백준 1931: 회의실 배정
마지막으로 그리디 알고리즘을 요약하자면, 그리디 알고리즘은 수행 과정에서 탐욕적으로 일단 한 번 선택하면, 이를 절대로 번복하지 않는다는 것이다.
정렬
셸 정렬
셸 정렬은 우선적으로 버블 정렬과 삽입 정렬에 대한 이야기가 필요하다.
버블 정렬이나 삽입 정렬이 수행되는 과정은 이웃하는 원소끼리의 자리 이동으로 원소들이 정렬된다.
버블 정렬이 오름차순으로 정렬하는 과정에서 작은 숫자가 배열의 앞부분으로 매우 느리게 이동한다.
그리고 삽입 정렬의 경우는 만일 배열의 마지막 원소가 가장 작은 숫자일 경우 그 숫자가 배열의 맨 앞으로 이동해야 하므로, 모든 다른 숫자들이 1칸씩 뒤로 이동해야한다.
셸 정렬은 이러한 단점을 보완하기 위해서 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자들을 앞부분으로 빠르게 이동시키고,
동시에 앞부분의 큰 숫자들은 뒷부분으로 이동시키고, 그리고 가장 마지막에는 삽입 정렬을 수행하는 알고리즘이다.
셸 정렬 아이디어
만약 아래와 같이 값이 저장된 배열이 존재한다고 하자.
30 60 90 10 40 80 40 20 10 60 50 30 40 90 80
먼저 간격 (gap)이 5가 되는 숫자끼리 그룹을 만든다.
각 그룹 별로 삽입 정렬을 수행한 결과를 1줄에 나열해 보면 다음과 같다.
30 30 20 10 40 / 50 40 40 10 60 / 80 60 90 90 80
간격이 5인 그룹 별로 정렬한 결과
- 80과 90같은 큰 숫자가 뒷부분으로 이동하였고,
- 20과 30같은 작은 숫자가 앞부분으로 이동하였다.
그 다음엔 간격을 5보다 작게 하여, 예를 들어, 3으로 하여, 3개의 그룹으로 나누어 각 그룹별로 삽입 정렬을 수행한다.
최종적으로 마지막에는 반드시 간격을 1로 놓고 수행해야 한다.
- 그 이유는, 다른 그룹에 속해 서로 비교되지 않은 숫자가 있을 수 있기 때문이다.
- 즉, 모든 원소를 1개의 그룹으로 여기는 것이고, 이는 삽입 정렬 그 자체이다.
- 삽입 정렬은 대강 정렬이 되어있는 상태에서 좋은 성능을 발휘한다.
// 수도코드
A[N]; // 크기가 N인 정렬되지 않은 배열
shell_Sort(A);
shell_Sort(A){
gap = [ g0 > g1 > ... > gk = 1 ]; // 큰 gap부터 차례로 저장된 gap배열, 마지막 gap은 반드시 1
for(g : gap){
for(i = 0; i < g; i++) { // gap 만큼 반복한다
insertion_Sort(i, gap); // 삽입 정렬
}
}
}
insertion_Sort(i, gap){
for(j = i + gap; j < N; j += gap){ // gap만큼 점프하며 삽입 정렬 수행
for(x = i; x < j; x += gap){
if(A[x] > A[j]){
swap(A, x, j);
}
}
}
}
swap(A, i, j){
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
만약 gap의 5라서 5개의 그룹이 구분되면, 각 그룹별로 삽입 정렬을 수행한다.
이 과정으로 인해 앞에 있는 큰 수가 빠르게 뒤로 가고, 뒤에 있는 작은 수가 빠르게 앞으로 올 수 있게 된다.
gap을 차차 줄여가며, 최종적으로 gap을 1을 둔 삽입 정렬을 시행한다.
삽입 정렬은 이미 어느정도 정렬이 된 상태일수록 효율이 O(n) 에 가까워 진다.
시간복잡도
셸 정렬의 최악 경우의 시간복잡도는 O(n^2) 이며, 셸 정렬의 수행 속도는 간격 선정에 따라 좌우된다.
셸 정렬은 1959년에 발표될 정도로 역사가 오래된 정렬 알고리즘인 만큼, 이 알고리즘에 대한 많은 실험들이 진행되어왔다.
그 중 가장 유명한 gap 설정 방법인 히바드(Hibbard) 간격을 사용하면 O(n^(1.5)) 라고 한다.
히바드 간격은 시작 간격을 2^k - 1로 두고 k를 1씩 줄여서 2^k -1, ... , 15, 7, 3, 1로 간격을 설정하는 방법이다.
이 후 많은 실험을 통한 현재까지의 셸 정렬의 최적의 시간복잡도는 O(n^(1.25)) 으로 알려지고 있다.
아직까지는 가장 좋은 간격이 무엇인지 밝혀지지 않기 때문에, 셸 정렬의 시간 복잡도는 아직 풀리지 않은 문제 이다.
지금까지 알려진 가장 좋은 성능을 보인 간격은 Marcin Ciura이 밝혀낸 1750, 701, 301, 132, 57, 23, 10, 4, 1 이라고 한다.
마지막으로 정리하자면, 셸 정렬은 입력 크기가 매우 크지 않은 경우에 매우 좋은 성능을 보인다.
셸 정렬은 임베디드(Embedded) 시스템에서 주로 사용되는데, 셸 정렬의 특징인 간격에 따른 그룹 별 정렬 방식이 H/W로 정렬 알고리즘을 구현하는데 매우 적합하기 때문이라고 한다.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent