http://people.csail.mit.edu/bdean/6.046/dp/

위 링크의 Dynamic Programming 문제들 중,

남은 두 문제인 Edit Distance 와 Two-Person Traversal of a Sequence of Cities 에 대하여 정리해 본다.

( 12번 Bin Packing 은 굳이 할 필요가 없어 패스 )

이 두 문제는 도대체 해결방법이 떠오르지 않아, 인터넷의 풀이를 보고 말았다.

두 문제의 풀이를 보면서 일단 DP 문제라도,

문제를 Recursive 하는 푸는 방법을 떠 올리고,

거기서 DP 풀이를 찾는 것이 좋겠다는 생각이 들었다.



- Edit Distance

문제) String A, String B 가 있을 때, A -> B 로 바꾸는 최소한의 Operation 수를 구하는 문제이다.

        Operation 은 다음과 같은 3 가지가 있다.

        1. Insert a character, 2. Remove a character, 3. Change a character to another character.


이 문제는 아래 링크의 풀이를 참고하였다.

https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/styles/pages/editdistance.html

거기서 사용된  예를 가지고 문제를 쪼개는 방법을 설명해 본다.




- Two-Person Traversal of a Sequence of Cities

문제) 순서가 있는 N 개의 도시가 있다. (지리적으로 순서가 있다는 의미가 아니다. 방문할 수 있는 순서를 말한다. )

        그리고 각각의 도시는 모두 연결되어 있다.

        이 도시들을 두 집합으로 나누고 (연속된 도시일 필요는 없다.),

        두 사람 A, B 가 각각의 도시 집합을 방문한다고 할 때,

        A, B 의 이동거리의 합이 가장 짧은 경우는 얼마가 되는가?

        단, A, B 방문 시작점은 각 도시 집합의 첫 번째 도시이다.


처음엔 문제 자체를 이해를 못해서 한참 해멨다.

그 다음에는 문제를 어떻게 풀어야 하는지도 몰라서 한참 생각하다가,

결국 인터넷을 뒤졌는데, 이걸 깔끔하게 설명한 곳도 찾기가 힘들었다.

그리다가 아래 링크의 Grimbal 이란 사람의 리플을 보고 풀었다.

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1311271494








반응형

설정

트랙백

댓글

- Counting Boolean Parenthesizations

문제) 5개의 심볼을 가지고 만든 Boolean Expression을 괄호로 묶어 Evaluation했을 때,

        결과가 true 가 되는 Case 의 갯수는 몇 개인가?

        심볼 = { true, false, and, or, xor }

        예를 들면, ' false and true xor true '가 true 가 되는 괄호 묶기 방법은 1가지 밖에 없다.




- Optimal Strategy for a Game

문제) N 개의 동전이 있다. (N은 항상 짝수)

        각 동전의 가치는 V(0)...V(N)이며, 이 동전들은 일렬로 놓여져 있다.

        두 사람이 일렬로 놓여져 있는 동전의 양쪽 끝 동전 중 하나를 가질 수 있다고 할 때,

        처음 시작하는 사람이 가능한 최대 금액은 얼마인가?


       상대방이 무엇을 선택하는지는 여기에서 문제가 아니다.

       모든 경우의 수에서 최대값을 찾는 문제인 것이다.

       처음엔 "상대방은?" 이라는 생각에 잠시 혼란스러웠었다.



두 문제 다, 나름 풀만한 문제였다.

근데, 이 두 문제 전에 있는 문제인 Edit Distance는 당췌 아이디어가 안 떠오르네...








반응형

설정

트랙백

댓글

1) Building Bridges

문제내용:

가운데로 강이 지나가는 2차원 지도가 있다. 강 북쪽과 남쪽으로 각각 N 개의 도시가 있다.

이 N 개의 도시를 A(1)...A(N), B(1)...B(N) 이라고 한다.

이 도시는 순서대로 위치해 있지는 않다. (즉 A(1) 옆에 A(2) 가 있는게 아니라는 말)

강 북쪽과 남쪽은 연결하는 다리를 건설하고자 하는데,

