TigerCow.Door

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

지난 포스팅에서 시간복잡도, 공간복잡도 등에 대해서 알아보며 Big-O 표기법에 대해서 살펴보았습니다.

이번에는 실제로 특정 코드나 알고리즘을 대상으로 그 시간복잡도를 분석해보는 실습을 진행해보도록 하겠습니다.


아래에서 다루게 될 예제들은 ''코딩인터뷰 완전 분석"(게일라크만맥도웰 지음, 이창현 옮김)_인사이트출판 서적에서 일부 참고 및 발췌하였습니다.



 > N에 대한 정확한 사용


우리는 이전 포스팅에서도 그러했듯이 Big-O 표기법으로 나타낼때에 흔히 O(N), O(log N) 과 같이 나타냅니다. 그런데 이때 N에 대해 정확하게 이해하지 못하였다면 추후 잘못된 분석을 할 수 있습니다.

아래와 같은 상황을 생각해보겠습니다.


여러개의 문자열로 구성된 배열이 있습니다. 

이때 각각의 문자열에 대해 먼저 정렬을 하고 이후 전체 문자열을 사전순으로 다시 정렬하는 알고리즘이 있습니다.

이러한 알고리즘의 수행시간은 어떻게 될까요?


간단히 생각해보면, 각 문자열을 정렬하는데 O(N*logN)의 시간이 소요되므로 모든 문자열에 대해서는 O(N*N*logN)이 소요될 것입니다. 그리고 전체 문자열들에 대해 사전순으로 정렬해야 하므로 O(N*logN) 이 추가됩니다.

즉, 해당 알고리즘의 수행시간은 O(N*N*logN + N*logN) = O(N*N*logN) 이라고 생각할 수 있습니다.


하지만 이는 완벽하게 틀린 분석입니다.

어디서 부터 잘못됐는지 아시겠나요?

바로 N에 대한 정확하지 않은 사용입니다.

위의 분석에서는 문자열의 길이와 문자열의 개수 모두 N으로 중복해서 사용하였습니다. 이는 아예 다른 시간복잡도를 가져오게 되는 큰 실수입니다.


제대로된 분석을 위해서는 다음과 같이 변수를 정의하고 진행합니다.


- 가장 길이가 긴 문자열의 길이를 s라고 하자.

- 배열의 길이를 a라고 하자.


이렇게 된다면, 각 문자열을 정렬하는데 O(s * log s) 가 소요되며 모든 문자열에 대해서 생각해 보면, O(a * s * log s) 가 소요됩니다.

그리고 문자열 비교시, 두개를 서로 비교할 때 O(s) 만큼 시간이 소요되고 이것을 총 O(a * log a) 번해야 하므로 O(a * s * log a) 만큼의 시간이 소요 됩니다.

따라서 전체 시간 복잡도는, O(a * s * (log a + log s)) 입니다.




> 재귀 호출 패턴 분석


아래는 균형 이진 탐색 트리에서 모든 노드의 값을 더하는 간단한 코드입니다. 수행시간을 한번 분석해보죠.


