혜아의 아무말

Logical Thinking 게시글의 현재까지의 제목과 게시물 링크를 모아놓고, 새로운 게시글이 생길 때 마다 업데이트 하도록 하겠다.

[Logical Thinking] 1. 수학적 귀납법

[Logical Thinking] 2. 루프 불변조건(Loop-invariant)

[Logical Thinking] 3. 동적 계획법

[Logical Thinking] 4. 시간복잡도

동적 계획법(Dynamic Programming)은 프로그래밍을 할 때 생기는 문제를 작은 문제들로 나눠서 풀고, 그것을 합치는 방법이다. 그 과정에서 이미 풀어봤던 문제가 발생하면, 문제를 다시 풀지 않고, 예전에 풀었던 정보를 가져오는 방법이다. 이것 때문에 분할 정복과는 다른 면이 있다. 글들은 최대한 이해하기 쉽게 작성하려고 했다.

동적 계획법

동적 계획법을 최대한 쉽게 설명해 보려고 노력 했고, 내가 할 수 있는 제일 쉬운 설명을 가져왔다. 숫자를 세어 보도록 하자, 첫번째 줄에는 1이 몇개 있는가?

1 1 1 1 1 1 1 1 1 1

아마 대부분이 세어 보지 않았을 거라고 생각하지만, 1이 10개가 있다. 그러면 여기서 1을 하나 더 그었다고 생각해 보자.

1 1 1 1 1 1 1 1 1 1 1

아래에서는 1이 몇개 있는가? 이것은 아마 이 문장을 보기 전에 답을 알고 있을 것이다. 11개이다. 우리는, 11개라는 답을 얻어낼 때, 처음부터 다시 세어본 것이 아니라 이전에 세었던 결과들을 미리 가져 온 것이다. 이것은 동적 계획법의 기본이 된다. 문제들을 비슷한 문제들로 바꾸고, 똑같은 문제에 대한 답을 미리 기억 해 놓는다.

최장 증가 부분 수열과 최적 부분구조(Optimal Substructure)

그림으로 그린 LIS문제, 3 4 5 6은 증가하는 수열이다.

동적 계획법의 예를 들어 보기 위해서, 우리는 간단한 하나의 문제를 가지고 올 것이다. 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이라는 문제는 굉장히 흔하게 알려진 문제이다.

임의의 수열을 하나 가지고 오자 예를들면 길이 10의 수열 "3 1 4 1 5 9 2 6 5 3"이 있다고 하자. 우리는 이 숫자들을 적당히 차례로 골라서 가장 길고, 증가하는 숫자들을 찾으려고 한다. 예를 들면 "3 1 4 1 5 9 2 6 5 3" 에서 굵게 표시된 "3 4 5 6"은, 증가하는 수열이고 순서를 보존한다. 이것 보다 더 큰 증가하는 부분 수열은 찾을 수 없기 때문에 "3 4 5 6"은 최장 증가 부분 수열이다. 이것이 유일하지는 않다. 예를들면 마지막 숫자만 9로 바꾼 "3 4 5 9"도 최장 증가 부분 수열이다. 하지만, 이 수열들의 길이는 4로 같다. 우리는 이 길이를 구하는 것에 초점을 맞추어 볼 것이다.

우리는 다음의 정리를 증명하려고 한다.

"(길이 2 이상의) i번째 수로 끝나는 증가 부분 수열중 가장 길이가 긴 것은, 1번째 수로 끝나는 증가 부분 수열 중 가장 길이가 긴 것 또는 2번째 수로 끝나는 증가 부분 수열 중 가장 길이가 긴 것 또는 ... i-1번째 수로 끝나는 증가 부분 수열을 포함하고 있다."

라는 것이다. 즉, "최장 증가 부분 수열"은, 더 작은 최장 증가 부분 수열을 포함하고 있다는 뜻이다.

증명은 간단하다. i번째 수로 끝나는 증가 부분 수열에 마지막에서 두번째 원소가 j번째 수라고 하자. (첫번째 원소를 x번째 수라고 해서, 수열을 a_x, ..., a_j, a_i로 나타내자.) 만약, 이 증가 부분 수열이 j번째 수로 끝나는 증가 부분 수열을 포함하고 있지 않다면 우리는 수열의 앞부분을 교체해서 더 길게 만들 수 있고, 우리가 "가장 길다"라고 말한 것에 모순이다. (j번째 수로 끝나는 최장 증가 부분 수열인 (a_y, ..., a_j)가 (a_x, ..., a_j)보다 더 길면, (a_y, ..., a_j, a_i)가 (a_x, ..., a_j, a_i) 보다 더 길다.) 그러므로, 본 명제가 증명되었다.

