TigerCow.Door

안녕하세요 .문범우입니다.

이번 포스팅에서는 hackerrank의 The Grid Search 문제를 풀어보았습니다.

난이도는 Medium, rate는 약 75%입니다.

문제 개념이나 이해자체는 크게 어렵지 않다고 생각되나 몇가지 고려할 부분들이 존재합니다.


제가 중요시 생각한 점은,

먼저 탐색하고자 하는 P배열에 대해 그 첫번째 행이 G배열에서 존재할때만 실질적인 탐색문을 반복하는 것과

그 첫번째 행이 G배열의 특정행에서 반복하여 존재할 수 있기 때문에 인덱스를 고려해가며 탐색하는 것 입니다.


보다 자세한 설명은 코드에 주석으로 달아 놓았습니다.

궁금하시거나 코드를 보다 효율적으로 개선할 방법에 대해서는 댓글 및 카카오톡, 이메일을 통해 말씀해주시면 감사하겠습니다 :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
 
    // Complete the gridSearch function below.
    static String gridSearch(String[] G, String[] P) {
        // G를 입력배열, P를 목표배열이라 하겠음
        int G_width = G[0].length(); // 입력배열의 가로길이 -> 목표배열 한줄씩 탐색시 사용됨. 
        int G_height = G.length// 입력배열의 세로길이 -> 목표배열 탐색 중에 입력배열의 높이를 넘어가면 NO를 반환
        int P_width = P[0].length(); // 목표배열의 가로길이
        int P_height = P.length// 목표배열의 세로길이 -> 목표배열 탐색 중에 목표배열의 높이를 넘어가면 YES를 반환
        int start_num = -1
        // 탐색중인 목표배열의 1 행이 13일떄, 입력배열에 01300130 과 같이 중복되서 나타날 수 있음
        // 이때 입력배열의 한줄에 대해 각각 검사하기 위해 사용하기도 하며
        // 목표배열의 1행이 위와 같이 13이고, 2행이 27일때, 입력배열이 다음과 같을 수 있음
        // 01300130
        // 99992799
        // 이러한 경우를 위해 각 입력배열의 각줄에 목표배열의 행이 포함되는지 여부뿐아니라,
        // 그 시작 인덱스가 일치하는지 알아야 하기 때문에 이때 start_num이 사용됨
        int count_from = -1;
        int count = 0;
        // count_from과 count변수는 입력배열의 탐색하고자 하는 목표배열의 행에 대해
        // 입력배열의 한 행에 몇개나 같은 문자열이 포함되어있는지를 저장함.
        // 즉, 위와 같이 01300130 같은 경우 count가 2가 되어서
        // 각각에 대해서 탐색을 진행해야 하기 때문에 탐색문을 2번 실행하게함
        for(int j=0;j<G_height;j++){ // 입력배열의 한 행씩 탐색을 진행함
            if(G[j].contains(P[0])){ // 어찌되었는 목표배열의 첫번째 행이 입력배열에 존재할때 탐색을 시작해야함
                count = 0
                start_num = -1;
                // count와 start_num 초기화, count_from은 아래 while문을 통해서 자동적으로 초기화가 됨
                while((count_from = G[j].indexOf(P[0], count_from + 1))>=0){
                    // G[j]에 P[0]가 어느 인덱스에서 시작되는지 확인, 이때 그 뒤에 count_from+1 인자를 줌으로써
                    // G[j]의 count_from+1 인덱스 이후로 부터 확인을 하는 것,
                    // 존재한다면 양수값을 주기때문에 count 값을 하나 증가,
                    // 존재하지 않는다면 -1을 반환하므로 count_from이 초기화 되는 기능이 됨
                    count++;
                }
                // 실질적인 탐색문 시작
                for(int i=0;i<count;i++){
                    start_num = G[j].indexOf(P[0], start_num+1); // G[j]에서 P[0]가 포함된 인덱스를 구함
                    for(int k=0;k<P_height;k++){ // 이제 모든 목표배열행에 대해 탐색할 것
                        if((G[j+k].contains(P[k]))&(start_num == G[j+k].indexOf(P[k],start_num))){
                            // 목표배열의 다음행이 입력배열의 다음행에 포함되어있는지 확인하면서
                            // 그 시작위치가 동일한지 확인 -> else: 즉, 그게 아니면 목표배열의 첫행에 대해 재탐색
                            if(k+1 == P_height){
                                // k가 증가하다가 목표배열의 높이를 넘어가면 모든 목표배열에 대해 탐색이 된 것이므로
                                // YES를 반환
                                return "YES";
                            }else if(j+k+1 == G_height){
                                // k가 증가하다가 목표배열의 높이를 넘어가기 전에 입력배열의 높이를 넘어가면
                                // 입력배열에 목표배열이 완전하게 존재하지 않는 것이기 때문에 NO를 반환
                                return "NO";
                            }
                        }else{
                            break;
                        }
                    }
                }
            }
        } // 해당 for문이 끝난 것은 입력배열에 목표배열이 포함되어 있지 않다는 뜻이기에 NO를 반환함
        return "NO";
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        for (int tItr = 0; tItr < t; tItr++) {
            String[] RC = scanner.nextLine().split(" ");
 
            int R = Integer.parseInt(RC[0]);
 
            int C = Integer.parseInt(RC[1]);
 
            String[] G = new String[R];
 
            for (int i = 0; i < R; i++) {
                String GItem = scanner.nextLine();
                G[i] = GItem;
            }
 
            String[] rc = scanner.nextLine().split(" ");
 
            int r = Integer.parseInt(rc[0]);
 
            int c = Integer.parseInt(rc[1]);
 
            String[] P = new String[r];
 
            for (int i = 0; i < r; i++) {
                String PItem = scanner.nextLine();
                P[i] = PItem;
            }
 
            String result = gridSearch(G, P);
 
            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 
cs


'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (1) 2018.07.12
블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc


안녕하세요.

이번 포스팅 부터 약 2-3회에 걸쳐 그리디 알고리즘(greedy algorithm)에 대해서 알아보겠습니다.

내용에 대해 궁금한 점이나 피드백은 언제든지 댓글을 남겨주세요 :)


1. 그리디 알고리즘(Greedy algorithm)


우리는 지난 포스팅에서 동적 프로그래밍(Dynamic programming)에 대해서 알아 보았습니다.

단순히 모든 경우에 대해서 반복적으로 재귀호출을 통해서 탐색을 하는 Brute force의 방식보다, 각각의 경우에 대해 테이블을 만들어 필요할 때마다 테이블 값을 이용하는 동적 프로그래밍은 보다 좋은 시간복잡도를 나타냈습니다.

하지만, 어찌되었든 간에 동적 프로그래밍 또한 탐색에 있어서 모든 경우에 대해서 탐색을 진행합니다. 이는 결국 필요하지 않은 케이스조차 검색하는 비효율적인 면을 갖고 있습니다.

헌데 어떤 문제들에서는 더 간단하고 보다 효율적인 알고리즘으로도 탐색을 할 수 있습니다.


일반적으로, 최적화 문제에서는 각 단계마다 여러 가지 경우 중에서 좋은 것을 택해야 합니다. 이러한 최적화 문제에서 동적 프로그래밍을 사용한다면 지나치게 많은 탐색을 하게 될 수 있습니다.

따라서 우리는 탐욕 알고리즘, 그리디 알고리즘을 사용합니다.

그리디 알고리즘(Greedy algorithm)은 각 단계에 있어서 가장 좋은 것을 선택합니다. 그리고 그러한 선택은 전체적으로 최적해로 안내하게 될거라는 바람에서 지속됩니다.

우리는 앞으로 그리디 알고리즘이 최적해를 제공할 수 있는 최적화 문제에 대해 알아볼 것입니다.


그리디 알고리즘이 언제나 최적의 해답을 구하지는 못하지만 많은 문제에 대한 해를 보다 효율적으로 구해낼 수 있습니다.



2. 활동 선택 문제(Activity Selection Problem)


활동 선택 문제란, 예를 들어, 한번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할 수 있는 스케줄을 짜는 문제입니다.



영어로 나와있는 바와 같이 문제를 가정하고 진행합니다.

특정 활동 ai가 있으며, si는 활동의 시작시간, fi는 활동이 끝나는 시간입니다. 그리고 ai, aj 활동이 각각 존재할 때, 두 활동의 활동시간이 서로 겹치면 안됩니다.

추가적으로, 주어지는 활동들은 끝나는 시간이 단조 증가하는 형태로 정렬된 상태입니다.


이제 아래의 활동들을 바탕으로 활동 집합을 고려해 보겠습니다.



위의 테이블을 보았을 때, a3, a9, a11은 함께 스케줄로 짤 수 있는, 즉 양립할 수 있는 활동들 입니다.

하지만 a1, a4, a8, a11 이라는 집합도 양립 가능하며 이러한 집합이 크기가 더 크기 때문에 최대 크기의 부분집합은 a1, a4, a8, a11이 됩니다.


이제 이러한 문제를 단계에 거쳐가며 탐색해보도록 하겠습니다.



3. 활동 선택 문제의 최적 부분 구조



활동 ai가 종료한 후에 시작하고, 활동 aj가 시작하기 전에 종료하는 활동들의 집합을 Sij로 나타냅니다.

Sij에 들어 있는 상호 양립 가능한 최대 크기의 집합을 찾기를 원하며, 그러한 최대 크기의 집합은 활동 ak를 포합하는 Aij라고 가정하겠습니다.

최적해 Aij에 ak를 포함하면 결국 두개의 부분 문제가 남게 됩니다. 하나는 Sik이며 다른 하나는 Skj입니다.

그렇다면, Aik = Aij  Sik이고 Akj = Aij  Skj 입니다. 이렇게 하면 Aik는 Aij에서 ak가  시작하기 전에 끝나는 활동들을 포함하고 Akj는 Aij에서 ak가 끝난 후에 시작하는 활동들을 포함하게 됩니다. 따라서 Aij = Aik U {ak} U Akj이고 Sij에 들어 있는 상호 양립 가능한 활동들의 최대 크기 집합 Aij는 |Aij| = |Aik| + |Akj| + 1 개의 활동들로 이루어 집니다.


이런 방식의 최적 부부 구조는 활동 선택 문제를 동적 프로그래밍을 사용해 풀수도 있음을 보여줍니다. 만약 집합 Sij를 위한 최적해의 크기를 c[i,j]로 나타낸다면, 다음과 같은 재귀방정식을 가지게 됩니다.



하지만 앞서 말한바와 같이 이러한 동적 프로그래밍 방식은 모든 부분 문제를 풀어봐야 한다는 단점이 있습니다.



4. 그리디 선택하기


활동 선택 문제에 있어서 그리디 선택을 한다는 것은 무엇을 의미할까요?

아마, 가능한 활동시간 내에서 최대한 많은 활동을 할 수 있도록 활동들의 집합을 고르는 것을 의미할 것 입니다.

위에서 동적 프로그래밍 방식은 모든 부분 문제를 풀어봐야 한다는 단점을 언급하였습니다. 그렇다면 그리디 선택은 어떤 장점을 가질까요? 

그리디 선택은 처음 개요에서 설명드렸듯이, 동적 프로그래밍에서 필요하지 않은 케이스 조차 탐색하는 불필요한 탐색시간을 없애고, 각 단계에서 최적의 선택을 함으로써 시간적으로 효율적인 것을 볼 수 있습니다.


그렇다면 활동 선택 문제에서의 그리디 선택은 어떻게 될까요?

바로, 제일 먼저 종료되는 활동을 선택하고, 해당 활동과 양립할 수 있는 활동들의 subproblem에서 또 다시 제일 먼저 종료되는 활동을 선택합니다. 이런식으로 반복하면 최대한 많은 활동들을 선택할 수 있습니다.

왜 그렇게 될까요? 간단하게 말해서, 제일먼저 끝나는 활동을 선택했을 때, 남은 subproblem에서 최대한 많은 활동을 고를 수 있기 때문입니다.


이러한 그리디 선택은 다음 그림에서 확인할 수 있습니다.




이러한 그리디 알고리즘을 수도 코드로 나타내면 다음과 같습니다.


먼저, 재귀적 그리디 알고리즘 입니다.


주어진 수도코드를 분석해보면, 전체 시간복잡도는 O(n)으로써 동적 프로그래밍에 비해 효율적인 탐색시간을 나타냅니다.


그리고 이번에는 반복 순환 그리디 알고리즘 입니다.


해당 수도코드의 시간복잡도 또한 O(n)입니다.



추가적으로 궁금한 사항이나 내용에 대한 피드백은 언제든지 댓글을 이용해주세요:)