1
2
3
4
5
6
int sum(Node node){
    if(node == null){
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}
cs



1. 재귀호출 패턴분석


위의 코드가 단지 이진 트리라는 이유로, 또는 재귀호출이라는 이유로 시간복잡도에 로그가 들어간다고 생각하면 안됩니다. 

실제로 재귀 함수에 분기가 여러개 존재한다면 수행 시간은 일반적으로 O(분기^깊이)가 됩니다. 즉, 두 개의 분기만 존재하는 재귀함수라면 일반적으로 O(2^깊이)의 시간복잡도를 가지게 됩니다.


그렇다면 깊이는 어떻게 될까요? 위의 코드에서 나온 트리는 균형 이진 탐색 트리입니다. 즉, 총 N개의 노드가 있다면 깊이는 대략적으로 log N 의 값을 가지게 됩니다.

그럼 수식에 따라 시간복잡도는 O(2^(log_2 N))이 되는 것을 알 수 있습니다.

하지만 조금 더 살펴보도록 합시다.

결과에 나온 log_2 N 는 과연 무엇을 의미할까요?

2^(log_2 N) = P 라고 생각해본다면, 양변에 로그를 취해

log_2 2^(log_2 N) = log_2 P 가 됩니다. 그러면 로그의 특징에 따라서,

log_2 N * log_2 2 = log_2 P

log_2 N = log_2 P

N = P

가 됩니다.

따라서 총 시간복잡도는 O(N) 이 됩니다.



2. 코드가 무엇을 의미하는가


위에서는 재귀 호출 패턴 분석을 통해 시간복잡도를 분석해보았습니다.

하지만 조금 더 직관적인 방법으로는, 코드가 무엇을 하는지를 살펴보면 알 수 있습니다.

위의 코드는 트리의 각 노드를 한 번씩 방문한 뒤 각 노드에서 상수 시간에 해당하는 일을 하게 됩니다. 즉, 수행시간은 노드의 개수와 선형관계에 있음을 알 수 있고, 이에 따라 N개의 노드가 있을때 알고리즘의 시간복잡도는 O(N)임을 알 수 있습니다.




> 순열(permutation)의 개수를 구하는 코드


아래의 코드는 입력된 문자열로 나타낼 수 있는 순열의 개수를 구하는 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
void permutation(String str){
    permutation(str, "")
}
 
void permutation(String str, String prefix){
    if(str.length() == 0){
        System.out.println(prefix);
    }else {
        for(int i=0; i<str.length(); i++){
            String rem = str.substring(0,i) + str.substring(i+1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}
cs


코드를 보면 꽤 까다로울 수 있습니다.

이에 대한 시간복잡도 분석을 먼저 스스로 해보시고 보시는 것도 추천드립니다 :)


먼저 위의 코드를 분석하기 위해 permutation 함수가 얼마나 호출되는지, 각 호출마다 걸리는 시간이 얼마나 걸리는지를 나누어 생각하면 쉽게 분석할 수 있습니다.


1. 순열이 완성되는 시점에서의 permutation 함수 호출

순열이 완성되는 시점에서는 코드의 7번째 라인이 실행되는 것인데, 이 또한 permutation 함수가 호출되었기 때문에 입니다. 따라서 특정 문자열에 대한 순열의 개수만큼, permutation 함수가 호출될 것이며 이 값은 n! 입니다.


2. 순열 생성이 완성되기 전에 permutation 함수 호출

동시에 9~12번째 코드라인이 얼마나 호출되어 반복되는지를 살펴보아야 합니다.

트리구조로 생각한다면 1번에서 알아본 n! 는 결국 리프노드의 개수입니다.

그리고 루트에서 리프노드까지의 거리는 n일 것이며, 이를 통해 트리의 총 노드는 절대로 n*n! 을 넘지 못합니다.


3. 한 번의 permutation 호출에서의 소요 시간

한번의 호출이 있었을 때 연산 시간이 얼마나 걸리는지를 파악합니다.

7번째 줄에서는 문자열 전체를 출력하기 때문에 O(N) 시간이 걸리며, 10번째 줄에서 시행되는 substring 함수 또한 O(N) 시간이 걸리게 됩니다.

( 단순 함수 호출이기에 O(1)로 생각하실 수 있으나 java 업데이트 후 해당 함수가 O(N)의 소요시간을 갖게 되었습니다. )


이렇게 1,2,3으로 나누어 분석한 결과 permutation 함수의 총 시간 복잡도는 O(N * N * N!) 임을 알 수 있습니다.




> 피보나치 수 1


아래의 코드는 N번째 피보나치 수(Fibonacci number)를 구하는 코드입니다.


1
2
3
4
5
int fib(int n){
    if (n <= 0return 0;
    else if (n == 1return 1;
    return fib(n-1+ fib(n-2);
}
cs


이는 위에서 우리가 알아보았던 재귀 호출 패턴 분석을 이용하면 O(2^N) 의 시간복잡도를 가지게 됩니다.


하지만 이를 좀 더 세밀하게 분석해보면 약 O(1.6^N)의 시간복잡도가 나오게 됩니다. 구체적으로 다루지는 않겠지만, 우리가 재귀 호출에 대해서 트리구조로 그려볼 때, 호출 스택의 밑바닥에서 가끔식 한번의 호출만 필요한 경우 등이 그 이유일 것입니다.




> 피보나치 수 2


이번에도 위와 같은 동작을 하는, 피보나치 수와 관련된 코드이지만 이번에는 이전에 계산된 결과 값을 정수 배열에 저장하고 이를 이용하는 방식의 알고리즘 입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
void allFib(int n){
    int[] memo = new int[n+1];
    for (int i=0; i<n; i++){
        System.out.println(i+": "+fib(i,memo));
    }
}
 
int fib(int n, int[] memo){
    if (n <= 0return 0;
    else if (n == 1return 1;
    else if (memo[n] > 0return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}
cs


위의 코드에 대해 임의의 n 값으로 실제 호출 스택을 그려본다면 fib(i)를 호출할 때마다 fib(n-1)과 fib(n-2)의 계산이 이미 끝나 있고 이를 단순히 배열에서 가져오는 연산을 진행하는 것을 알 수 있습니다.

즉, 이러한 과정은 상수시간 안에 동작하고 상수 시간의 동작을 총 N번 반복하기 때문에 해당 알고리즘의 시간복잡도는 O(N)을 가지게 됩니다.


이러한 방법은 메모이제이션(Memoization) 이라고 불리는 방법으로써, 지수 시간이 걸리는 재귀 알고리즘을 최적화할 때 쓰는 흔한 방법 중 하나 입니다.

비슷한 방법 중 하나로는 동적계획법(Dynamic Programming) 이 있습니다.


물론 메모이제이션과 동적계획법이 아예 같은 개념인 것도 아니고, 아예 다른 개념인 것도 아닙니다.

필요하다면 추후 다루게 되겠지만 간단하게 살펴보면, 메모이제이션은 결과를 구하고 이를 할용하면서 문제를 해결하는 것이고, 동적계획법은 큰 문제에 대해 작은 부분으로 나누어 작은 것부터 해결해 나가는 것 입니다.



이렇게 지난 포스팅에서 알아본 시간복잡도에 대한 개념에 이어 여러가지 예제들을 함께 살펴보았습니다.

해당 예제들을 통해 실수 할 수 있는 부분들을 캐치하여 추후 자신이 분석하고자 하는 알고리즘에 대해 보다 정확한 분석이 이루어 져야 합니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

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

최근 Java로 알고리즘 스터디를 시작하게 되었습니다.

단순히 문제풀이 보다는 이론적인 내용들을 살펴보며 관련된 문제를 푸는 방식으로, 기초부터 다시 살펴보려합니다.

이번에는 직접적인 알고리즘 내용에 앞서, 알고리즘 분석 즉 시간복잡도와 공간복잡도에 대해 이야기를 먼저 진행해보겠습니다.



> 왜 알아야 하는가?


Big-O 표기법은 알고리즘의 효율성을 나타내는 지표 혹은 언어이다.

이를 통해 자신이 작성한 알고리즘이 이전보다 빨라졌는지 느려졌는지 판단하는데 도움이 될 것이다.

물론 이 외에 다른 개발자들과 특정 알고리즘에 대해 이야기하거나 효율성 판단등에 의해서 Big-O 표기법을 통해 보다 원활하게 의사소통을 진행할 수 있다.


실제로 Big-O 표기법 이외에 다른 표기법도 있으나 이에 대해서는 혼동을 피하기 위해 제일 마지막에서 언급하겠다.


또한 Big-O 표기법에 대해 이해하는 방식이 조금씩 상이할 수 있지만 그 정의를 정확하게 이해한다면 문제되지 않을 것이다.



> Big-O 표기법의 정의


Big-O 표기법은 사전적으로, 시간(또는 공간)의 상한을 이야기한다.

즉, 시간복잡도와 공간복잡도의 상한에 대해서 이야기하는 것이다.

(주로 시간복잡도를 다루게 될 것이므로 시간을 대표로 설명하겠다.)


정의대로 이야기한다면 시간복잡도에 대해서 이야기할 어떤 것의 최악의 경우(가장 느렸을 경우)에 대한 시간을 이야기 하는 것이다.

즉, 평균적으로 10시간이 걸리는 업무가 있지만 특정 상황에 따라 20시간이 걸린다고 생각해보자. 이때 그 업무에 대한 시간의 상한은 20시간이다. 아무리 오래 걸려도 20시간이면 되기때문이다.

이때 이야기 하는 '아무리 오래 걸려도' 라는 키워드가 결국 Big-O이다.


그럼 이러한 의문이 들 수 있다.


"그럼 그 업무는 아무리 오래 걸려도 100시간 안에 할 수 있으니, 시간의 상한이 100시간이라고 해도 맞는건가요?"


그렇다. 정의에 따라서는 전혀 틀린말이 아니고 수학적으로도 옳은 표기이다.

하지만, 대체로는 그렇게 이야기하지 않는다.


Big-O가 대략적으로 어떤걸 의미하고자 하는지 이해가 갔다면 조금 더 수식적으로 살펴보자.


이를 위해서 위에서 언급한 예시를 조금 더 구체화 해보자.

특정 업무에 대해서 처리할 문서가 n개라고 가정하자.


이때 만약 A라는 사람은 정직하게 일해서 문서당 소요시간이 1시간이다.

근데 B라는 사람은 아직 경력이 부족해서 문서당 소요시간이 2시간이다.

슬프게도 C라는 사람은 호기심이 많아 문서개수에 대해 제곱시간이 소요된다.

놀랍게도 D라는 사람은 자동화 툴을 만들어 놓아서 문서개수에 상관없이 10시간이 소요된다.


이러한 사람들에 대해 각각 Big-O로 소요시간을 나타내보자.


A는 O(N)이다.

문서 1개당 소요시간이 1시간이므로 문서가 늘어나면 소요시간도 선형적으로 늘어난다.


B는 O(2N)이다.

A와 비슷하게 선형적으로 늘어나지만 그 값이 2배일 뿐이다.


C는 O(N^2)이다.

A와 B에 비해 호기심이 많은 C는 문서당 제곱시간이 소요된다고 하였기에 위와 같이 표기된다.


D는 O(10)이다.

자동화 툴을 만들어 놓은 D는 문서 개수와 상관없이 무조건 10시간이 소요된다.


Big-O표기는 위와 같이 표기하는 것이다.

하지만 아직 한가지가 남았다. Big-O 에서는 작은 것들은 신경쓰지 않는다.


정말 간단하게 이야기한다면 Big-O 표기법은, 제일 영향력있는 놈만 신경쓰겠다는 이야기다.

실제로 알고리즘에 큰 영향을 주는 것만 고려하겠다는 이야기인 것이다.


이것은 특정 수식에서 최고차항을 제외한 나머지를 무시한다는 의미이기도 하며, 최고차항에 대한 상수배 또한 무시하겠다는 것이다.


최고차항에 대한 상수배를 무시하겠다는 것은

즉, Big-O 정의에 따르면, O(N)과 O(2N)은 모두 동일하게 O(N)으로 표기된다.

그렇다면, O(10)은 어떻게 표기될까?

상수 시간이므로 O(1) 로 표기된다.


그리고 최고차항을 제외한 나머지를 무시하겠다는 것은,

O(N^2 + 10N + 3) 으로 표시된 값이 있을때 이를 O(N^2)과 같이 표기하겠다는 것이다.



위와 같이 알아본 Big-O 표기법은 초기에 언급한 것과 같이 단순히 시간복잡도를 분석하는데만 사용되지 않는다. 시간 또는 공간 모두 분석하는데 사용되며 공간에 대해 분석하는 것을 공간복잡도라고 이야기한다.


공간복잡도에 대해서 추가적인 설명을 하자면 다음과 같다.


> 공간복잡도

재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함된다.

하지만 함수를 단지 n번 호출했다고 해서 무조건 O(n) 공간을 사용하는 것은 아니다.



Big-O 표기법에서 주로 사용되는 표현들에 대한 대소비교를 해본다면 다음과 같다.(시간복잡도, 공간복잡도 순서)


O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)


그럼 마지막으로, 처음에 이야기했던 Big-O 이외의 표기법들에 대해 간단히 알아보자.


+ Big-Omega

빅 오메가라고 부르는 표기법은 시간에 대한 등가 또는 하한의 개념을 나타낸다.

즉 모든 process는 Ω(1)로 표기할 수 있다. 결국 오메가로 표기되는 알고리즘은 Ω 수행시간보다 빠를 수 없다.


+ Big theta

빅 세타라고 부르는 표기법은 Big-O와 Big-Omega 모두를 이야기한다.

즉, 특정 알고리즘의 시간복잡도가 O(N) 이면서 Ω(N) 이라면 이는 θ(N)이라고 표기할 수 있다.




이렇게 Big-O에 대한 개념적인 내용을 정리해보았습니다.

추후 필요하다고 생각되면 특정 코드나 내용들에 대해 시간복잡도와 공간복잡도를 계산해보는 내용에 대해서도 정리해보겠습니다.



블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

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

이번 포스팅에서는 분류나 회귀에서 사용되는 KNN(K - Nearest Neighbors) 알고리즘에 대해서 알아보도록 하겠습니다.



1. KNN(K - Nearest Neighbors)


KNN, K-최근접 이웃 알고리즘은 특정공간내에서 입력과 제일 근접한 k개의 요소를 찾아, 더 많이 일치하는 것으로 분류하는 알고리즘입니다.


말로 이해하는 것보다 아래 그림을 통해 이해하는 것이 훨씬 쉬울 것 입니다.


위의 그림과 같은 좌표공간을 예시로 확인해보겠습니다.

위에서 파란색 점으로 되어 있는 그룹을 A그룹이라고 생각하고, 주황색 점으로 되어 있는 그룹을 B라고 하겠습니다.

이때 우리는 별 모양으로 표시된 입력값이 A그룹에 속하는지, B그룹에 속하는지를 알고 싶습니다.


그리고 이럴때 사용되는 KNN 알고리즘은 다음과 같이 적용됩니다.

우선 k값을 정의해줘야 합니다. 해당 k값에 대한 설명은 조금 밑에서 드리도록 하고, 우선 k를 3이라는 값으로 정했다고 생각해보겠습니다.


그럼 우리는 입력값과 가장 근접한 k개의 요소를 찾습니다. k = 3이므로 3개의 요수를 찾아보면 다음 그림과 같습니다.


별 모양의 점을 기준으로 원을 그려서 확인함으로써, 위의 빨간색 원과 같이 파란색 점 하나와 주황색 점 두개가 선택됨을 알 수 있습니다.

그리고 이를 통해 입력값은 주황색 점의 그룹, 즉 B의 그룹과 더 일치하다는 판단을 내릴 수 있습니다.


추가적으로 생각해보면, KNN 알고리즘은 정의한 k 값에 따라서 입력값의 분류 결과가 달라질 수 있습니다.


만약 우리가 k를 3으로 두지 않고 1로 두었다면, 아래 그림과 같은 원이 그려짐으로써 입력값은 A그룹으로 분류될 수 있습니다.



 KNN 알고리즘을 사용할 때는 적절한 k값을 찾아 설정해주는 것이 중요합니다.


또한, 위와 같이 2개의 그룹에 대해 분류를 할때 만약 k값을 짝수로 한다면 어떻게 될까요?

만약 k = 4 라고 설정했다면 다음과 같은 결과가 나옵니다.


그림에서 확인할 수 있듯이, 파란색 점 2개, 주황색 점 2개가 됨으로써 입력 값이 어떠한 그룹이라는 결론을 내릴 수 없게 됩니다.


그렇다고 무조건 k를 홀수 값으로 설정해야 하는 것은 아닙니다.

위와 같이 2개의 그룹에 대한 분류를 할때는 무조건 홀수 값을 주어야 겠지만, 만약 입력값을 3개의 그룹에 대해 분류를 할때 k = 3으로 둔다면 각각의 그룹의 요소가 하나씩 포함되어 위와 같이 어떠한 그룹이라는 결론을 내지 못하는 상황이 올 수 있습니다.


즉, KNN알고리즘을 사용할때는 분류될 그룹의 종류등을 고려하여 적절한 k값을 설정해주는 것이 중요합니다.



2. 파이썬으로 구현하기


위에서 알아본 KNN 알고리즘을 파이썬으로 구현해 보았습니다.

* 코드는 jupyter notebook에서 실행하였습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib nbagg
 
A_x_list = [0,2,4,1,1,4]
A_y_list = [4,1,5,5,2,6]
A_x = np.array(A_x_list)
A_y = np.array(A_y_list)
 
B_x_list = [7,7,5,7,10,9]
B_y_list = [4,0,2,2,3,3]
B_x = np.array(B_x_list)
B_y = np.array(B_y_list)
 
finding_point = [5,4]
 
plt.figure()
plt.scatter(A_x,A_y)
plt.scatter(B_x,B_y)
plt.scatter(finding_point[0],finding_point[1], marker='*')
 
plt.show()
cs


먼저 입력값과 기존에 존재하는 A그룹, B그룹을 좌표상으로 나타내보았습니다.

위의 코드를 통해 나오는 그래프는 아래와 같이, 우리가 위에서 살펴봤던 예제 그림과 같습니다.



그리고 실제로 입력값을 KNN 알고리즘에 적용시켜 분류하는 코드는 다음과 같습니다.


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
# L리스트에서 c번째 작은 값 찾는 함수
def count_min_value(L,c):
    temp = L.copy()
    temp.sort()
    item = temp[c-1]
    return L.index(item),item
 
# 입력값이 A그룹인지 B그룹인지 찾는 함수::KNN Algorithm 적용
def finding_AorB(k,x,y):
    numA = 0
    numB = 0
    A_xy = []
    B_xy = []
    # x,y 좌표가 따로 있는 것을 하나의 리스트로 통합
    for i in range(len(A_x_list)):
        A_xy.append([A_x_list[i],A_y_list[i]])
    for i in range(len(B_x_list)):
        B_xy.append([B_x_list[i],B_y_list[i]])
 
    A_distance = []
    B_distance = []
    # x,y 좌표에 대해 입력값과의 거리 산출
    for each in A_xy:
        dis = ((each[0- x)**2 + (each[1- y)**2)**(1/2)
        A_distance.append(dis)
    for each in B_xy:
        dis = ((each[0- x)**2 + (each[1- y)**2)**(1/2)
        B_distance.append(dis)
    A_result = []
    B_result = []
    
    A_min_count = 1
    B_min_count = 1
    while(numA + numB < k):
        min_A = 99999
        min_B = 99999
 
        _, min_A = count_min_value(A_distance,A_min_count)
        _, min_B = count_min_value(B_distance,B_min_count)
 
        if min_A < min_B:
            numA += 1
            A_min_count += 1
            A_result.append(A_xy[A_distance.index(min_A)])
            A_distance[A_distance.index(min_A)] = -1
        elif min_A > min_B:
            numB += 1
            B_min_count += 1
            B_result.append(B_xy[B_distance.index(min_B)])
            B_distance[B_distance.index(min_B)] = -1
        elif min_A == min_B:
            numA += 1
            numB += 1
            A_min_count += 1
            B_min_count += 1
            A_result.append(A_xy[A_distance.index(min_A)])
            A_distance[A_distance.index(min_A)] = -1
            B_result.append(B_xy[B_distance.index(min_B)])
            B_distance[B_distance.index(min_B)] = -1
    if numA > numB:
        print("RESULT: The point is A")
    elif numA < numB:
        print("RESULT, The point is B")
    elif numA == numB:
        print("I DON'T KNOW")
    print("A point is",A_result,"\nB point is",B_result,"\n")
            
cs


위의 코드를 통해 k = 1, 2, 3, 4 로 실행 시켜보면 아래와 같은 결과가 나옵니다.




이렇게 하여 KNN 최근접 이웃 알고리즘에 대해서 알아보았습니다.

위에서 구현된 파이썬 코드는 아래 github주소에 있습니다 :)


https://github.com/doorBW/KNN-Algorithm-by-python


오류가 발생하거나 잘못된 점이 있다면 언제든지 피드백 해주시길 바랍니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / 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

Data-Analysis / AI / back-end / 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

Data-Analysis / AI / back-end / 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

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


안녕하세요.

우리는 지난 포스팅들을 통해서 동적 프로그래밍(Dynamic programming)의 3가지 예시에 대해 살펴보았습니다.

이번 포스팅에서는 예시들과 같은 최적화 문제에 동적 프로그래밍을 적용하기 위해 가져야 하는 두 가지 중요한 구성요소,

최적 부분 구조와 중복되는 부분 문제에 대해 살펴보도록 하겠습니다.


어떤 문제에 대해서 동적 프로그래밍을 적용하기 위해서 해당 문제가 가져야 할 두 가지 구성요소는,

최적 부분구조와 중복되는 부분 문제입니다. 하나씩 자세히 살펴보도록 하겠습니다.


1. 최적 부분 구조(Optimal substructure)


동적 프로그래밍을 적용하기 위해 가장 먼저 확인해야 할 것은 최적해의 구조의 특징입니다.

기본 문제의 최적해가 부분 문제의 최적해를 포함하고 있을 때, 우리는 그 문제가 최적 부분 구조를 가졌다고 할 수 있습니다.

어떤 문제가 최적 부분 구조를 가진다는 것은 동적 프로그래밍이 적용될 수 있다는 좋은 단서가 됩니다.

앞에서 알아보았던 것처럼, 동적 프로그래밍은 부분 문제의 최적해로부터 전체 문제의 최적해를 구하기 때문입니다.

우리는 아래와 같은 보편적인 방법을 통해 최적 부분 구조를 스스로 찾아볼 수 있습니다.


ㄱ. 문제에 대한 해는 선택하는 과정으로 만들어짐을 보여야 한다. 예를 들어, 막대에서 맨 처음 자르는 곳을 선택하거나 행렬 체인을 나눌 위치를 선택하는 과정을 포함하고 있다. 이런 선택을 하는 과정은 한 개 또는 그 이상의 풀어야 할 부분 문제를 남긴다. 즉, 선택을 통해서 한개 이상의 부분 문제를 만들어 낸다.


ㄴ. 주어진 문제에 대해서 최적해에 이를 수 있는 선택이 주어졌다고 가정한다. 이런 선택을 어떻게 결정하느냐는 아직 걱정하지 않는다. 단지 그 선택이 주어졌다고 가정한다.


ㄷ. 주어진 이 선택에 대해서 발생하는 부분 문제가 어떤 것인지를 정하고 그 부분 문제들의 범위를 가장 잘 표현할 수 있는 방법을 전한다.


ㄹ. 한 개의 최적해에 사용된 부분 문제들의 해가 최적이어야 함을 "잘라붙이기(cut and paste)" 방법을 이용해 보인다. 이것은 각 부분 문제들의 해가 최적이 아니라고 가정하고 모순임을 보이면 된다. 특히, 각 부분 문제들의 최적해가 아닌 부분을 "잘라내고(cutting)" 거기에 최적해를 "붙이면(paste)", 원래의 해보다 좋은 해를 얻게 된다. 따라서 잘라 붙이기 이전의 해가 최적해라는 가정에 모순이 되는 결론에 도달한다. 최적해에서 발생하는 부분 문제가 하나 이상이면 그 부분 문제들은 일반적으로 모두 비슷하므로 하나에 대해 적용한 잘라 붙이기 방법을 다른 부분 문제에도 쉽게 수정해 사용할 수 있다.


쉽게 말해서, 최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.

예를 들어, A라는 문제의 부분 문제 a,b가 있을 때, a,b의 최적해는 a',b'라고 가정한다면 A의 최적해는 a'와 b'로써 구성됩니다. 다시 말해, A라는 문제가 최적 부분 구조를 가지고 있는데 방금과 같은 조건에서 A의 최적해는 a'와 b'로 구성되는 것을 증명한다면, 최적 부분 구조를 가진다는 것을 언급하며 이로 인해 A의 최적해가 a'와 b'가 아닌 a'와 c'으로 구성된다고 가정한다면 b의 최적해는 c'이어야 하는데 b의 최적해는 b'이기 때문에 가정이 모순임을 보여 증명할 수 있습니다.



이때 문제가 최적 부분 구조를 가지고 있지 않음에도 최적 부분구조를 가지고 있다고 가정하지 않도록 주의해야 합니다.

예시를 통해 바로 확인해보도록 하겠습니다.



위의 그림에 대해 확인하기 앞서 아래 두가지 개념에 대해서 잠깐 설명드리겠습니다.

그래프에서 두 정점 a, b에 대해서,

(비가중)최단 경로: a에서 b까지 연결되는 가장 적은 개수의 간선들로 이루어 지는 경로입니다.

(비가중)최장 경로: a에서 b까지 연결되는 가장 많은 개수의 간선들로 이루어 지는 경로입니다.

또한 각각의 경로는 경로 내에서 순환이 포함되지 않는 단순(simple) 조건을 가지고 있으며 각 간선에 대해서는 가중치가 존재하지 않습니다.


그렇다면 위의 그래프를 보았을 때, q와 t사이의 최단 경로는 무엇일까요?

q -> r -> t 또는 q -> s -> t 입니다.

각각을 부분 문제로 나누어 보았을 때의 최적해는 어떻게 될까요?

q 와 r 사이의 최단경로는 q -> r 이며, r과 t사이의 최단경로는 r -> t 입니다.

이러한 것을 보아 최적 부분 구조를 가지고 있다고 알 수 있습니다.


하지만, 최장 경로에 대해서는 어떨까요?

q와 t사이의 최장 경로 또한 위와 같이 q -> r -> t 입니다.

그런데 그 부분 문제, q와 r사이의 최장 경로는 어떨까요?

q -> r이 아닌, q -> s -> t -> r 이 됩니다.


이러한 예는 최장 단순 경로를 찾는 문제가 최적 부분 구조를 가지지 않을 뿐만 아니라 부분 문제들의 최적해로부터 전체 문제의 조건에 맞는 해를 언제나 만들어 낼 수 있는 것은 아니라는 사실을 보여줍니다.


그렇다면, 최장 단순 경로의 부분 구조와 최단 경로의 부분 구조는 왜 다른 것일까요?

바로, 최장 경로를 찾는 문제의 부분 문제는 독립적(Independence)이지 않기 때문입니다.

여기서, 부분문제가 독립적이다라는 것은 어떤 것을 의미할까요?

독립적이다라는 것의 의미는, 동일한 문제에서 부분 문제 하나의 해가 다른 부분 문제의 해에 영향을 주지 못함입니다.

다시 말해, 위의 최장 단순 경로에서는 하나의 부분 문제를 풀기 위해 사용된 자원이 또 다른 부분 문제에서 사용되기 때문에 독립적이다라고 볼 수 있습니다. 그렇기에 최적 부분 구조 또한 아닙니다.


즉, 최적 부분 구조를 가지기 위해 부분 문제들은 독립성을 가져야합니다.



2. 중복되는 부분 문제(Overlapping subproblems)


동적 프로그래밍을 적용하기 위해 기본 문제가 가져야 할 구성요소 중 두번째입니다.

만약 재귀 알고리즘이 같은 문제를 계속해서 풀게 되는 경우 우리는 그 최적화 문제가 중복되는 부분 문제를 가진다고 말합니다. 반대로, 분학정복 기법을 사용하기에 적합한 문제는 보통 재귀적으로 호출하는 각 문제들이 새로운 것입니다.

동적 프로그래밍 알고리즘은 중복되는 부분 문제를 이용하는데, 각 부분 문제에 대해서 한 번만 계산하고 그 해를 테이블에 저장합니다. 그리고 그 부분 문제가 중복되어 나올 때 마다 상수 시간동안 테이블을 확인하여 해를 반환합니다.


이러한 해결방식 중에서 대표적인 것은 메모하기(memoize)입니다.

기본적인 아이디어는 자연스러우나 계속 되는 호출로 인해 비효율적인 재귀 알고리즘을 메모하는 방법으로써, 각 부분 문제들의 해를 저장하는 테이블을 가집니다. 맨 처음에 테이블의 각 엔트리들은 그 테이블이 아직 채워지지 않았다는 것을 나타내는 특정한 값을 가지고 있다가, 재귀 알고리즘을 수행하는 동안 부분 문제가 처음으로 호출되면 그 문제의 해를 계산하고 그 값을 테이블에 저장합니다. 그리고 이후 동일한 부분 문제가 호출되면 테이블에서 저장된 해를 반환합니다.



이렇게 해서 간단하게, 동적 프로그래밍의 요소 두 가지를 알아보았습니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


이번 포스팅에서는 동적 프로그래밍의 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)에 대해서 알아보도록 하겠습니다.


1. 행렬 체인 곱셈(Matrix-chain Multiplication)


이번 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)문제는 n개의 행렬을 곱하는 것에 대한 문제입니다.

먼저 행렬의 곱은 아래의 수도코드와 같은 방식으로 진행됩니다.



위의 수도코드를 보면 A행렬이 p*q이고 B행렬이 q*r일때, 이 두 행렬의 곱을 통한 새로운 행렬 C를 계산하는데 걸리는 시간은 수도코드의 8행에 따른 곱셈의 횟수, pqr번에 의해서 결정됩니다.

예를들어, 아래와 같은 세개의 행렬이 있을 때, 두가지 방법의 곱셈이 가능할 것입니다.



A1와 A2를 먼저 계산한다면 총 840번의 곱을 수행해야 합니다.

하지만 A2와 A3를 먼저 계산한다면 총 460번의 곱을 수행하면 됩니다.


따라서 행렬 체인 곱셈 문제에서는 행렬을 곱할 때 비용이 가장 적은 순서를 찾아내는 것이 목표입니다.



2. Brute-force 방식


지난 두 예제에서 알아본 것과 같이, 동적 프로그래밍을 적용한 해결 방법을 살펴보기전에 모든 경우의 수를 조사하는 brute-force방식을 살펴보도록 하겠습니다.

n개의 행렬을 괄호로 묶는 서로 다른 방법의 수를 P(n)이라고 함ㄴ다면, n이 1일 때에는 행렬이 한 개뿐인 것이므로 괄호를 묶는 방법은 단 한가지 입니다. n이 2보다 크거나 같을 때, 행렬 전체를 완전하게 괄호로 묶는 방법의 수는 두개의 완전하게 괄호로 묶인 두 부분 곱들의 곱이고, 두 개의 부분 곱 사이를 나누는 것은 1과 n-1의 값, k번째와 k+1번째 행렬의 사이가 됩니다. 이를 통해 아래의 점화식을 얻을 수 있습니다.



위의 식을 분석해보면 점화식의 해가 대략 개를 가지는 것을 알 수 있습니다.



3. 동적 프로그래밍으로 행렬 체인 곱셈 문제 해결하기


먼저 행렬 체인 곱셈 문제의 최적 부분 구조를 생각해보면 다음과 같습니다.

를 괄호로 최적으로 묶기 위해 와 의 사이에서 나눈다고 생각해보겠습니다. 그렇다면 앞의 부분 곱, 을 확인하였을 때, 의 괄호 묶는 방법은 의 최적의 괄호 묶는 방법으로 되어야 할 것 입니다.


즉, 최적의 괄호를 묶기 위해서 부분 곱에서 또한 같은 특징이 성립되어 부분 곱도 괄호 묶기에 대해 서로 최적이어야 합니다.


따라서 m[i,j]는 다음과 같이 정의됩니다.



그리고 m[i,j]는 다음과 같은 점화식을 통해 값이 구성됩니다.



이렇게 구한 m은 행렬 곱셈을 계산하는데 필요한 최적의 계산 수를 저장합니다.

하지만 행렬을 곱하는 방법을 제공하지는 않기에 우리는 s라는 배열을 사용하여 필요한 정보를 저장합니다.


s[i,j] 에는 Ai행렬부터 Aj까지의 행렬을 곱할 때 마지막으로 괄호 묶기가 되는 와  의 k값을 저장합니다.


이러한 테이블과 점화식을 토대로 행렬 체인 곱셈문제를 해결하는 알고리즘은 다음과 같습니다.




위의 수도코드에서 4번라인까지는 테이블 m을 초기화하는 과정입니다.(길이가 1인 행렬 곱셈에 대한 최소비용은 0이므로)

이후 5번 라인에서 반복문이 시작되며 처음엔, i가 1부터 n-1까지 증가하는 동안 길이가 2인 행렬에 대한 최소 비용을 구하며, 두번째 반복에서는 i가 1부터 n-2까지 증가하는 동안 길이가 3인 행렬에 대한 최소비용을 구합니다. 이런식으로 반복문이 진행되고 이를 통해 수도코드의 총 시간복잡도는 이며, 테이블 m과 s를 저장하기 위해 필요한 공간 복잡도는 입니다.


A1부터 A6행렬까지 있는 곱셈을 계산하였을때 작성되는 테이블 m과 s는 아래와 같으며 중간 계산 중 일부가 아래에 나와 있으니 확인하시고 확실히 이해 하시길 바랍니다.




이렇게 해서 동적 프로그래밍의 세번째 예제, 행렬 체인 곱셈(Matrix-chain Multiplication)에 대해서도 알아보았습니다.

특히나 저는 행렬 체인 곱셈이 많이 헷갈리고 어려웠기에 추가적으로 확인하면서 더 간단하게 설명이 되는 부분은 수정하도록 하겠습니다.

이해가 잘 안되거나 궁금한 점은 언제든 댓글을 남겨주세요 :)


블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요.

이번 포스팅에서는 동적 프로그래밍(Dynamic Programming)의 예제인 Assembly Line Scheduling과 Matrix-chain Multiplication에 대해서 알아보도록 하겠습니다. 동적 프로그래밍과 막대자르기(Rod-Cutting)예제에 대한 내용은 지난포스트를 확인해주시길 바랍니다.


1. Assembly Line Scheduling


먼저 Assembly Line Scheduling 예제에 대한 설명을 하겠습니다.



위와 같은 사진을 참고하여 어느 특정 공장에 두 개의 라인이 있습니다.

그림에서는 위의 라인이 S1, 아래의 라인이 S2입니다.

그리고 각각의 라인에서 진행되는 1부터 n까지의 공정이 있습니다.

이때 같은 열에 있는 공정은 같은 공정이지만 라인에 따른 시간차이가 있습니다.

또한, 위 또는 아래의 라인에서 다른 라인으로 넘어 가는데 소요되는 시간 t가 존재합니다.

이때, 같은 라인에서 넘어가는 시간은 0이라고 가정합니다.

즉, S1,1에서 S2,2로 넘어가는 시간은 t1,2 입니다. 또한 S1,1에서 S1,2로 넘어가는 시간은 0입니다.


각각의 기호에 대한 개념을 정리하면 아래와 같습니다.

 : i라인에서의 j번쨰 공정(j-th station on line i)

 : 에서 공정에 소요되는 시간(assembly time required at station )

 : i 라인으로 들어가는데 소요되는 시간(time to enter line i)

 : i 라인에서 나오는데 소요되는 시간(time to exit line i)

 : j 번째 공정을 하고 i 라인에서 다른 라인으로 교체되는 시간(time to transfer from line i after station j)



예들 들어 보겠습니다.

먼저, 위의 라인으로 들어가는 시간 e1은 0.5초, 아래의 라인으로 들어가는 시간 e2는 1초로 가정합니다.

그리고 위의 라인에서 진행되는 첫번째 공정은 S1,1로 표현하며 여기서 진행되는 공정 a1,1는 1초가 걸린다고 가정하겠습니다.

그리고 아래의 라인에서 진행되는 첫번째 공정은 S2,1로 표현하며 여기서 진행되는 공정 a2,1는 2초가 걸린다고 가정하겠습니다.

같은 방식으로 a1,2는 4초, a2,2는 3초가 걸린다고 가정하겠습니다. 또한 t1,2는 0.5초이며 t2,2는 3초라고 가정하겠습니다.

정리해보면 아래와 같습니다.

e1 = 0.5s

e2 = 1s

a1,1 = 1s

a2,1 = 2s

a1,2 = 4s

a2,2 = 3s

t1,2 = 0.5s

t2,2 = 3s

위와 같은 조건이 있을때 두번째 공정까지 진행하는 최단시간과 그 과정은 어떻게 될까요?

이러한 문제를 해결하는 것이, Assembly Line Scheduling 입니다.


위의 예제를 하나씩 확인해보겠습니다.

먼저 첫번째 공정을 마무리하는 시점을 생각해보면 S1,1 는 e1+a1,1 = 1.5s 이며 S2,1는 e2+a2,1 = 3s 입니다.

그리고 두번째 공정에 대해서 생각해보겠습니다.

만약 S1,2에서 공정을 진행한다고 가정하면, e1+a1,1+a1,2 = 5.5s 또는 e2+a2,1+t2,2+a1,2 = 10s 입니다.

그리고 S2,2에서 공정을 진행한다고 가정하면, e1+a1,1+t1,2+a2,2 = 5s 또는 e2+a2,1+a2,2 = 6s 입니다.

가장 최단시간이 걸리는 것은 5초의 과정을 가진 e1 + a1,1 + t1,2 + a2,2 입니다.



2. Brute-force


Assembly Line Scheduling에 대한 알고리즘을 고민해봅시다.

최적의 답을 찾기 위해서 전체의 경우의 수를 고려해보면 어떨까요?

n개의 공정이 존재할 때, 2개의 라인이 존재하므로 총 개의 경우의 수를 고려해야 합니다.

쉽게 말해서, S1,4의 공정을 수행하는데 오는 경로는 S1,3과 S2,3이 있는 것을 통해 특정 위치의 공정을 위한 경로를 확인하면 2개씩 존재하고, 공정의 개수는 총 n개이므로 총 개를 확인해야 하는 것 입니다.

즉, 이러한 모든 경우의 수를 탐색하는 Brute-force Approach로는 다음과 같은 시간복잡도를 가집니다.


In Brute-force Approach, 


이러한 Brute-force 방식은 상당히 많은 소요시간을 가지는 것을 지난 막대자르기 예제에서 확인 할 수 있었습니다.

뒤에서 수도코드를 확인하면서 설명드리겠지만,

동적 프로그래밍을 통해 해당 Assembly Line Scheduling 문제를 선형시간에 탐색할 수 있습니다.

따라서 동적 프로그래밍으로 알고리즘을 구현해보도록 합니다.



3. 동적 프로그래밍에 의한 Assembly Line Scheduling 해결


지난 포스팅에서 이야기 했던 것 처럼, 동적 프로그래밍의 기본 핵심은 테이블을 사용하는 것 입니다.

따라서 우리는 모든 경우에 수에 대해 탐색하는 것이 아니라, 탐색한 경우에 대해서는 테이블에 저장하여 필요할 때 값을 참조하도록 합니다.



위의 사진에 나와있듯이, 사용하는 테이블 의 의미는, i라인에서 진행하는 j 공정(=Si,j)을 시작지점으로 했을 때 가장 빠른 시간입니다.

즉 우리는 다룬 위의 예제에서는 2개의 라인을 이용하므로 f1과 f2가 테이블로 존재할 것입니다.

그리고 f*는 최종적으로 가장 빠른 시간을 저장하는 변수 입니다.

이때 f*는 다음과 같은 식으로 결정 됩니다.



그리고 각각의 테이블을 구성하는 방법은 다음과 같습니다.



또한 이후 수도코드에서 보게될 L테이블이 있습니다.

이는 최종적으로 Assembly Line Scheduling의 과정을 보여주기 위한 테이블입니다.

즉, l1[3]에 입력되는 값은, S1,3에 오는데 어떠한 라인에서 오는 것이 최적인지를 구분한 라인의 번호입니다.


이를 통해 최종적으로 구성되는 수도코드는 아래와 같습니다.



위의 수도코드를 확인해보면,

f1[1]과 f2[1]에 enter하는데 필요한 소요시간과 1번 공정을 하는데 소요되는 시간을 더해서 입력합니다.

이후, 2번 공정부터 n번째 공정까지 f1과 f2의 테이블에 적절한 값을 입력할 수 있도록 if문을 통한 처리를 진행합니다.

내부에서는 추가적인 반복문 없이 진행됩니다.

그리고 최종적으로 n번째 공정까지 마무리가 되면 라인에서 빠져나오는 시간을 고려하여 가장 소요시간이 적은 값을 f*에 저장합니다.

이를 통해서 해당 수도코드의 시간 복잡도는 선형시간을 가진다는 것을 알 수 있습니다.

 

또한 최종 과정을 보기위한 출력함수는 아래와 같습니다.



위의 수도코드들을 통해 아래 사진을 보고 그 과정을 하나씩 확인해보시면 이해가 빠를 것 입니다.




이렇게 해서 동적 프로그래밍, 동적 계획법의 두번째 예제인 Assembly Line Scheduling에 대해서 알아보았습니다.

다음 포스팅에서는 동적 프로그래밍의 세번째 예제인 Matrix-chain Multiplication에 대해서 알아보도록 하겠습니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


지난 포스팅에서 동적 프로그래밍(Dynamic Programming)에 대해서 알아보고 그에 대한 예제로 막대자르기(Rod Cut)에 대해서 공부하였습니다.

이번 포스트에서는 막대자르기 예제에서 단순 하향식 재귀표현법과 상향식 방법을 실제로 python코드로 작성해보고 시간을 비교해보도록 하겠습니다.


1. 개요


먼저 이번 포스팅에서 진행할 막대자르기문제에 대한 몇 가지 조건은 아래와 같습니다.


ㄱ. P-table(price table)의 값은 임의의 단조증가 형태

ㄴ. Rod의 길이 값을 4부터 N으로 변화시키면서 Brute-force방법(하향식 재귀 표현)과 DP방법(상향식 방법)으로 최적의 값과 해결 소요 시간을 비교

ㄷ. 소요 시간 비교는 최종적으로 표와 그래프를 이용하여 시각적으로 표현


위의 조건들을 가지고 코드를 작성하는데, 이때 참고하는 수도코드는 각각 아래와 같습니다.


#Brute-force(하향식 재귀 표현)


#DP(상향식 방법)




2. Price table 구성


먼저 조건 ㄱ을 구현하기 위해 P-table(Price table)을 구성하는 함수를 작성합니다.

P-table은 임의의 단조증가 형태를 띄어야 합니다.

먼저 P-table를 알맞게 구성하는 Initprice()라는 함수를 작성하여 값을 price_table.txt 파일로 저장한 다음 이후 해당 파일을 읽어서 사용할 수 있도록 readPriceTable()함수를 구현하겠습니다.


2-1. Initprice()


단조증가 형태를 띄는 P-table은 아래 코드를 통해 구성됩니다.




위의 코드를 통해 생성된 price_table.txt 파일의 일부는 아래와 같습니다.




2-2. readPriceTable()


위에서 작성한 price_table.txt를 이후 코드에서 사용하기 위해 해당 파일을 읽어서 배열로써 반환하는 함수는 아래와 같습니다.




3. Brute-force, 하향식 재귀 표현


위와 같은 수도코드를 통해 Cut-Rod 방법을 구현한 함수는 아래와 같습니다.




위의 코드는 이론상으로 의 시간복잡도를 가집니다.




4. DP, 상향식 방법



위와 같은 수도코드를 통해 Bottom-UP 방법을 구현한 함수는 아래와 같습니다.



위의 코드는 이론상으로 의 시간복잡도를 가집니다.



5. 결과 출력


먼저 위에서 구현한 하향식 재귀 방법과 상향식 방법을 동시에 실행시키면서 각각을 통한 최적의 값과 실행 소요시간을 출력하는 함수를 작성하여 결과를 한눈에 보기 편하도록 하겠습니다.

check(n,price)함수를 구현하였고 매개변수 n은 최대 수익 값을 구하고자 하는 막대의 길이이며 price는 P-table입니다.

또한, n이 값이 증가하였을때 하샹식 재귀방법은 이론적으로 큰 시간 소요를 가질 것으로 예상 되므로 n이 커질때 상향식 방법만 확인하기 위한 checkBtUP(n,price) 함수를 구현하였습니다.

각각의 코드는 아래와 같습니다.



위와 같은 코드를 통해 최종적으로 아래 코드를 실행시킵니다.



이에 따른 결과의 일부는 아래 사진과  같습니다.






6. 시간비교


각각의 값을 txt파일로 기록하여 이를 excel에 옮겨서 표를 구성한 사진과 이를 그래프로 나타낸 결과는 아래 사진들과 같습니다.



위의 표는 n이 4부터 30까지의 대한 각각의 값을 나타냅니다.

두가지 알고리즘에 의한 최적의 값을 비교했을 때, 두 알고리즘 모두 같은 값을 도출하였습니다.

또한 각각의 값은 자르지 않았을 때의 값보다 크거나 같습니다.

아래 첫번째 그래프는 하향식 재귀표현 알고리즘과 상향식 방법 알고리즘에 대한 시간비교를 진행한 것 입니다. 파란색 선은 하향식 재귀 방법의 소요시간을 나타내며 주황색 선은 상향식 방법의 소요시간을 나타냅니다.

이론에서 배운 것과 같이 하향식 재귀 방법이 상향식 방법보다 n이 커질수록 큰 소요시간을 가지는 것을 확인할 수 있습니다.

그 아래 두번째 그래프는 n이 31부터 1000까지의 상향식 방법의 소요시간을 측정한 그래프 입니다.

n이 커질수록 소요시간이 증가되는 것을 볼 수 있습니다.




실습에서 진행되었던 코드 전문은 아래와 같습니다.

코드 전문 보기





이렇게 해서 파이썬을 통한 막대자르기(Rod Cut) 문제의 알고리즘 시간비교를 진행하였습니다.

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

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc