|
|
목적: 배낭채우기 문제(knapsack problem) 해결을 통해 Dynamic
Programming과 Greedy 알고리즘 설계법을 이해하기 위함.
과제물 내용:
배낭채우기 문제: 0/1 배낭채우기 문제와 일반 배낭채우기 문제의 두 가지 버전이 있음.
0/1 배낭채우기 문제와 일반 배낭채우기 문제 해결을 위해 다음 두 가지 알고리즘 설계법을 사용하여야 함:
- 동적계획법 – 0/1 배낭채우기 문제
- Greedy 설계법- 일반 배낭채우기 문제
프로그래밍 작업:
위 2가지 알고리즘을 구현하고 적당한 테스트 데이터를 이용하여 실행할 것.
테스트를 위해 10개 미만의 항목들로 구성된 입력 데이터 2세트 이상 스스로 만들 것.
입력 데이터는 반드시 파일에 저장된 것을 읽어와야 하며, 각 테스트 데이터의 파일의 포맷은 다음 형태일 것:
7 /* 항목의 수 */
50 /* 배낭의 무게 W */
10 20 30 40 55 45 25 /*
항목들의 이익 pi */
8 12 7 15 17 13 11 /* 항목들의 무게 wi */
입력 데이터의 첫 번째 라인은 항목의 수, 두 번째 라인은 배낭의 무게, 그리고 세 번째와 네 번째 라인은 각각 각 항목들의 이익과
무게임.
출력은 한 가지 입력 데이터에 대해 0/1 배낭채우기 문제와 일반 배낭채우기 문제의 해결 결과를 각각 비교할 수 있게 해야 하며, 이 때
반드시 배낭에 들어간 항목 번호, 무게의 합, 이익의 합이 나타나야 함. 또한 출력에 각각의 결과를 얻는데 걸린 시간을 나타냄(가능한 방법
모색해서).
제출물:
1.문제의 설명
2.알고리즘의 설명
3.입력 데이터 설명
4.Comment가 포함된 소스 리스트
5.실행 결과 (스크린 캡쳐 포함)
6.이 문제 해결과정에서 나타난 두 알고리즘 차이의 비교/평가와 이 과제물을 통해 알게 된 사실 요약 (표나 그래프 사용 가능)
계산복잡도와 병렬 알고리즘 |
|
|
| 조회 :
423 |
|
최수원 | 병력특례로 기나긴 군 생활을 마치고 4학년 복학을 앞두고 있는 전산학도이다. 현재 EAI 솔루션을 개발하고
있으며, 계산 생물학이라는 분야를 한번 공부해 보고자 알고리즘 공부를 시작하고 있다. 생물학에는 문외한 임.
지난 호에 우리는 한
가지 문제를 해결하는 여러 알고리즘을 개발하고 분석하는 방법에 대하여 다루었습니다. 각 알고리즘들을 분석했다는 말은 각 알고리즘의 시간복잡도나
시간복잡도의 차수를 구했다는 것을 의미합니다. 지금까지 여러분이 보아온 방법이외의 더 나은 방법으로 알고리즘을 찾을 수는 없을까요?
어떤
문제가 시간복잡도 Θ(n3)인 알고리즘으로 해결되었고, 그 후 시간복잡도 Θ(n2.81)인 알고리즘으로도 해결되었다고 가정합시다(실제 이
알고리즘은 행렬 곱셈 문제를 해결하는 일반 알고리즘과 쉬트라센의 알고리즘입니다(2장 5절 참고). 만일 이 문제를 해결하는데 있어 지금보다 더
나은 알고리즘을 찾아봐야지 하다가 우연히 다른 방식의 해결법을 찾을지도 모를 일입니다. 자신이 찾은 해결법이 앞서 말한 방법(Θ(n2.81)인
알고리즘)보다 더 나은 방법이라는 것을 증명하기 위해서는 새롭게 찾은 알고리즘을 분석해, 즉 시간복잡도를 구해서 앞의 시간복잡도
Θ(n2.81)보다 뛰어나다는 것을 보이면 됩니다. 이 처럼 알고리즘을 개발하고 분석하는 방법으로 이 문제를 접근해 나가는 것도 좋은 방법이지만
많은 연구가들은 이런 방법을 사용하지 않습니다.
한계의 지표를 나타내는 계산복잡도
앞의 문제를 해결하는 좋은 알고리즘의 경우
어느 시간복잡도 이하는 존재하지 않는다고 누군가 말해준다면 또는 그것을 증명해 줄 수 있다면 아무도 그 시간복잡도 이하의 시간복잡도를 가지는
알고리즘을 찾으려 하지 않게 될 것입니다. 바로 문제의 계산복잡도라는 것이 그 문제를 해결하는 방법이 어디까지 좋아질 수 있는가하는 한계를
나타내주는 지표라 하겠습니다.
앞서 얘기한 행렬의 곱셈 문제를 해결하는 알고리즘의 하한은 Ω(n2)이라는 결과가 밝혀졌습니다. 그래서
아마도 앞서 어떤 이가 우연히 구한(?) 알고리즘의 시간복잡도는 쉬트라센 알고리즘의 시간복잡도 Θ(n2.81)보다 작고 Θ(n2)보다는 클
것입니다. 하한이 Ω(n2)라고 해서 꼭 시간복잡도 Θ(n2)인 알고리즘이 있다는 뜻은 아닙니다. 단지 Θ(n2)보다 나은 알고리즘을 찾는 것은
불가능하다는 뜻일 뿐입니다.
다루기 힘든 정도
시간복잡도가 Θ(n2), Θ(2n+1), Θ(nlogn)…와 같이 입력크기
n에 대하여 다항식의 함수로 표시되는 알고리즘을 ‘다항식으로 시간복잡도가 표시되는 알고리즘(ploynominal-time algorithem)’
혹은 ‘다항식 시간 알고리즘’이라고 합니다. 어떤 문제를 다항식으로 시간복잡도가 표시되는 알고리즘으로 풀 수 없을 때, 그런 문제를 ‘다루기
힘들다(intractable)’라고 표현합니다.
알고리즘 이론에서는 해당 문제를 다항 시간으로 시간복잡도가 표시되는 알고리즘으로 풀 수
있는가 그렇지 않는가에 따라서 다음과 같이 분류하고 있습니다.
짾 다항식으로 시간복잡도가 표시되는 알고리즘이 존재하는
문제
짿 다루기 힘들다고 증명된 문제
쨁 다루기 힘들다고 증명되지도 않았고, 다항식으로 시간복잡도가 표시되는 알고리즘도 찾지 못한
문제
짾번 부류의 문제들은 정렬(Θ(nlgn)), 검색(Θ(lgn)), 행렬곱샘(Θ(n2.83)) 등과 같이 시간복잡도가 입력n에
대한 다항식으로 표현되는 알고리즘이 이에 속합니다. 짿번 부류의 문제들은 비다항식 크기의 결과를 요구하는 문제들, 즉 필요 이상으로 많은 답을
요구하는 문제(입력의 크기가 n인데, 결과를 n!개, 2n만큼 내야 하는 문제)들 그리고 비다항식 크기의 결과를 요구하지는 않으나 다항식 시간에
풀 수 없다고 증명된 문제와 결정 불가능한 문제들이 속합니다. 이런 문제들은 상대적으로 거의 없는데 다음과 같이 튜링(Alan Turing)이
증명한 Halting 문제는 결정 불가능한 문제의 대표적인 예입니다.
튜링의 Halting 문제
결정 불가능한
문제(undecidable problem)는 문제를 풀 수 있는 알고리즘이 존재할 수 없다고 증명된 문제를 말하는데, 바로 튜링의 Halting
문제가 문제를 풀 수 있는 알고리즘이 존재하지 않다고 하는 것입니다. Halting 문제는 “어떤 프로그램(또는 알고리즘)이 있는데 그
프로그램이 수행 중에 멈춰(halting) 버릴 수 있는 프로그램인지 아닌지 알 수 있는가를 결정하라”는 것입니다. 만약 이를 알아내는 방법이나
프로그램이 있다면 소프트웨어 회사의 사장이 꽤 반길 만 할 것 같습니다. 튜링은 “Halting 문제는 결정 불가능하다”라고 했는데, 즉
멈추는지 아닌지 실제로 돌려보기 전에는 아무도 알 수 없다는 말 같습니다. 이를 증명하는 과정을 한번 살펴봅시다.
Halting
문제는 결정 불가능하다
일단 이 문제를 풀 수 있는(수행 중에 멈출지 아닐지를 결정하는) 알고리즘이 존재한다고 가정합니다. 그리고 알고리즘
Halt의 입력으로 어떤 프로그램 P가 들어왔을 때 P가 종료하면 ‘True’의 답을 주고, 그렇지 않으면 ‘False’의 답을 준다고 합시다.
Halt는 문제를 해결할 수 있는 알고리즘이라고 말했습니다.
이 Halt라는 알고리즘을 이용해서 다음과 같은 ‘IsHalting’이라는
알고리즘을 만들 수 있습니다(이 알고리즘은 isHalting() 이라는 메쏘드로, ‘Halt’ 알고리즘은 halt() 메쏘드로, 입력 프로그램은
Program으로 표현된다고 합시다).
boolean isHalting(Program p) {
if( halt(p) ==
true ) {
while(true)
print(“is running!!”);
}
}
이 코드를 일반적인
코드로 보면 안 되고 이해를 돕기 위한 상징적인 코드로 봐줘야 합니다. 그리고 이 ‘IsHalting’이라는 알고리즘 또한 프로그램이라는 점을
상기합시다.
첫째, 이 알고리즘(isHalting을 말합니다)이 ‘정상적으로 종료하는 알고리즘’이라고 하고, 자기 자신이 입력으로
들어간다고 합시다(재귀호출 정도로 생각합시다). 그러면 halt(p)(여기서 p는 isHalting이 되겠죠)는 true를 리턴하게 됩니다.
isHalting이 ‘정상적으로 종료하는 알고리즘’이라고 했기 때문입니다. 앞의 코드에서 halt()가 true를 리턴하게 되면 while문을
타고 영원히 종료하지 않게 됩니다. 이는 isHalting이 ‘정상적으로 종료하는 알고리즘’이라고 가정한 논리에 모순이 됩니다.
둘째,
이 알고리즘이 ‘정상적으로 종료하지 않는 알고리즘’이라고 하고 이와 같이 자신이 입력으로 들어간다고 합시다. 그러면 halt(p)는 false를
리턴하게 되고, 앞의 코드에서 보면 halt(p)가 false를 리턴하게 되면서 그냥 종료하게 됩니다. 마찬가지로 ‘정상적으로 종료하지 않는
알고리즘’이라고 한 가정에 모순이 됩니다.
이런 가정에 모순된 점들로 처음에 가정한 ‘이 문제를 풀 수 있는 알고리즘(Halt)이
존재한다는 것’이 모순임을 증명하게 됩니다. 또한 Halt 알고리즘은 존재하지 않다는 것을 증명하게 되는 것입니다. 어쩌면 우격다짐 같아
보이지만 곰곰이 생각해보면 이해할 수 있을 것입니다. 결정 가능하면서 다루기 힘든 문제들도 존재하며, 이들 또한 짿번 부류의 문제에 속합니다.
그리고 쨁번 부류에 속하는 문제들은 다항시간 복잡도로 표시되는 알고리즘을 찾지 못했지만, 그렇다고 그런 알고리즘이 불가능하다고 증명도 못한
문제들입니다.
P와 NP
그러면 왜 이 문제가 NP에 속하는가를 이해하기 위해서는 결정 문제와 비결정 문제에 대해 이해를
해야 합니다. 지난 호에 다룬 ‘0-1 배낭 채우기 문제’를 다시 상기해 봅시다. “어떤 배낭에 넣을 수 있는 아이템들의 무게와 가치를 알고
있을 때 배낭이 담을 수 있는 최대 무게 W를 넘지 않으면서 아이템들의 총 가치의 합이 최대가 되게 하는 아이템을 담을 수 있는 조합을
찾아라”하는 문제입니다. 이 문제를 다음과 같이 바꾸어 봅시다. “이 아이템 조합 중에 가치의 합이 p를 넘는 조합이 있는가?”라는 문제로
바꾸면 좀더 쉬운 문제가 됩니다. 후자와 같이 문제의 답을 ‘예’ 혹은 ‘아니오’로 답할 수 있는 문제를 결정 문제라고 합니다.
이와
같이 최적화 문제들은 그에 상응하는 결정 문제를 만들어 낼 수 있습니다. 그러면 왜 결정 문제를 만들까요? 상대적으로 해결하기 쉬운 결정 문제로
다항식으로 시간복잡도를 표현할 수 있는 알고리즘으로 찾아낸다면, 그 결정 문제에 상응하는 최적화 문제를 푸는 알고리즘을 만들어 낼 수 있기
때문입니다.
그러면 P와 NP는 무엇인가? P는 ‘다항식시간 알고리즘’으로 해결할 수 있는 문제들의 집합이라고 정의할 수 있으며, NP는
‘다항식시간 비결정적 알고리즘’으로 풀 수 있는 모든 결정 문제의 집합이라고 정의합니다.
다항식시간 비결정 알고리즘
‘0-1 배낭
채우기 문제’의 결정 문제로 “이 아이템 조합 중에 가치의 합이 p를 넘는 조합이 있는가?”를 다음과 같은 방법으로 풀어 봅시다.
짾 아이템의 조합을 마구잡이로 생성해 냅니다(추측 과정).
짿 그 조합의 가치 합이 p를 넘는가를 검증합니다(검증
과정).
이와 같이 추측 과정과 검증 과정을 거치는 이런 방식의 알고리즘을 ‘비결정적 알고리즘(Nondeterministic
algorithm)’이라 합니다. 실제로 이 방식으로 문제를 해결하는 것은 불가능해 보이는데, 다음과 같은 경우 비결정적 알고리즘이 이 결정
문제를 ‘푼다’라고 얘기합니다.
첫째, 결정 문제의 답이 ‘예’인 경우, 즉 가치 합이 p가 넘는 아이템의 조합을 제시하는 입력에 대해서
검증 과정을 거쳤을 때 ‘정답이 맞음’이 되는 입력이 추측 과정에 의해 생기는 경우입니다. 둘째, 결정문제의 답이 ‘아니오’인, 즉 가치 합이
p가 넘지 않는 아이템의 조합을 제시하는 입력에 대해서 검증 과정을 거쳤을 때 ‘정답이 맞음’이 되는 입력이 추측 과정에 의해 생기지 않는
경우입니다. 즉, 검증 과정에서 정확하게 맞고 틀림을 결정할 수 있는 입력들만 추측 과정에서 생성한다면 비결정적 알고리즘이 이 문제를 푼다고
얘기합니다. 그리고 ‘비결정적 알고리즘’이 답을 검증하는 부분의 알고리즘이 다항식시간(다항식으로 시간복잡도를 표현할 수 있는) 알고리즘일 때,
이를 ‘다항식시간 비결정 알고리즘’이라고 합니다.
종합해 보면 문제가 NP에 속하기 위해서는 ‘다항식시간에 검증’을 하는 알고리즘이
존재해야만 합니다. ‘0-1 배낭 채우기 문제’의 결정 문제인 “이 아이템 조합 중에 가치의 합이 p를 넘는 조합이 있는가?”하는 문제의 경우
이를 검증하기 위한 비결정 알고리즘 검증 부분의 알고리즘이 다항식시간이므로(입력 아이템 집합들이 들어오고, 이의 가치를 합해서 p가 넘는지 안
넘는지를 검사하는 일은 충분히 다항식시간에 마무리 지을 수 있습니다) NP 문제에 속하게 됩니다. 그러나 ‘0-1 배낭 채우기 문제’의 결정
문제를 ‘푸는’ 다항식시간 알고리즘이 반드시 존재한다는 것은 아닙니다. 단지 ‘검증’하는 알고리즘이 다항식시간이라는 것 뿐입니다. 왜냐하면 답을
추측하는 과정에서 다항식시간을 넘을 경우가 충분하기 때문입니다(아이템 집합의 수가 n이라면 이 집합의 가능한 모든 부분집합의 수가 2n이기
때문입니다).
그렇다면 어떤 결정 문제가 주어진다면 여러분들은 이 문제가 NP에 속하는 문제임을 보일 수 있겠습니까? 조금은 난해한
말장난 같아 보입니다만 P니 NP이니 하는 이 모든 것이 알고리즘 문제들을 분류하기 위해서 생겨난 용어일 뿐입니다. 그리고 P에 속하는 문제는
당연히 NP에도 속하는데, NP에 속하는 문제는 P에 속하지 않는다고 증명된 문제는 하나도 없다고 합니다. 즉 집합 관계상 NP-P=0,
NP=P 일지도 모르는데, 많은 사람들이 N≠NP라고 생각하는데 이를 증명한 사람이 아무도 없다고 하는군요. 여러분들이 한번 도전해
보길….
병렬 알고리즘
크기가 n인 배열 s에서 가장 큰 수를 구하는 문제를 생각해 봅시다.
int
find_largest(int[] s) {
int largest = s[0];
for( int i=1; i if( s[i] > largest )
largest = s[i];
}
}
이와 같은 코드는 이
문제를 해결하는 코드입니다. 배열 s의 크기가 n이므로 ‘s[i] > largest’의 코드는 n-1번 수행되고 결국 Θ(n)의
시간복잡도를 가지게 됩니다. 앞의 프로그램을 프로세서(cpu)가 여러 개인 환경에서 병렬로 실행시키면 어떨까요? 더 빨리 수행이 될까요? 여기서
많은 사람들이 병렬 수행에 대한 오해를 하고 있는데 이 프로그램은 병렬 프로세서에서 동시에 수행시킨다고 해서 각 프로세서가 일을 나누어서
처리하지 않습니다. 물론 병렬 환경을 지원하는 컴파일러나 환경의 도움으로 앞에서 처럼 작성된 코드는 컴파일 타임에 병렬 환경을 지원하게끔
변환되어져 수행될 수도 있지만 그런 상황을 생각하지 않는다면 말입니다. 따라서 우리는 이 문제를 병렬 알고리즘으로 보다 빠른 시간에 해결하고자
한다면 병렬 환경을 생각해서 알고리즘을 재작성해야 하는 것입니다.
앞의 배열 s에서 최대수를 찾는 문제를 병렬 알고리즘으로 생각해
봅시다. 우선 병렬 환경에 대한 이해를 바탕으로 해야 하는데 ‘CREW PRAM 모델’에서 생각하도록 합시다. 이 모델은 각 프로세서가 각각의
제어장치와 독자 메모리 영역을 가지며, 모든 프로세서가 상호연결 네트워크로 공유하는 공유 메모리가 있고, 이 공유 메모리에 대한 접근이 동시에
읽기가 가능하고 배타적으로 쓰기가 가능한 모델입니다. 이 모델에 대한 자세한 이해나 다른 병렬 모델에 대해서는 책을 참조하면 됩니다. 다음은
앞의 n개의 수 중 가장 큰 수 찾기를 n/2개의 프로세서를 가지고 해결해나가는 방법입니다.
이해하기 쉽게 n을 8이라 하고, n개의
수는 다음과 같다고 합시다(12, 10, 5, 15, 18, 12, 4, 16). 프로세서의 수를 4(n/2)개라고 다음과 같이
표시합니다(P1, P2…P4). 모든 프로세서가 공유하는 메모리에 배열 S[]가 앞의 자료를 가지고 있다고 합시다. 각각의 프로세서가 동시에
2개씩의 데이터를 공유 메모리에서 고유 로컬 메모리로 차례로 가져와서 두 수를 비교해서 큰 수만을 위의 공유 메모리 배열 S[]에 차례대로
쓴다면, 첫 단계를 거치고 나면 S[]의 내용은 다음과 같을 것입니다. (12.15,18,16,...) 뒤의 4개의 데이터는 무의미하겠죠. 다시
앞의 4개의 데이터를 가지고 똑같은 과정을 P1, P2만으로 처리를 합니다. 그 후 S는 (15, 18…)이 되고, 다음 마지막의 단계를 거치면
S는 (18…)이 되어 원하는 가장 큰 수를 S[0]에서 얻을 수 있습니다. 이런 알고리즘의 방식으로 해결할 때 가장 많이 사용되는 프로세서
P1의 수행 수는 3(lg8)번이 되게 됩니다. 일반화해보면 lgn의 수행 횟수를 갖게 되고 Θ(lgn)의 시간복잡도를 가지게 되어, 1개의
프로세서가 처리하는 방식에 비해 성능의 향상이 있음을 알 수 있습니다.
책과 씨름하길 바라며
지금까지 3회에 거쳐 책의
전반적인 소개와 내용의 이해에 중요한 몇몇 부분에 대한 이해를 목적으로 진행해 왔습니다. 책을 다 읽지 않고도 통독을 했다는 느낌을 받을 수
있도록 의도하였는데 잘 되었는지는 모르겠습니다. 끝으로 이제는 독자 분들이 스스로 원하는 재미있는 알고리즘을 찾아서 이해하고 분석하고 새로운
알고리즘을 설계ㆍ분석해 보일 수 있는 능력을 이 책을 통하여 배양할 수 있기를 바랍니다.
정리 | 조규형 |
jokyu@korea.cnet.com
| ///////////////////////////// |
0-1 배낭채우기 알고리즘을 구현하는데요.
|