블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc


안녕하세요. 이번 포스팅에서는 동적 프로그래밍(Dynamic Programming)에서의 최적 이진 검색 트리(Optimal Binary Search Tree)에 대해서 알아보겠습니다.


1. 최적 이진 검색 트리 (Optimal Binary Search Tree)


최적 이진 검색트리를 보다 쉽게 이해하기 위해서 상황을 가정하며 설명드리겠습니다.

특정 문서에 중복이 허용된 여러개의 영어단어가 존재하는데 이를 한글로 번역해서 저장하는 프로그램을 필요로 한다고 가정합니다. 그렇다면 프로그램은 이를 수행하기 위해서 문서에 있는 각각의 영어단어에 접근하고, 이에 해당하는 한글 단어를 찾아야 합니다. n개의 영어 단어가 존재한다고 했을 때, 어떻게 해야 이를 효율적으로 수행하는 프로그램을 작성할 수 있을까요?


바로 이럴 때 사용될 수 있는 것이 이진 검색 트리입니다.

위의 상황을 생각하면 이때 이진 검색트리에서는 하나의 노드에 영어 단어에 해당하는 key와 그에 해당하는 한글데이터가 존재할 것 입니다. 문서에 있는 하나의 영어 단어 각각에 대해서 트리를 한번 검색해야 하므로 우리는 트리의 높이가 비슷하게 균형잡힌 이진 트리 검색을 이용한다면 단어 하나당 O(lg n)의 검색 시간을 보장할 수 있습니다.

그러나 이것이 과연 최적의 이진 트리일까요?

가정된 상황을 다시 살펴보면 영어 단어는 '중복'될 수 있다고 하였습니다. 즉, 특정 단어에 대해서는 빈번히 검색이 진행될 것이고 다른 단어에서는 검색이 거의 사용되지 않을 것 입니다.

이러한 상황에서 우리는 최적 이진 검색 트리(Optimal Binary Search Tree)를 사용할 수 있습니다.


최적 이진 검색 트리에서는, n개의 서로 다른 키 K = <k1, k2, ... , kn>이 오름차순으로 정렬된 상태로 주어지며 이러한 키를 바탕으로 이진 검색 트리가 구성됩니다. 그리고 각 키 ki에 대해 검색이 일어날 확률 pi또한 함께 존재합니다. 

추가적으로, 우리는 어떤 단어 K에 대해서 탐색이 되지 않을 경우도 고려해야 합니다. 따라서 가상키라는 개념을 통해 이를 해결합니다. 가상키는 이진 검색 트리의 리프 노드로 배치될 것이며 특정 단어 K가 어떤 키 ki를 발견하지 못하면 가상키를 발견하게 될 것이고 이는 단어에 대한 해석을 찾지 못한 것으로 판단할 수 있습니다.

이러한 가상키는 n개의 노드를 가지는 이진 검색 트리의 리프노드들이므로 총 n+1개이며 d0는 k1보다 작은 모든 값을 나타내고 dn은 kn보다 큰 모든 값을 나타냅니다.


아래 사진을 보면 두개의 이진 검색 트리를 확인할 수 있습니다.



그림 아래에 존재하는 표는 각각의 항목이 일어날(검색될) 확률을 의미합니다.

Search Cost의 계산은 각 항목의 탐색시간(방문하는 노드수 = 깊이+1) * 확률의 총합이라고 하겠습니다. 

먼저 첫번째 (a)의 이진 검색 트리를 보면 비슷하게 균형 잡힌 것을 볼 수 있습니다. 이러한 이진검색트리의 Search Cost는 그림에서 나온것과 같이 2.80입니다.

그리고 두번째, (b)의 이진 검색트리의 Search Cost는 2.75로써 (a)보다 작은 것을 볼 수 있습니다.


이렇게, 최적 이진 검색 트리는 단순히 높이를 균형있게 하는 것이 아니라 탐색시간을 최소로 하여 최적의 탐색시간을 갖도록 하는 것입니다.

일반적으로 최적 이진 검색 트리는 다음과 같이 정의됩니다.



위에서 언급한 바와 같이, 모든 탐색에서 방문하는 노드들의 회수의 최소를 갖도록 하는 것입니다.



2. 최적 이진 검색 트리의 최적 부분 구조



최적 이진 검색 트리의 최적 부분 구조를 찾기 위하여 부분 구조를 살펴보겠습니다.

어떤 이진 검색 트리의 서브 트리를 고려하면, 그 부분 구조는 1<= i <= j <= n에 대해 연속하는 범위 ki, ... , kj에 해당하는 키를 포함해야 합니다. 그리고 키 ki, ... , kj를 포함하는 서브트리는 그 해당 가상키 di-1, ... , dj도 포함해야 합니다.


이제 최적 이진 검색트리의 최적 부분 구조에 대해서 알아보겠습니다.

최적 이진 검색 트리 T가 있을 때, 키 ki, ... , kj를 포함하는 서브 트리 T'을 가진다면 이 서브 트리 T'은 키 ki, ... , kj와 가상 키 di-1, ... , dj를 가지는 부분 문제에 대해서도 최적이어야 합니다.

이러한 주장을 증명하기 위해서 cut&paste 방법을 적용합니다. T'보다 기댓값이 작은 서브 트리 T''이 존재한다고 가정합니다. 이때 T'을 잘라내고 그 자리에 T''을 붙여 넣으면 T보다 기댓값이 작은 이진 검색 트리가 나타나게 되고 이것은 T가 최적이라는 가정에 모순입니다.



그럼 이제 이러한 최적 부분 구조를 사용해서, 부분 문제에 대한 최적해를 구함으로써 주어진 문제에 대한 최적해를 구할 수 있음을 보여야 합니다.



위의 그림처럼 루트가 kr이고 키 ki, ... , kj를 갖는 최적 서브 트리가 있다고 합시다.(i <= r <= j)

그렇다면 아래 그림과 같이, 루트 kr의 왼쪽 서브 트리키는 ki, ... kr-1과 가상키 di-1, ... , dr-1를 포함할 것이며 오른쪽 서브 트리는 키 kr+1, ... , kj와 가상키 dr, ... , dj를 포함합니다. 이때 루트 kr에 대해 i부터 j까지의 모든 후보 루트 ki, ... , kj를 고려하면서 왼쪽 서브 트리로 ki, ... , kr-1를 포함하며 오른쪽 서브 트리로 kr, ... , kj를 포함하는 모든 최적 이진 검색트리를 검색하면 최적의 이진 검색 트리를 발견할 수 있습니다.



이때 만약 서브 트리의 루트를 ki로 선택한다면 왼쪽 서브 트리는 ki, ... ki-1을 포함합니다. 즉, 왼쪽 서브 트리는 어떤 키도 갖지 않는 빈 서브 트리가 됩니다. 그러나 왼쪽 서브 트리가 아무것도 갖지 않는 것은 아닙니다. 바로 가상키를 갖기 때문이죠. 왼쪽 서브 트리는 di-1, ... dr-1 의 가상키를 갖는다고 했으니, 루트가 ki인 서브 트리의 왼쪽 서브 트리는 di-1이라는 하나의 가상키만을 갖게 됩니다. 이것은 kj를 서브 트리의 루트로 잡았을때 오른쪽 서브트리에서 갖은 상황이 발생합니다.



3. 재귀해


이제 재귀적으로 최적해의 값을 찾을 준비가 되었습니다.

i >= 1, j <= n, j >= i-1 인 키 ki, ... , kj를 포함하는 최적 이진 검색 트리를 찾는 것으로 부분 문제의 범위를 정합니다.

위에서 언급한 바와 같이 j=i-1 일때는 실제키가 없고 가상키 di-1만 가지게 됩니다.

그리고 키 ki, ... , kj를 포함하는 최적 이진 검색 트리를 찾는 기대비용을 e[i,j]로 정의하도록 하겠습니다.

결국 우리의 목표는 e[i,n]을 찾는 것입니다.


먼저, 우리는 j=i-1에 대해서 값을 쉽게 찾을 수 있습니다. 가상키 di-1만 존재하므로 기대 검색 비용, e[i,i-1] = qi-1 입니다.

이제 j >= i 일 때에 대해서 생각합니다. ki, ... , kj 중에서 루트 kr을 선택해야 하며 왼쪽 서브 트리가 최적 이진 검색트리가 되어야 하며 오른쪽 서브 트리 또한 최적 이진 검색트리가 되어야 합니다. 