다리의 건설은 A(k) 와 B(k) 만 연결할 수 있다.

이 때, 가장 다리를 많이 놓을 수 있는 갯수는 몇 개 인가?


설명이 은근히 길다.

그림으로 그리고 싶지만, 잘 찾지도 못하겠고 그리기도 귀찮아서 패스.





- Balanced Partition

문제:

N 개의 정수를 가진 집합을 2개의 Subset S1, S2 로 나누었을 때, |Sum(S1) - Sum(S2)| 의 최소값을 구하라.


사실 이 문제는 내가 못 풀었다.

Subset 을 나누는 데, 단순히 한 Element 를 기준으로 좌/우로 나누는 건줄 알았다.

그래서 문제를 이해해서 제대로 못 풀었다.

그리고 해답을 얼핏 보고 아하.. 하고 다시 푼 문제.





반응형

설정

트랙백

댓글

- Longest Increasing Subsequence

임의의 순서로 나열된 집합 A 가 있을 때,

값이 증가하는 최장 길이 수열을 찾는 문제이다.

단, 수열은 인접해 있을 필요는 없고,

이러한 수열은 여러가지 종류가 있을 수 있다.


예를들어 아래와 같은 수열이 있을 경우

{ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }

LIS 는 0, 2, 6, 9, 13, 15 혹은 0, 4, 6, 9, 11, 15 이 되겠다.


처음에는 2차원 배열로 계산을 했었는데,

그다지 좋은 방법은 아니었다. 

메모리도 많이 쓰고 최장 길이는 찾을 수 있었으나, 실제 수열을 찾지는 못했기에...




- Box Stacking

임의의 N 개 타입의 박스가 있을 때, 박스를 가장 높이 쌓을 수 있는 경우와 그 높이를 구하는 문제이다.

박스의 갯수는 제한이 없다. 

단, 박스를 쌓기 위해서는 strictly larger 야 한다.

( 즉, 박스의 Width > Depth 라고 했을 때,

 아래박스.Width > 위박스.Width && 아래박스.Depth > 위박스.Depth 를 만족해야 한다. )



* Box Stacking 문제부터 STL을 사용 해 보았는데,

  Box Class 의 Sorting 이 조금 문제가 있었다.

  STL 의 sort() 를 이용하기 위해 operator < 오버로딩 하였는데,

  단순히 return (w > b.w && d > d.w); 를 하게 되면,

  원하는대로 정렬이 되지 않아, !((w < b.w) || (d < b.d)); 를 사용하였다.

  Box 처럼 크다, 작다, 크지도 작지도 않다, 같다..  이런식으로 구분되는 것에는 좀 주의해야 하겠다.





반응형

설정

트랙백

댓글

N 개 타입의 동전으로 어떠한 금액을 만드는 것과 관련된 문제이다.


여기서 몇 가지 문제를 생각할 수 있는데,


1. Frobenius coin problem

이 문제는 NP-hard 문제로, GCD(최대공약수)가 1인 N 개 타입의 동전으로 만들 수 없는,

가장 큰 수를 찾는 문제이다. 이 수를 Frobenius(프로베니우스) number 라 한다.

하지만 N이 1,2,3 일 때는 다항시간에 찾을 수 있는 공식이 나와있다.

더 자세

한 내용은 위키피디아 http://en.wikipedia.org/wiki/Coin_problem 참고.



2. N 개 타입의 동전으로 어떠한 금액을 만들 때, 가장 적은 수의 동전을 사용했을 때의 동전의 수.

(단 N >= 1 이고 N[1] = 1 )

요 문제는 Greedy 한 방법으로 풀어도 되지만, DP 방법으로 풀 수도 있다.




3. N 개 타입의 동전으로 어떠한 금액을 만들 때, 가능한 동전 조합의 경우의 수를 구하는 경우.

(단 N >= 1 이고 N[1] = 1 )

이 문제는 약간 어려웠던거 같다. 그냥 생각만으로는 잘 안되서,

아주 간단한 케이스를 가지고 종이에 적어가면서 확인했다.




