본문 바로가기

IT 이론/자료구조&알고리즘9

Branch and bound 기법을 이용한 TSP Branch(가지)와 Bound(범위) 기법이란 "최적의 경우"를 찾는 알고리즘으로써, '최소한 이정도는 되어야 답이 될 가능성이 있다' 라는 범위(Bound)를 정 해두고 범위를 벗어나는 값들은 가지치기(Branch)해가며 결과값을 추적한다. 이 알고리즘으로 풀 수 있는 문제는 대표적으로 Knapsack과 TSP가 있는데, 인터넷에 있는 예제들은 대부분 Knapsack에 관한 예제이므로, 여기선 TSP를 풀어 보도록 하자. 0 5 2 4 1 6 0 5 4 3 2 3 0 4 5 2 3 4 0 1 4 2 1 3 0 위와 같은 input이 있다. 그래프는 그리지 않겠다. 이번 알고리즘은 확실히 Matrix로 보는게 더 편하다. 매트릭스를 어떻게 보는지 모르는 분들을 위해 간단하게 설명 드리자면 (1, 1),.. 2013. 5. 28.
[C언어 소스] Backtracking을 이용한 N-Queen 문제 해결법 일단 N-Queen문제가 뭘까? 이 문제의 목적은 잘 모르겠으나 알고리즘을 공부하다 보면 자주 보이는 문제이다. 이 문제를 푸는 방법도 참 여러가지다. 일단 이 문제는 이름대로 장기판에 여왕말을 놓는 문제인데, 이 여왕말이 다 적이다. 어떤 여왕말이든 다른 여왕말을 먹을 수 있다는 것이다. 하지만 그걸 못 먹도록 하는게 이 문제의 핵심이다. 즉, 모든 여왕말이 다른 여왕말이 바로 공격할 수 있는 거리에 있는 것이다. 그 말인 즉슨 어떤 여왕말이 다른 여왕말을 먹으면 그 여왕말은 또 다른 말에게 먹히기 때문에 아무도 움직일 수 없는 상태인 것이다. 예를 들어 4x4의 체스 판에서는 Q Q Q Q 이런 구도라면 어떤 여왕말도 쉽사리 움직 일 수 없다. 그리고 5x5라면 Q Q Q Q Q 이런식의 결과가 나올.. 2013. 5. 26.
Chainging Coin System 관련 Suppose you are in the wonder land in which the coin changing system is not governed by the greedy strategy. There are only 4 coins cl = 1, c2 = 3, c3 = 7, and c4 = 11 in the country. (a) Construct N[0..21] and P[0..21] for changing 21 wons. (b) Write a recursive program "void print_coins (int x)" to print optimal coins for x wons. You must assume that array P[0..21] is global to this program. (.. 2013. 4. 15.