이때 고려할 점이 있습니다. 만약 트리 T가 존재할 때 이 트리가 어떤 루트 N에 대해서 서브 트리가 된다면 T라는 트리의 검색비용에는 무슨 일이 벌어질까요? T 트리에 있는 모드의 깊이가 모드 1씩 증가하므로 T 트리의 검색 비용은 모든 노드들이 검색될 확률의 총합만큼 증가하게 됩니다.

그럼 점화식을 한번 알아보도록 하겠습니다. 



먼저 위의 그림에서,



이것은, ki, ... ,kj 의 키를 가진 서브 트리의 모든 확률의 합을 나타냅니다.

이를 통해 점화 식을 한번 세워보면, 위의 그림의 첫번째 식인,

e[i,j] = pr + (e[i,r-1] + w(i,r-1)) + (e[r+1,j] + w(r+1,j)) 이 나오게 됩니다.

식에서 의미하는 바를 그림으로 알아보겠습니다.



먼저 식에서 첫번째 인자인 pr은 위의 그림에 있는 트리의 루트가 검색될 확률을 의미합니다.

루트의 깊이는 0이므로 검색이 실행될때 pr*1만큼의 검색비용이 필요합니다.

그리고 e[i,r-1]은 왼쪽 서브트리, 그림에서 초록색을 가진 서브트리에 대한 검색비용을 의미합니다.

w(i,r-1)은 왼쪽 서브트리의 깊이가 1만큼 증가했으므로 그에 대해 왼쪽 서브트리의 모든 노드들의 확률의 합을 의미합니다. 그림에서는 빨간색 선으로 생각하시면 되겠습니다.

마찬가지로, e[r+1,j]는 그림에서 주황색테두리를 가진 서브트리를 의미하며, w(r+1,j)는 그림에서 파란색 선을 의미합니다.


위의 점화식을 보다 간단하게 하기 위해

w(i,j) = w(i,r-1) + pr + w(r+1,j)

라는 사실을 이용합니다.

그러면 위의 점화식은

e[i,j] = e[i,r-1] + e[r+1,j] + w(i,j)

가 됩니다.


그리고 r을 범위내 모든 값에 대해 탐색을 진행하고 그 중 최소의 검색 비용을 갖는 r을 찾아야 하므로 최종적인 점화식은 아래와 같습니다.




4. 알고리즘


먼저 Optimal BST를 구하기 위한 수도코드는 아래와 같습니다.



동적 프로그래밍을 이용하여 보다 효율적으로 탐색을 진행하기 위해 수도코드에서는 총 3개의 테이블을 사용합니다.

그리고 앞에서 이야기 했던 것처럼 e값을 재귀적으로 도출하면서 최종적인 목표에 도달하게 됩니다.


글의 서두에서 보여드렸던 키들을 이용하여 Optimal BST으로 계산하면 아래와 같은 테이블이 생성됩니다.


이러한 Optimal BST의 총 시간 복잡도는 O(n^3)입니다.


이렇게 하여 최적 이진 검색 트리(Optimal Binary Search Tree)에 대해서 알아보았습니다.

추가적인 궁금사항이나 내용에 대한 피드백은 댓글을 이용해주세요 :)



블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc


안녕하세요.

이번 포스팅에서는 최장 공통 부분 수열(LCS: Longest Common Subsequence)에 대해서 알아보도록 하겠습니다.

궁금하신 점이나 내용에 대한 피드백은 댓글을 이용해주세요 :)


1. 최장 공통 부분 수열

(LCS: Longest Common Subsequence)


먼저 최장 공통 부분 수열이 어떠한 것인지 알아보도록 하겠습니다.

문제를 이해하기 위해 다음을 가정합니다.


X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>


이러한 두 수열 X, Y가 있습니다. 이때, <ABD>는 X와 Y의 공통 부분 수열입니다.

X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>

위에서 X 수열과 Y 수열에 밑줄을 쳐놓은 부분을 통해 <ABD>는 X와 Y의 공통 부분 수열이라는 것을 알 수 있습니다.
꼭 연결되어 있어야 하는 것이 아니며, 단지 단조 증가하는 수열로써 존재하면 되는 것이죠.
그렇다면 최장 공통 부분 수열이란 무엇일까요?
바로 위에서 알아본 <ABD>와 같은 공통 부분 수열들 중에서, 가장 길이가 긴 것을 말합니다.
X, Y수열을 살펴보면 <ABD>를 제외하고도 <ABCD>와 같은 공통 부분 수열도 있습니다.
물론 하나의 공통부분 수열만 존재할 수도 있지만 2개 이상의 공통 부분 수열을 가질 수도 있습니다.
그러한 공통 부분 수열들 중에서 가장 길이가 긴 것을 우리는 최장 공통 부분 수열(LCS)라고 말합니다.
위의 X, Y수열에서는 아래 밑줄 친 것과 같이 <ADABCDCC> 가 가장 긴 공통 부분 수열, 최장 공통 부분 수열 입니다.

X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>



2. 최장 공통 부분 수열의 최적 구조


우리는 앞에서 동적 프로그래밍의 최적 구조를 살펴보았습니다.

그럼 지금 알아보고 있는 LCS의 최적 구조는 어떻게 될까요? 바로 다음과 같습니다.




3. 최장 공통 부분 수열의 길이 구하기


그럼 이제 본격적으로, 최장 공통 부분 수열의 문제를 풀어보도록 합니다.

우리가 최종적으로 구해낼 것은 두 수열 X, Y가 있을 때 두 수열의 최장 공통 부분 수열의 길이입니다.


먼저 X의 i번째 문자열과 Y의 j번째 문자열까지의 최장 공통 부분 수열의 길이를 c[i,j]라고 가정합니다.



위의 내용을 하나씩 확인해보도록 하겠습니다.


3-1. i=0 or j=0

두 수열 중 하나의 수열의 길이가 0 이라면, 최장 공통 부분 수열의 길이도 0입니다. 서로 일치하는 문자가 전혀 존재할 수 없기 때문이죠.


3-2. i,j>0 and Xi = Yi

i,j가 양수인 것은 당연합니다. 문자열을 거꾸로 확인하지는 않을테니까요.

양수인 i,j에 대해서 Xi와 Yj가 서로 일치한다면 해당 문자는 최장 공통 부분 수열에 포함되는 문자일 것 입니다.

따라서 해당 문자를 제외한 나머지 문자열에서 LCS를 탐색하게 되고, 최종적으로 반환이 될때는 제외한 문자가 최장 공통 부분 수열에 포함되므로 +1을 합니다.


3-3. i,j>0 and Xi != Yi

양수인 i,j에 대해서 Xi와 Yj가 서로 일치하지 않다면, 각각의 수열에서 하나씩 제거해서 LCS를 탐색합니다.

Xi와 Yj가 서로 일치하지 않을 때는 각각의 수열에서 마지막 문자를 제거한, c[i,j-1] 또는 c[i-1,j] 둘 중 하나가 최장 공통 부분 수열을 포함하고 있을 것입니다. 



4. 테이블 그리기