조합의 수를 구하는 문제는 좀 헷갈리긴 했지만,

생각을 좀 해보고, 간단한 케이스를 확인해 보면서 찾을 수 있었다.

반응형

설정

트랙백

댓글

문제) N 개의 실수 A(1) ~ A(N)이 있을 때, 연속된 수 A(i) ... A(j)의 합이 최대가 되는 값을 구하라.


솔직히 Brute Force 방식으로 풀어도 O(N^3)의 복잡도를 가지므로,

NP-Complete 한 문제는 아니다.

하지만 D.P 연습으로 공부를 하는 거니깐.



D.P 문제 중에는 난이도가 낮은 문제가 아닐까?

반응형

설정

트랙백

댓글

- Knapsack Problem

Dynamic Programming을 공부하면서,

(정말 정말 너무나 쉬운) Fibonacci 수열의 값을 구하는 예를 제외하고,

가장 많이 이용되는 예가 아닐까?


열 마디 설명보다 그림이 이해하기 쉬우므로, 부담없이 인용할 수 있는 위키피디아 그림을 가져왔다.

File:Knapsack.svg
(저자: Dake, 출처: http://en.wikipedia.org/wiki/File:Knapsack.svg )


위 그림과 같이 15kg까지 담을 수 있는 배낭에

각각 Value와 Weight를 가진 N 종류 타입의 상자들을 담았을 때,

Max Value가 되는 값이 얼마인가? 를 구하는 문제이다.


Knapsack Problem에는 3가지 종류가 있다.

이 구분은 사용가능한 N 종류 타입의 아이템의 갯수에 따라 나뉜다.

(위 그림으로 치자면 상자의 각 타입의 상자가 몇 개씩 있느냐?)


1. 0-1 Knapsack Problem : N 개의 타입의 아이템이 1개씩 있음.

2. Bounded Knapsack Problem : N 개의 타입의 아이템이 x(임의의 갯수)개씩 있음.

3. Unbounded Knapsack Problem : N 개의 타입의 아이템의 갯수 제한이 없음.


기본적인 해결 아이디어는 동일하다.

하지만 종류에 따라 아이디어를 조금 간소화 시킬 수 있다.


3가지 방법에 대해 일반적으로 사용할 수 있는 Knapsack 소스는 다음과 같다.



결론

다시 한번봐도 어렵긴 마찬가지다.

여러가지 D.P 문제들을 보고 익숙해지길 바라는 수 밖에.



(추가사항)

Knapsack Problem 중에 아이템을 쪼갤수 있는 Case의 경우는,

Value/Weight 가 높은 순으로 Greedy 한 방법을 통해 해결할 수 있다.

반응형

설정

트랙백

댓글

'C로 구현한 알고리즘' (Algorithms with C) 의 간단한 리뷰를 남겨본다.


먼저 자료구조 부분은 괜찮았다.

실제로 동작하는 소스 코드도 제공하고,

어느 정도 기본을 익히기에는 충분하다고 생각한다.


알고리즘 부분에 대해선 내가 원하는 스타일은 아니었다.

내가 원했던 것은, 알고리즘 접근 방법에 따라 분류를 나누고

(Divide&Conquer, Dynamic Programming, Greedy Algorithm, Heuristic Algorithms 등...)

이 방법을 이용해 문제를 해결하는 것을 원하였는데,

이런 설명 보다는 적용 분야에 따라 주제를 나누고 설명한 것이 별로였다고 본다.

( 물론 기하 알고리즘과 같은 새로운 분야에 대한 이야기는 흥미로지만 )


특히, 강력하지만 익숙해지기 어려운 Dynamic Programming 에 대한 설명은

거의 전무했다는 점에 대해선 실망스럽다.


결론은,

컴퓨터 프로그래밍 공부를 위해 알고리즘 책을 선택해야 한다면, 추천하고 싶진 않다.

앞에도 이야기 했듯, 자료 구조 내용은 나쁘진 않았지만,

알고리즘 책으로써는 별로라고 생각한다.


반응형

설정

트랙백

댓글

책의 기하 알고리즘 부분에서는

1. 선분 교차 테스트

2. 컨벡스 헐

3. 구면 위의 호의 길이

를 다룬다.


이전 TSP 에서 선분교차에 대해서 자세한 방법에 대한 이해를 못하여,

대충 직사각형 교차 체크만 하고 넘어갔기에, 거기에 대해 좀 자세히 알아보고,

나머지는 개념만 이해하고 넘어가겠다.


1. 선분 교차 테스트

점 A, B, C, D 에 대하여

선분 AB 와 선분 CD 가 서로 교차하는지,

컴퓨터를 이용하여 확인하는 방법에 대한 것이다.

수학에서라면 간단히 두 선분의 직선의 방정식의 해를 구하여

그 해가 선분의 범위안에 들어가는지 체크하면 쉽지만,

일반적으로 정확한 실수 연산이 되지 않는 컴퓨터 언어로는

그렇게 간단히 되지 않는다.


그래서 다음과 같은 2 단계를 따른다.

i) 선분의 양 끝 점을 대각선으로 하는 직사각형을 그려 교차하는 부분이 있는지 체크 한다.

   교차하는 부분이 없다면 교차하지 않음. 교차하는 부분이 있다면 ii) 로.

ii) 삼각형 ABC와 삼각형 ABD의 Signed Area의 곱이 <= 0, (곱이 0 이라면 선분이 겹치는 경우)

   AND 삼각형 CDA와 삼각형 CDB의 Signed Area의 곱이 <= 0 인지 확인.

i) 조건을 패스하고 ii) 조건이 True 가 된다면 두 선분은 교차한다.

Signed Area 는 세 점으로 만들어지는 면적을 구하는 데,

세 점의 방향에 따라 '+' 나 '-' 값을 가진다.

Signed Area 를 구하는 방법은 다음과 같다.

점 A, B, C 의 (x, y) 좌표를 각각 (a[0], a[1]), (b[0], b[1]), (c[0], c[1]) 이라고 했을 때,

삼각형 ABC의 Signed Area = ( a[0]*b[1] - a[1]*b[0] + b[0]*c[1] - b[1]*c[0] + c[0]*a[1] - c[1]*a[0] ) / 2

공식으로 구할 수 있다.


  



2. 컨벡스 헐(Convex Hull)

어떤 점 집합의 컨벡스 헐은 그 집합의 모든 점들을 포함하는 가장 작은 볼록 다각형을 말한다.


File:ConvexHull.svg
(출처: http://en.wikipedia.org/wiki/File:ConvexHull.svg )


위 그림에서 파란색으로 표시된 다각형이 바로 컨벡스 헐이다.


점 집합 P에 대한 컨벡스 헐을 만드는 한 방법은 Jarvis 행진(Jarvis's march)이라는 방법을 사용하는 것이다.

 File:Jarvis march convex hull algorithm diagram.svg
(출처: http://en.wikipedia.org/wiki/File:Jarvis_march_convex_hull_algorithm_diagram.svg )


위와 같이 P0 에서 시작하여 각 점에 대하여 각도가 가장 작거나 큰 점들을 찾아서 계속 연결해 나가면 된다.




3. 구면 위의 호의 길이

구면 위의 두 점이 있을 때, 두 점의 거리(호의 길이를 말함)를 계산하는 방법에 대한 것이다.

자세한 수식은 생략하고 간단히 과정을 설명하겠다.


1. 두 점 A, B 의 좌표가 (x,y,z) 형태가 아닌,

   (구의 중심으로 부터의 거리, xz평면에서 y축 방향으로의 각도, yz평면에서 x축 방향으로의 각도) 형태로

   주어질 경우 (x,y,z) 형태의 좌표로 바꾼다.

2. 벡터의 내적을 이용하여 두 점 A, B의 각도(a)를 구한다.

3. 아래와 같이 원의 호를 구하는 공식을 이용하여, 호의 길이를 구한다.

 



결론

기하 문제들을 컴퓨터로 표현하고 해결하는 것은 흥미로운 과정이다.

특히, 게임 프로그래밍에 관심이 있다면 필수 과목이 아닐까?

반응형

설정

트랙백

댓글

이번엔 그래프 알고리즘 두 번째,

Dijkstra 알고리즘과 TSP 문제에 대해서 정리해 보자.


- Dijkstra 알고리즘

일반적으로 '다익스트라'라고 읽었던 것 같은데...

위키피디아에는 '데이크스트라'가 제대로 된 이름이라고 하는거 같다.

이 Dijkstra 알고리즘은 Edge의 Weight가 양수인 Graph가 있을 때,

두 Vertex간의 Shortest Path를 찾는 알고리즘이다.

(* Edge의 Weight가 음수도 있을 경우는 Bellman-Ford 알고리즘을 사용한다)


(2012.7.30 수정)

Dijkstra 알고리즘은 Greedy Algorithm이지만, Optimal Solution을 찾는 알고리즘이다!

Dijkstra 알고리즘은 Dynamic Programming + Greedy 방법으로 Optimal Solution 을 찾는 알고리즘이다.
위키피디아에 있는 Pseudocode를 보면서 알고리즘의 아이디어를 알아보자.

1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: // 초기화 3 dist[v] := infinity ; // v 로부터의 거리를 아직 모름 5 previous[v] := undefined ; // 최적의 경로 배열 초기화 7 8 dist[source] := 0 ; // 시작점 -> 시작점의 거리는 0 9 Q := the set of all nodes in Graph ; // 최초에는 그래프의 모든 노드에 대하여 10 // 체크를 해야함.

11 while Q is not empty: // 메인 루프 12 u := vertex in Q with smallest distance in dist[] ; // 처음에는 시작점에서 시작 13 if dist[u] = infinity: 14 break ; // 시작점에서 접근 가능한 모든 노드에 15 // 대하여 체크가 끝났음. 16 17 remove u from Q ; 18 for each neighbor v of u: // 단, 'v' 는 Q 에 포함된 노드. 20 alt := dist[u] + dist_between(u, v) ; 21 if alt < dist[v]: // Relax (u,v,a) - dist, previous 업데이트 22 dist[v] := alt ; 23 previous[v] := u ; 24 decrease-key v in Q; // dist[] 값이 변하므로, 필요시 Reorder Q. 25 return dist;

먼저 각 변수의 의미 및 설명인 필요한 라인에 대하여 알아보자.

- dist[v]: 시작 Vertex 에서 Vertex 'v' 까지의 거리. 알고리즘이 진행되면서 계속 업데이트 됨.

- previous[v]: 최적의 경로에서 Vertex 'v'의 이전 Vertex.

- Q : 최소 경로 확인이 끝나지 않는 Vertex 'v' 의 집함.

       Q 를 단순히 Linked List 나 Array 로 구성한다면, 복잡도가 O(V^2) 이 될 것이다. (그래도 구현이 쉽다)

       이 Q 의 v.key 값은 dist[v] 값이 되고, 이 key 값에 대해서 Binary Heap으로 Q를 구성한다면,

       복잡도는 O(E log V)가 된다. Fibonacci Heap 으로 Q를 구성한다면 O(E + V log V)가 된다.

- 18번 라인: 메인 루프에서 현재 체크 중인 노드의 인접 노드를 체크할 때, 인접 노드가 Q 에 있는지 유무를

                 반드시 확인해야 한다.

- 21번 라인: Relax (책에는 늦춘다) 라는 표현을 썼는데,

                 조금 설명을 해보자면 현재 dist[u] 는 최적의 경로이다.

                 여기에서 E(u,v) 를 더 했을 때 Weight 값(alt)이, 기존의 dist[v] 보다 작으면 alt 값을

                 dist[v] 의 새로운 최적의 경로로 설정하는 것이다.

- 24번 라인: Q 를 Min-Heap 등으로 구현하였을 경우,

                 Q 의 원소 'v' 의 key 값이 변경되므로 Q 를 재정렬할 필요가 있다.


위의 알고리즘이 끝난 뒤, Short Path 는 아래와 같은 Pseudocode 로 구할 수 있다.

1  S := empty sequence
2  u := target
3  while previous[u] is defined:
4      insert u at the beginning of S
5      u := previous[u]
6  end while ;

음..이건 따로 설명은 필요없어 보인다.



- TSP (Travelling Saleperson Problem, 외판원 여행 문제)

( http://en.wikipedia.org/wiki/Travelling_salesman_problem )

많은 알고리즘 책에서 설명하는 대표적인 NP-Hard 문제이다.

문제는 간단하다.

"여러 도시(Vertex)들이 있고 한 도시에서 다른 도시로 이동하는 비용(Edge weight)이 모두 주어졌을 때,

모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서는 무엇인가?"


그래프 이론의 용어로 설명하자면,

"Weighted Complete Graph[각주:1](가중치가 있는 완전 그래프)에서

 가장 작은 가중치를 가지는 Hamiltonian cycle[각주:2](해밀턴 사이클)을 구하라"

이다.


현재는 이런 문제를 다항시간에 풀 수 있는 알고리즘이 없으므로,

Heuristics(휴리스틱) 알고리즘이나 Approximation(근사) 알고리즘을 사용하여 빠르게 좋은 해를 찾는다.

(최근의 방법들은 높은 확률로 최적 해에서 2% ~ 3% 정도 오차가 있는 근사 해를 찾아낸다고 한다)

여기에는 여러가지 방법이 있을 수 있지만, 검색 좀 해보니 이런 방법들에 대한 연구는

거의 텀 프로젝트 수준이므로 패스하고,

Nearest Neighbor Algorithm 과 2-Opt Algorithm 에 대해서 설명하겠다.


- Nearest Neighbor Algorithm

( http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm )

이 방법은 단순하다. 일단 시작점이 주어지면, 시작점에서 가장 가까운 다음점을 찾아 연결한다.

그리고 그 다음점에서 다시 가장 가까운 점을 찾아 연결하는 과정으로 모든 점을 연결하고,

마지막 점과 시작점을 연결하는 것으로 완료된다.


- 2-Opt Algorithm

이 알고리즘은 처음부터 해를 찾는 알고리즘이 아니라,

NN Algorithm 등으로 찾은 해를 Improve 하는 알고리즘이다.

(더 이상 개선이 되지 않을 때 까지 반복을 하면, Local Optimal 이 되는 것이다)

(* 나의 경우엔, 두 선분의 Cross Check 가 귀찮아 대충 사각형을 그려서 겹치는 부분이 있으면,

    바꿔서 Length 를 구해보고 개선이 되면 바꾸는 방법을 사용하였기 때문에

    여러번 반복해야 했는지도 모르겠다)


간단하게 텍스트로 그려보면 아래와 같다.

 - V1   V2 -             - V1 - V3 -
      X         ==>     
 - V3   V4 -             - V2 - V4 -

V1-V4 와 V2-V3 가 Cross 하면, V1 - V2 - V3 - V4 순서를 V1 - V3 - V2 - V4 순서로 바꾸는 것이다.

요것도 그리 어렵진 않다.


하지만 TSP 문제가 아닌 Graph에서 사용하려면... Cross Check 하는 방법이 있긴 한지 잘 모르겠다.

2-Opt 의 좀 더 일반적인 방법인, Lin–Kernighan heuristic 을 사용한다면 방법이 있는거 같다.

(이것도 사실 잘 모르겠다)


어쨌거나 이렇게 근사해 구하고 개선하는 방법으로 풀면,

좋은 시간에 좋은 해를 구할 수 있는걸로~.




-- 각주 --

  1. Complete Graph 란, 임의의 한 점에서 다른 점까지 모두 이어져 있는 Graph를 말한다. 예를들면 정오각형 안에 별이 그려져 있는 도형을 생각해보라. [본문으로]
  2. 어떤 Graph에서, 모든 점을 단 한번만 지나는 경로를 의미한다. 어떤 Graph에서 해밀턴 사이클이 존재하는지 여부를 묻는 문제는 NP-Complete 문제이다. [본문으로]
반응형

설정

트랙백

댓글