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

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

댓글을 달아 주세요