그럼 위에서 알아본 방법으로 LCS를 어떻게 구할까요?

바로 아래와 같은 테이블을 통해서 LCS를 구합니다.


 

j

0

1

2

3

4

5

6

i

 

Yi

B

D

C

A

B

A

0

Xi

0

0

0

0

0

0

0

1

A

0

 

 

 

 

 

 

2

B

0

 

 

 

 

 

 

3

C

0

 

 

 

 

 

 

4

B

0

 

 

 

 

 

 

5

D

0

 

 

 

 

 

 

6

A

0

 

 

 

 

 

 

7

B

0

 

 

 

 

 

 



먼저 X수열은 <ABCBDAB>이며 Y수열은 <BDCABA>라고 가정합니다.

테이블의 첫번째 열과 첫번째 행은 i또는 j가 0이므로 모두 0으로 채우도록합니다.

그리고 하나의 칸씩 채워보도록 하는데 이후 LCS의 길이뿐 아니라 그 수열까지 함께 구할 수 있도록 화살표를 함께 사용합니다.


각각에 대해서 탐색을 할때는 다음과 같은 방법을 이용합니다.

ㄱ) 두 문자가 같을 때, 좌측위에 있는 숫자에 1을 더한 값을 가지며 화살표는 좌측위를 가리킵니다.

ㄴ) 두 문자가 다를 때, 좌측이나 위에 있는 숫자중 큰 값을 가리키며 같은 값을 가집니다. 동일한 값일 때는 위의 값에 대해 행동합니다.


먼저, i가 1일때 1부터 6까지의 j에 대해 확인합니다.

X1는 A이며 Y1은 B이기 때문에 두 문자가 서로 다르고, 좌측과 위에 있는 숫자가 같은 값을 가지기에 그 값을 가지며 위를 가리킵니다.

X1과 Y2도 같은 방식이고, X1과 Y3 또한 같은 방식입니다.

X1과 Y4를 보시면 서로 같은 문자, A를 가지고 있습니다. 따라서 대각(좌측상단) 방향의 값보다 1큰 값인 1을 값으로 가지며 대각을 화살표로 가리킵니다.

이러한 방법으로 모든 칸을 채우면 아래와 같이 채워지게 됩니다.




따라서 LCS의 길이는 4이며 LCS수열을 구하고 싶다면 제일 좌측 하단에서부터 시작해 화살표 방향으로 따라가며 대각선방향을 가리키는 부분의 문자를 나열하면 됩니다.


이렇게 해서 최장 공통 부분 수열(LCS: Longest Common Subsequence)에 대해서 알아보았습니다.

추후 시간이 된다면 LCS알고리즘을 파이썬으로 직접 구현하여 테스트 해보도록 하겠습니다.


블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.


정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.



입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 자연수 N이 주어진다.


출력

첫째 줄에 연산을 하는 횟수의 최소값을 출력한다.



예제 입력 : 2

예제 출력 : 1


예제 입력2 : 10

예제 출력2 : 3



처음에는 알고리즘을 단순하게 생각했다가 바로 틀려버린 문제입니다.

먼저 최종 정답으로 통과한 코드는 아래와 같습니다.


정답 코드



처음에는 단순히 반복문과 조건문을 이용해서 문제를 풀었습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
= int(input())
count = 0
 
while True:
    if a==1:
        print(count)
        break
    
    if a%3 == 0:
        a = a/3
    elif a%2 == 0:
        a = a/2
    else:
        a = a-1
    count = count + 1
cs


이렇게 해서 풀었더니 가차 없이 틀리더군요..

뭐가 틀렸을까 고민해보다가 예제입력2로 주어진 10이라는 숫자가 보였습니다.

처음에 작성한 코드에 10을 입력하면 count는 4로 출력됩니다.

하지만 문제에서 최소한의 연산을 이용하라고 했음에 유의해야합니다.

위의 코드대로라면 10 -> 5 -> 4 -> 2 -> 2 순서로 연산이 되어 연산 회수는 총 4번입니다.

하지만, 10에서 2로 나누지 않고 1을 빼는 연산을 우선으로 한다면?

10 -> 9 -> 3 -> 1 순서로 연산이 진행되어 연산 회수는 총 3번입니다.


이러한 결과를 도출하기 위해 고민했습니다.

연산에 우선순위를 두는 것은 소용이 없습니다.

10이라는 입력에 대해 올바른 출력을 위해 1을 빼는 것을 우선 순위로 처리한다면?

6이라는 숫자를 입력했을때, 6 -> 3 -> 1 의 순서가 아닌, 6 -> 5 -> 4 -> 2 -> 1 의 순서로 연산이 될 것 입니다.

그렇다면, 입력한 숫자로 세가지 연산을 모두 수행하여(1,2번 연산은 가능할 때만) 그 결과 값을 리스트로 저장하고, 그 리스트안에 있는 각각의 숫자들을 다시 세가지 연산 모두를 수행하도록 하고, 각 루프 한번당 count를 1씩 증가시키면 어떨까요?


정리해본다면, 세가지 연산을 모두 처리하는 함수 cal()을 만들어서 cal()함수를 재귀적으로 호출하는 방법입니다.


그래서 처음에 언급한 코드를 구현하게 되었습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
= int(input())
count = 0
minimum=[a]
def cal(a):
    list = []
    for i in a:
        list.append(i-1)
        if i%3 == 0:
            list.append(i/3)
        if i%2 == 0:
            list.append(i/2)
    return list
 
while True:
    if a == 1:
        print(count)
        break
    temp = minimum[:]
    minimum = []
    minimum = cal(temp)
    count +=1
    if min(minimum) == 1:
        print(count)
        break
cs


위의 코드를 보시면, 처음에 minimum이라는 리스트를 선언하고 초기값으로 입력값을 넣습니다.

그리고 4번 라인부터 12번 라인까지는 3가지 연산을 수행하고 그 결과값을 배열로써 반환하는 함수입니다.

15번에서 입력값이 1일때를 처리하고, 이후 minimum배열을 복사해서 temp 배열을 구성하고, minimum 배열은 다시 비우도록 합니다. 단순히 하나의 배열에 계속 넣게되면 메모리 초과가 될까봐 이런식으로 구현하였습니다.

그리고 temp를 cal()함수의 인자로 넣어 연산을 수행하고, 그 결과값 배열을 minimum으로 받습니다.

그리고 연산 count를 1 증가시키고, minimum에 있는 값중 최소값이 1일때 count값을 출력하며 반복문을 마무리하도록 합니다.


블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc



안녕하세요. 문범우입니다.

이번 포스팅부터 Introduction to Algorithm (3rd Edition) 책의 15장. 동적 프로그래밍(ch15, dynamic programming)에 대해서 이야기하려 합니다.

매주 1~2번 정도 포스팅 될 예정이며, 공부를 하면서 내용을 정리해서 올리기 때문에 잘못된 정보나 지식이 포함되어 있을 수 있으니 참고용으로 확인해주시고, 잘못된 내용에 대해서는 피드백 주시면 감사하겠습니다.