어쨌든 결론은 우리는 최장 증가 부분 수열을 문제를 풀 때, 큰 문제의 답에는 작은 문제의 답이 들어 있다는 것이다. 이것을 최적 부분 구조(Optimal Substructure)라고 말하고, 작은 문제를 풀고 그것을 이용할 수 있다는 것이다. 이것을 토대로 우리는 코드를 짜 볼 수 있다.

// 배열 A가 주어졌을 때, M번째 원소로 끝나는 최장 증가 부분수열의 길이를 구한다.
int solve(int M, const int A[])
{
    // 자기 자신이 유일한 최장 증가 부분 수열인 경우
    int ans = 0; 

    // 부분 문제를 답으로 가지고 있다.
    // i번째 수열을 사용하려면, A[M]을 덧붙일 수 있어야 한다.
    // 그래서 A[i] < A[M]일 경우에만, 문제의 답을 가져온다.
    for(int i=0; i<M; ++i)
        if(A[i] < A[M]) 
            ans = std::max(ans, solve(i, A) + 1);

    return ans; 
}

int LIS(int N, const int A[])
{
    // 모든 숫자에 대해서, 그 숫자로 끝나는 최장 증가 부분 수열의 길이를 구한다.
    // 그 중 최댓값이 전체에서의 최장 증가 부분 수열이다. 
    int ans = 0;
    for(int i=0; i<N; ++i)
        ans = std::max(ans, solve(i, A));
 
    return ans;
}

부분문제 반복(Overlapping Subproblem)

위의 코드를 실제로 실행 시켜 보면, 굉장히 느릴 것이다. 왜냐하면, 우리는 solve(1, A)를 호출 할 때도, solve(2, A)를 호출할 때에도 계속 solve(0, A)를 호출 할 수 있기 때문이다. 하지만, 우리는 여러번 실행 시켜봐도 답이 변하지 않는다는 사실을 알고 있다. (코드가 어떤 경우에도 결정적이고, 외부에 있는 변수를 바꾸지 않는다.) 그래서 우리는 몇가지 트릭을 써보려고 한다. 만약에 우리가 한번 계산한 값이면, 다시 계산할 필요가 없고, 이 값을 저장시켜 놓는 것이다. 우리는 그 배열의 이름을 dp라고 정할 것이다.: 코드는 다음과 같다.

int *dp;
int solve(const int M, const int A[])
{
    // 이미 계산된 값일 경우, 그 값을 그대로 쓴다.
    if(dp[M] != -1) return dp[M];
    int ans = 0; 
    
    // 부분 문제를 답으로 가지고 있다.
    for(int i=0; i<N; ++i)
        if(A[i] < A[N])
            ans = std::max(ans, solve(i, A) + 1);
 
    // 계산된 값을 저장해 놓는다.
    dp[M] = ans; 
    return ans; 
}

int LIS(const int N, const int A[])
{
    // dp배열을 -1로 채운다.
    // 여기서 -1은 우리가 아직 계산을 해 보지 않은 값이란 의미이다.
    dp = new int[N]; fill(dp, dp+N, -1);
    
    int ans = 0;
    for(int i=0; i<N; ++i)
        ans = std::max(ans, solve(i, A));
  
    delete[] dp;
    return ans;
}

이 방법을 쓰면, 우리는 여러번의 같은 코드가 실행되는 상황에서 한번만 그 문제를 계산하고, 나머지는 있는 값을 그대로 가져오는 것으로 풀 수 있다. 즉, 여러번의 문제가 반복되는 상황에서(부분문제 반복) 중복된 계산을 하지 않는다. 이 코드를, solve함수를 명시적으로 만들지 않고, 암시적으로 만들면 다음과 같은 코드가 된다.

int LIS(const int N, const int A[])
{
    int* dp = new int[N];
    int ans = 0; //LIS 함수에서의 ans 값이다.
    for(int i=0; i<N; ++i)
    {
        dp[i] = 0; //solve 함수에서의 ans 값이다.
        for(int j=0; j<i; ++j)
            if(A[j] < A[i])
                dp[i] = std::max(dp[i], dp[j] + 1);

        ans = std::max(ans, A[i]);
    }
    delete[] dp;
    return ans;
}