오늘은 동적 프로그래밍에 대한 개요와 동적 프로그래밍의 막대 자르기(Rod Cut)에 대해서 알아보겠습니다.


1. 동적 프로그래밍(Dynamic programming)


동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합하여 문제를 해결합니다.

이때, 프로그래밍이란 것은 코딩을 하는 것이 아니라 테이블을 이용하여 문제를 해결하는 방법을 말합니다.

동적 프로그래밍은, 동적 계획법, Dynamic programming, DP 등으로 부르기도 합니다.


분할정복 알고리즘은 기본적으로, 하나의 문제를 겹치지 않는 부분 문제들로 분할(divide)하여 해당 부분 문제들을 재귀적으로 해결한 후, 각각의 결과를 다시 결합하여 원래의 문제를 해결합니다.

반면, 동적 프로그래밍에서는 부분 문제가 서로 중복될 떄, 즉 부분 문제가 다시 부분 문제를 공유할 때 적용됩니다.

동적 프로그래밍 알고리즘을 이용하여 부분 문제를 한번만 해결하고 그 해를 테이블에 저장함으로써 각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있습니다.


일반적으로 최적화 문제(Optimization problem)에서 동적 프로그래밍을 적용합니다.

최적화 문제에서는 대체적으로 다양한 해를 가질 수 있는데 우리는 다양한 해들 중에서 최적(최소 또는 최대)의 해를 찾기를 원합니다. 이러한 해를 그 문제에 대한 유일한 최적해라고 하지 않고, 한 개의 최적해라 합니다. 최적의 값을 가지는 해가 여러개 존재할 수 있기 때문이죠.

동적 프로그래밍 알고리즘을 개발할 때는 아래의 4단계를 따릅니다.


1. 최적해의 구조의 특징을 찾는다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산한다.

4. 계산된 정보들로부터 최적해를 구성한다.


1~3 단계는 주어진 문제에 대한 동적 프로그래밍 해의 기초가 됩니다.

이어서 4 단계에서는 최적해의 값만 필요한 것이 아니라 최적해 자체가 필요할 때 수행하는 것으로써 값만 필요할때에는 생략할 수 있습니다.


2. 막대 자르기


막대 자르기 문제는 다음과 같습니다.

길이가 n인 막대와 i = 1,2,3,...,n에 대한 가격 p_i의 표가 주어지면 해당 막대를 잘라서 판매했을떄 얻을 수 있는 최대수익 r_n을 결정하는 것 입니다. 길이가 n인 막대의 가격 p_n이 충분히 비싸면 최적해는 자르지 않은 것일 수도 있습니다.


아래 표와 그림을 통해 확인해보겠습니다.


표에는 막대의 길이가 얼마일 때, 얼마의 가격인지가 나와 있습니다.

그리고 아래 그림에서 막대를 다양한 방법으로 잘라, 그 가격을 나타내고 있습니다.

(a) ~ (h)를 봤을 때 어떤 경우가 최적의 해 인가요?

막대를 2의 길이, 두 개로 자른 (c)의 경우의 수익이 10으로써 가장 최적의 해를 나타내고 있습니다.


위와 같이, 길이가 n인 막대는 개의 다른 방법으로 자를 수 있습니다.

제일 좌측에서 부터 i = 1,2,3,...,n-1 에 대한 모든 i길이마다 자르거나 자르지 않거나 하는 독립적인 선택이 가능하기 때문입니다.

만약 최적해가 막대를 에 대해 k의 조각으로 나누면,

막대를 조각 길이 로 나누는 다음의 최적의 분해는

 이며,

다음과 같은 최대의 해당 수익을 제공합니다.


좀 더 일반적으로 말하면, 에 대한  값을 더 작은 막대로부터의 최대 수익을 이용해 나타낼 수 있습니다.



첫 번째 인자 은 자르지 않고 길이가 n인 막대를 그대로 파는 것에 해당합니다.()

max 함수에 대한 다른 인자는 막대를 처음에 i와 n-i의 길이가 되도록 둘로 나누고 두 조각을 더 최적으로 잘라서 두 조각으로부터 최적의 이익을 얻습니다. 그런데 어떤 i의 값이 최대의 수익을 가져오는지 미리 알 수 없기 때문에 i에 대한 모든 가능한 값을 고려해야 합니다.


다시말해서, 크기가 n인 원래 문제를 풀기 위해서 종류가 같은 더 작은 크기의 문제를 풉니다.

처음에 자르기를 진행하여 도출된 두 가지의 문제는 서로 독립적인 예로 생각해도 됩니다.

전체적인 최적해는 두 부분 문제의 각각에 대해 수익을 최대화하는 해를 이용합니다.

이에 따라 막대 자르기 문제는 최적 부분구조(Optimal substructure)를 가졌다고 말합니다.

따라서 길이가 n인 막대의 모든 분해를 첫 번째 조각과 나머지 조각의 어떤 분해로 볼 수 있습니다. 그렇게 할 때는 막대를 전혀 자르지 않는 방법의 해를 포함하여 좀 더 간단한, 아래와 같은 식을 얻을 수 있습니다.



우리는 위의 식을 토대로 몇 가지 알고리즘을 구현해보도록 하겠습니다.


2-1. 하향식 재귀의 표현


알고리즘의 의사코드는 아래와 같습니다.



위의 CUT-ROD 의사코드에 대해 간략히 확인해볼까요?

길이 n이 0인 막대기는 당연히 0을 반환합니다.

그리고 그것이 아닐때에, 최대 수익 q를 음의 무한대로 초기화를 진행하고 i가 1부터 n까지 값으로 재귀 함수를 호출합니다.

이러한 알고리즘의 총 수행시간은,

   

입니다.


CUT-ROD 알고리즘이 위와 같은 수행시간을 보이듯, 비효율적인 이유는 무엇일까요?

그것은 CUT-ROD 알고리즘이 같은 인자를 똑같이 반복해서 계산하려고 하기 때문입니다.

아래의 트리를 보면 이해하기 쉬울 것 입니다.

n=4 일때를 보여주는 위의 트리에서, 재귀적으로 호출되는 함수 때문에 n=1 일때, n=2일때의 경우가 반복되서 호출되고 있습니다. 

즉 CUT-ROD 함수에서는 길이가 n인 막대를 자르는 데 가능한 개의 경우의 수를 모두 고려하고 있는 것 입니다.



3. 동적 프로그래밍을 이용한 최적의 막대 자르기


이제 1에서 알아보았던 동적 프로그래밍을 이용하여 막대 자르기 문제를 효율적으로 해결해보록 하겠습니다.

동적 프로그래밍은 위에서 알아본 바와 같이, 각 부분 문제를 단 한번만 풀고 그 해를 저장하도록 처리합니다.

그렇게 함으로써 반복되는 부분 문제의 해를 구할 떄 다시 계산하지 않고 저장된 값을 참조만 함으로써 시간소요를 줄일 수 있습니다. 하지만 이렇게 동적 프로그래밍은 시간을 절약하기 위해 부가적인 메모리를 사용합니다.

이것은 시간-메모리 트레이드 오프(Time-memory trade-off)의 한가지 예로써 작용합니다.


막대자르기 문제를 동적 프로그래밍 방법으로 해결하는데 있어서 크게 두 가지 방법이 존재합니다.

하나는 메모하기를 이용한 하향식 방법, 다른 하나는 상향식 방법입니다.



3-1. 메모하기를 이용한 하향식


메모하기를 이용한 하향식의 기본 개념은 2-1에서 진행한 하향식 재귀와 비슷합니다.

하지만 특정 부분 문제를 해결하였을때 해당 부분 문제의 해를 배열이나 해시 테이블에 저장해놓도록 수정하여 이후 같은 부분 문제가 반복되었을때 다시 계산하지 않고 배열이나 해시 테이블을 참조하여 이용할 수 있도록 함으로써 시간을 절약합니다.

아래는 메모하기가 더해진 하향식 CUT-ROD 의 의사코드입니다.

메인 알고리즘, MEMOIZED-CUT-ROD는 새로운 배열 r[]을 선언하고 음의 무한대로 초기화 합니다.

배열 r의 구성은, 특정 길이 n'에 대한 최적의 해를 r[n']에 저장합니다.

그리고 길이 n에 대해서 MEMOIZED-CUT-ROD-AUX 함수가 호출이 됩니다.

그리고 1행에서 길이 n에 대한 최적의 해가 존재하다면 그것을 리턴하게 됩니다.

(초기에 배열 r[]을 음의 무한대로 초기화 하였으니 특정 길이 n'에 대하여 r[n']의 값이 0보다 크거나 같다면 길이 n'에 대한 최적의 해가 저장되어 있다는 것을 알 수 있습니다.)

계산되어 있지 않다면 이후 3행부터는 2-1에서 진행한 하향식 재귀함수와 동일합니다.



3-2. 상향식 방법


상향식 방법은 보다 간단합니다.

상향식 방법에서는 동적 프로그래밍 방법에서 부분 문제의 자연스러운 순서를 사용합니다.

만약 i > j 이라면 크기 i의 부분 문제는 크기 j 의 부분 문제보다 작습니다. 그러므로 해당 상향식 방법에서는 크기가 0부터 n으로 커지는 부분 문제의 크기 순으로 해결합니다.


수도코드의 1행에서 배열 r[]에 대해서 선언하고 이후 우리는 r[] 배열에 부분 문제의 결과를 저장할 것 입니다.

그리고 길이가 0인 막대에 대한 최대 수익은 0 이므로 2행에서 r[0]=0 으로 저장합니다.

3행에서부터는 길이가 1부터 j까지 하나씩 증가하는 각 부분 문제를 해결하여 값을 구하고 그것의 값을 7행에서 배열 r[]에 저장합니다.

마지막 8행에서 우리가 얻고자 하는 길이 n에 대한 최대 수익값을 리턴하게 됩니다.

이러한 상향식 방법의 수행시간은 을 가집니다.



3-3. 해의 재구성


우리가 위에서 공부한 두가지 알고리즘에서는 최적 해의 대한 값만 도출합니다.

즉, 길이가 n에 대한 막대를 통해 얻을 수 있는 최대 수익만을 반환할 뿐이지 해당 막대를 어떻게 잘라야 하는지는 리턴하지 않습니다.

이러한 동적 프로그래밍 방법을 각각의 부분 문제에 대한 계산된 최적 값 뿐만 아니라, 그 최적 값에 이르는 선택도 기록하도록 확장할 수 있습니다. 즉 이러한 정보와 함께 최적 값 뿐 아니라 최적해 자체를 쉽게 출력할 수 있습니다.



위의 수도코드에서는 그 전과 다르게 1행에서 배열 s[]를 선언합니다. 그리고 8행을 확인하시면 잘라내는 첫번째 조각의 최적크기 i를 보관하는 것을 알 수 있습니다.

그리고 최적 해를 가지는 r과 최적의 첫 번째 막대 크기들의 배열 s[]을 반환합니다.

아래 수도코드는 길이 n의 막대의 최적 분할에서의 모든 조각 크기의 리스트를 함께 출력합니다.





이렇게 해서 동적프로그래밍에 대한 개요와 하나의 예제인 막대 자르기(Rod-cutting) 에 대해서 공부해보았습니다.

추가적으로 궁금하신 점이나 피드백해주실 점은 댓글 또는 이메일(doorbw@outlook.com)을 이용해주세요 :)



블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

안녕하세요.

이번에는 python을 이용한 CSP algorithm 중 하나인 Einstein's puzzle(아인슈타인 퍼즐) 해결 코드를 작성해 보겠습니다.



먼저 아인슈타인 퍼즐에 대해 소개해 드릴게요.

아인슈타인의 퍼즐은 아래와 같은 문제입니다.


* 문제의 배경

1. 색깔이 서로 다른 5채의 집이 일렬로 지어져 있다.

2. 각 집에는 서로 다른 국적의 사람이 살고 있다.

3. 다섯 사람은 서로 다른 음료를 마시고, 서로 다른 담배를 피며, 서로 다른 동물을 기른다.


* 15개의 정보

1. 영국인은 빨간 집에서 산다.

2. 스웨덴인은 개를 기른다.

3. 덴마크인은 차를 마신다.

4. 초록집은 하얀집의 왼쪽 집이다.

5. 초록집에 사는 사람은 커피를 마신다.

6. 펠몰 담배를 피는 사람은 새를 기른다.

7. 노란집에 사는 사람은 던힐 담배를 피운다.

8. 한 가운데 집에 사는 사람은 우유를 마신다.

9. 노르웨이 인은 첫번째 집에 산다.

10. 블렌드 담배를 피우는 사람은 고양이를 기르는 사람 옆 집에 산다.

11. 말을 기르른 사람은 던힐 담배를 피우는 사람 옆 집에 산다.

12. 블루매스터 담배를 피는 사람은 맥주를 마신다.

13. 독일인은 프린스 담배를 피운다.

14. 노르웨이인은 파란 집 옆 집에 산다.

15. 블렌드 담배를 피우는 사람은 생수를 마시는 사람과 이웃이다.


위의 문제 배경과 15개의 정보가 있을때, '물고기를 기르는 사람의 국적은 무엇인가'?