우리가 이런 코드를 만들 수 있는 이유는 위에서 solve(i, A)가 계산 될 시점에는, solve(0, A), solve(1, A), ..., solve(i-1, A)가 모두 계산 되어 있기 때문이다. 즉, 우리가 solve의 계산이 수행되는 순서를 알고 있기 때문이다. 그렇기 때문에, dp 배열의 값들을 안전하게 이용할 수 있다.

이 구역에 있는 두가지 코드는 동적 계획법을 계산하는 같은 역할을 하는 서로 다른 코드이다. 두 방법의 장단점이 모두 있으니, 상황에 따라 쓰면 좋다. 첫번째 방법의 좋은 점은, 필요 없는 dp값을 계산하지 않는 다는 점과, solve가 호출되는 순서를 알 필요가 없다는 것이다. 두번째 방법의 좋은 점은, 함수의 오버헤드가 없어서 실행 속도가 굉장히 빠르다는 점이다. 그리고 배열의 식을 그대로 사용하기 때문에 다양한 최적화를 하기 쉽다는 것이다.

동적계획법의 방법과 예제에 대해서 알아 보았다. 이 문제는, 현실의 문제를 푸는데도 굉장히 많이 이용된다. 대부분의 문제가 최적 부분구조와 부분문제 반복이라는 구조를 가지고, 문제를 변형하면 DP를 적용하기 쉬운 형태가 된다. 특히 bit-DP라는 방법이 현실의 문제를 푸는 방법과 많이 유사하다. 다양한 테크닉은 이 글의 범위를 초과하니 따로 포스트를 작성하는 것으로 하겠다. 다음에는 시간복잡도에 대한 포스트를 작성하도록 하겠다. 아래에 풀어볼만한 연습문제를 남겨 놓겠다. 풀이 등에 대한 질문이 있거나, 게시글에 개선할 사항은 덧글로 남겨줬으면 한다. 참고로 5번 문제는 Fenwick Tree라는 자료구조를 알고 있는 사람이 풀어 보았으면 좋겠다.

1. https://www.acmicpc.net/problem/1463

2. https://www.acmicpc.net/problem/11726

3. https://www.acmicpc.net/problem/1932

4. 그래프 문제중에, "단순 최장 경로"라는 문제가 있다. 이것은, 그래프에서 정점을 중복해서 지나지 않는 최장경로를 찾는 문제다. 이 문제는 정점에 대한 동적 계획법으로 풀리지 않는다. 왜 풀리지 않는가 설명하라.

5. 그런 반면에, 최단경로를 구하는 문제는 동적 계획법으로 매우 잘 풀린다. (모든 간선의 길이가 양수 일 때) 동적 계획법으로 그래프의 모든 정점쌍간의 최단거리를 구하는 알고리즘을 만들어라.

6. 가장 마지막의 LIS함수를 Fenwick Tree를 사용하여 O(n log n)으로 최적화 하여라.

이제까지의 모든 Logical Thinking 게시글 보기: http://blog.kyouko.moe/8

최근에 소녀전선에서 거지런을 많이 돌다 보니, 쓰기 적당한 거지런 루트가 4개 정도 있는 것 같다. (4-3E, 0-2, 5-2N, 6-3N) 각각 거지런들과 작전보고서를 함께 정리 해 보려고 한다.

작전보고서

작전보고서는 한 개를 만드는데에 전지 3개를 소모하며, 하나당 1500개의 경험치를 준다. 10렙, 30렙, 70렙. 90렙, 100렙을 만드는 데에 각각 2, 15, 235, 659, 1088개의 작전보고서가 필요하다. 작전 보고서는 편제 수에 영향을 작지 않으므로, 편제가 작을 수록 (상대적으로) 효과적이며, 나는 작전보고서 15개를 먹여서 3링을 찍은 이후에 시작하는 편이다.

0-2 거지런

0-2 거지런은 최종 컨텐츠라고도 알려져 있다. 딜러를 G11/SOPMOD/FAL/HK416 같은 하나 빼고 유탄 계열딜러를 쓰고, 탱커를 M16A1을 써서 도는 거지런이다. 핸드건을 하나 넣어서 딜러의 빠른 딜링을 도와주는게 좋다. 탱커와 딜러를 제외하고 3명의 승객을 태울 수 있다. 수복을 포함하여 승객이 3-4링일 때, 전투당 쓰는 인탄식부는 대략 70/60/36/7이고, 경험치는 588/490 * 2(2.5)이고, 총 경험치는 7840 * 2(2.5) = 15680(19600)이다. 한번 전투 할 때 쓰는 시간은 대략 3분정도이다. 코어벌이도 같이 할 수 있고 자유 경험치도 잘 오르기 때문에 꽤나 선호되는 거지런이다.

4-3E 거지런

가장 처음으로 접할 수 있는 4-3E 거지런이다. 딜러를 4링크 혹은 5링크 AR을 두고, 탱커를 5링크 또는 키울 손님을써서 도는 거지런이다. 탱커를 포함하여 4명의 승객을 태울 수 있다. 수복을 포함하여 승객이 3-4링일 때, 전투당 쓰는 인탄식부는 대략 55/48/24/5이고, 경험치는 444/370 * 2(2.5)이고, 총 경험치는 6216 * 2(2.5) = 12432(15540)이다. 75~84렙 까지는 경험치 감소가 있어서, 받는 경험치량이 4972*2.5=12430, 85~94렙까지는 3729*2.5=9323이다. 한번 전투 할 때 쓰는 시간은 대략 2분정도이다. 저렙의 딜러들을 꽤나 빠르게 키울 수 있고, 4링 딜러를 쓸 경우 딜러도 육성을 할 수 있기 때문에 그럴 경우에 가장 효율이 좋은 거지런이다.

5-2N 거지런

머신건을 쓰는 야간전 거지런이다, 탱커를 두지 않으며, 딜러를 4링크 MG하나를 두고, 4명의 승객을 태우는 거지런이다. (사실 MG육성도 필요하기 때문에 자기 자신도 태운다고 봐도 된다). 탄통을 이용해서 탄약을 12까지 올려주어야 한다. 탱커가 없기 때문에 수복이 없다. 승객이 3-4링일 때, 전투당 쓰는 인탄식부는 대략 45/46/15/0이고, 경험치는 624(MVP)/576/480 * 2(2.5)이고, 총 경험치는 5280 * 2(2.5) = 10560(13200)이다. 딜러를 빼면 4032*2(2.5) = 8064(10080)이다. 한 번 전투 할 때 쓰는 시간은 대략 1분 정도이다. (전투를 시작하기 전에 제대편성 기능으로 딜러를 바꾸면 좀 더 시간을 단축할 수 있다.) 두번째 전투때 앞열에 있는 인형들을 퇴각해 줘야하고, 5-1N을 뚫고 스토리를 보지 않을면 5-2N을 뚫어야 하는등 여러 준비가 필요하고 꽤나 힘든 점도 많지만, 장비를 얻어서 강화재료로 쓸 수 있다는 좋은 점이 있다.

6-3N 거지런

머신건을 쓰는 야간전 거지런이다, 탱커를 두지 않고, 딜러를 5링크 MG하나를 두고, 4명의 승객을 태우는 거지런이다. 탄통을 이용하여 탄약을 11까지 올려주어야 한다. 탱커가 없기 때문에 수복이 없다. 승객이 3-4링일 때, 전투당 쓰는 인탄식부는 대략 50/56/27/0이고, 경험치는 600/500 * 2(2.5)이고, 총 경험치는 4200 * 2(2.5) = 8400(10500)이다. 한 번 전투 할 때 쓰는 시간은 대략 1분 30초 정도이다.  5-2N과 비교해 퇴각컨이 필요 없지만, 한 턴을 더 보내야 한다. 장비를 얻어서 강화재료로 쓸 수 있다. 컨트롤 할 필요가 없다는 점 때문에 선호되는 거지런이다.

거지런은 결국에는 제일 효율적인 방법을 찾아서 돌게 되는데, 내가 느낀것은 초반에 30렙까지 작전보고서를 먹여서 키운 다음에 0-2거지런과 6-3N거지런을 기본적으로 돌고, 4링 AR을 키울 때는 4-3E, 머신건을 키울 때는 5-2N, 섞어서 키우는게 제일 좋은 것 같다. (폰 성능이 안 좋다 보니 휴대폰으로 할 때는 5-2N대신 6-3N을 선호하는 편이다.) 코어 벌이나 장비 벌이가 필요할 때 마다, 퀘스트가 나올 때 마다 필요한 것을 섞어서 해주면 좋지 않을까 싶다.