(문제 출처: https://web.stanford.edu/~laurik/fsmbook/examples/Einstein%27sPuzzle.html)



이론적인 문제 풀이 방식은 아래와 같은 순서로 풀이가 가능합니다.

먼저 15개의 정보 중에서 확실히 알 수 있는 사실들을 이용한다. 15개의 정보 중에서 8, 9, 14번의 정보는 순서대로 하여 확실히 특정 사실을 알 수 있는 정보이다. 세가지 정보를 이용하면 위의 표와 같이 알 수 있다.


두번째로는 특정 조건들을 결합하여 이용한다. 먼저 4번 정보와 5번 정보를 이용하였다. 4번 정보를 통해 초록집은 하얀 집의 왼쪽 집임을 만족시켜야 한다. 4번 정보를 다르게 해석하면, 초록집의 오른쪽 집은 하얀 집이다. , 1, 2, 5번은 초록집이 될 수 없다. 그리고 5번 정보를 이용하면 초록 집은 3번이 될 수 없다. 따라서 남은 것은 4번뿐이므로 초록집은 4번이다. 또한 4번 집사람은 커피를 마시고 5번집은 하얀집이다. 다음 1번 정보를 확인하면, 2,4,5번 집은 이미 색이 있으므로 빨간집이 아니며 1번집은 노르웨이사람이 살고 있으므로 1번도 아니다. 3번 집이 빨간집이며 영국사람이 산다. 이어서 남은 1번은 자연스럽게 노란색 집이되며 7번 정보를 통해 1번집 사람은 던힐담배를 피운다. 또한 11번 정보를 통해 2번 집 사람은 말을 기른다.



이제 주어진 조건들을 응용하여 추리한다. 3번 정보와 12번 정보를 해석한다. 현재 남은 음료는 생수, , 맥주이다. 3번 정보에서 덴마크인이 차를 마신다고 하였으므로 노르웨이인은 생수 또는 맥주를 마실 것이다. 12번 정보에서 블루매스터 담배를 피우는 사람은 맥주를 마신다고 하였는데, 노르웨이인은 던힐 담배를 피우므로 맥주를 마시지 않는다. 즉 노르웨이인은 생수를 마신다. 또한 15번 정보를 통해서 2번 집 사람은 블렌드 담배를 피운다.

다시 12번 정보를 확인한다. 2번 집 사람은 차 또는 맥주를 마실 텐데 12번 정보에서 블루매스터 담배를 피는 사람이 맥주를 마신다고 하였다. 2번 집 사람은 블렌드 담배를 피우므로 맥주를 마시지 않고 차를 마신다. 그리고 남은 맥주는 당연히 5번 집 사람이 마시고, 5번 집 사람은 블루매스터 담배를 핀다. 이어서 3번 정보를 통해 차를 마시는 2번 집 사람은 덴마크인이다. 




마지막으로 남은 조건들로 추리를 완성한다. 먼저 13번 정보를 확인한다. 독일인은 4번 또는 5번집에 살텐데 5번 집 사람은 블루매스터 담배를 핀다. 따라서 13번 정보를 통해 독일인은 4번집에 살며 프린스 담배를 피운다. 이어서 5번집 사람은 스웨덴인이며, 3번집 사람은 펠몰담배를 핀다.

다음 6번 정보를 통해 펠몰담배를 피는 3번집 사람은 새를 기른다. 또한 2번 정보를 통해 5번 집에 사는 스웨덴인은 개를 기른다.

마지막으로 10번 정보를 통해서 3번 집사람은 이미 새를 키우는 것을 알았으므로 1번집 사람이 고양이를 기른다. 최종적으로 남은 4번집 사람은 물고기를 기른다.




이렇게 해서 아인슈타인의 퍼즐을 해결할 수 있습니다.

이러한 문제를 CSP(Constraint Satisfaction Problems: 제약조건 만족문제)라고 합니다.


아인슈타인 퍼즐을 해결하기 위해 2가지 정도의 알고리즘을 생각해볼 수 있습니다.

첫번째로는, 모든 경우의 수(5^25 or (5!)^5 둘 다 매우 큰 수 입니다...)를 고려하여 그 중 하나를 꺼내 정보와 비교하는 방법.

해당 방법은, 모든 경우의 수를 (5!)^5 으로 고려했을때 경우의 수가 약 240억개 입니다.

우리들의 컴퓨터로는 해결하기가 매우 힘들 수 있죠..


그래서 생각한 것이 두번째 알고리즘 입니다.

두번째 알고리즘은 각각을 카테고리 또는 조건으로 나누어 해결하는 방법입니다.

즉, A라는 조건을 다수의 배열 중 만족하는 배열을 찾아내는 것이 아니라 다수의 배열을 선언하기 전에 A라는 조건을 먼저 대입하고

이를 만족하는 배열 a가 있다면 a를 다음 조건, B에 대입하여 확인해나갑니다.

이렇게 해결을 진행하면 결국 DFS 방법으로 해결방법을 찾아나간다는 것을 아실 수 있습니다.


python으로 코드를 작성하기 위해 검색하던 중, python에서 제공하는 강력한 함수를 찾았습니다.

바로, python-constraint 함수 입니다.

함수에 대한 추가적인 사항은 아래 링크를 참고하시면 좋을 것 같습니다.

https://labix.org/python-constraint

https://pypi.python.org/pypi/python-constraint


python-constraint 함수를 통해, 직접 변수를 설정하고 제약조건을 추가하여 문제를 해결할 수 있습니다.

생각보다 code가 매우 간단해질 수 있어서 꼭 한번 다시 공부해보고 싶은 함수입니다.

추가적인 질문 이나 궁금사항은 댓글로 달아주시거나 이메일 주세요!


전체적인 python code와 실행결과는 아래와 같습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Houses
# 1 2 3 4 5
 
from constraint import *
problem = Problem()
 
nationality = ["영국""스웨덴""독일""노르웨이""덴마크"]
pet = ["개""고양이""새""말""물고기"]
cigarette = ["던힐""블렌드"
"펠몰""프린스""블루매스터"]
colour = ["빨강""초록""노랑""파랑""하양"]
beverage = ["커피""우유""맥주""생수""차"]
 
criteria = nationality + pet + cigarette + colour + beverage
problem.addVariables(criteria,[1,2,3,4,5])
 
problem.addConstraint(AllDifferentConstraint(), nationality)
problem.addConstraint(AllDifferentConstraint(), pet)
problem.addConstraint(AllDifferentConstraint(), cigarette)
problem.addConstraint(AllDifferentConstraint(), colour)
problem.addConstraint(AllDifferentConstraint(), beverage)
 
problem.addConstraint(lambda e, r: e == r, ["영국","빨강"])#1
problem.addConstraint(lambda s, d: s == d, ("스웨덴","개"))#2
problem.addConstraint(lambda c, g: c == g, ("커피","초록"))#5
problem.addConstraint(lambda u, t: u == t, ("덴마크","차"))#3
problem.addConstraint(lambda g, i: g-== 1, ("하양","초록"))#4
problem.addConstraint(lambda o, s: o == s, ("펠몰","새"))#6
problem.addConstraint(lambda k, y: k == y, ("던힐","노랑"))#7
problem.addConstraint(InSetConstraint([3]), ["우유"])#8
problem.addConstraint(InSetConstraint([1]), ["노르웨이"])#9
problem.addConstraint(lambda c, f: abs(c-f) == 1, ("블렌드","고양이"))#10
problem.addConstraint(lambda k, h: abs(k-h) == 1, ("던힐","말"))#11
problem.addConstraint(lambda l, o: l == o, ["블루매스터","맥주"])#12
problem.addConstraint(lambda j, p: j == p, ["독일","프린스"])#13
problem.addConstraint(lambda k, h: abs(k-h) == 1, ("노르웨이","파랑"))#14
 
solution = problem.getSolutions()[0]
 
for i in range(1,6):
  for x in solution:
    if solution[x] == i:
      print (str(i), x)
cs



블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc