uang's blog

www.acmicpc.net/problem/17472

이 문제는 DFS, MST(최소신장트리) 를 이용해 푸는 문제이다. 질문 게시판을 보니 삼성 코딩테스트 기출문제인듯 하다. 위 문제 풀이 방법 중 핵심은 인접한 셀들을 "섬"으로써 잘 Grouping 하여, 다른 "섬"(group)과의 최단거리를 찾아야 한다. 

일단 필요한 알고리즘들을 생각해보면,

   1. DFS : 섬의 개수 세기

   2. MST(최소신장트리) : 모든 섬들을 연결하는 최단 간선 구하기 

이다.

MST 에는 크루스칼(Kruskal) 알고리즘, 프림(prim) 알고리즘이 있다. 

크루스칼 알고리즘

간선의 가중치를 정렬해 작은 것 부터 차례로 선택해나가는 방법

1. 간선들을 가중치의 오름차순으로 정렬한다
2. 정렬된 간선 중 사이클을 형성하지 않는 간선을 선택
3. 해당 간선을 현재 MST 집합에 추가
4. 1~3 과정을 "|정점 수| - 1" 번 반복  // V 개의 정점을 연결하기 위해 필요한 간선은 V-1개 이므로

프림 알고리즘

하나의 정점을 선택해 가장 가중치가 작은 간선들을 차례로 연결해나가는 방법

1.  시작 노드(어떤 노드든 상관없음) 를 MST 집합에 포함
2.  1단계에서 만들어진 MST 집합에 인접한 노드들 중 최소 간선으로 연결된 노드를 선택해 MST 집합에 포함
3.  1~2 과정을 "|정점 수| - 1" 번 반복  // V 개의 정점을 연결하기 위해 필요한 간선은 V-1개 이므

프림알고리즘의 구현을 위해선 priority_queue(우선순위 큐)가 필요할 수 있지만, 본 문제에서는 간선을 우리가 만들어가며 찾아야하기 때문에 BFS(너비우선탐색)를 통해 찾는 것이 적절하다. 같은 이유로 Kruskal 알고리즘을 사용하기 복잡하다.

대략 알고리즘을 설명하면 다음과 같다.

1. 섬의 갯수 찾기 (DFS)

    - 각 섬의 Grouping을 위해 ID 를 부여한다.

2. 섬의 갯수-1 번 반복하여 다른 그룹의 섬을 잇는 간선 찾기 (BFS)

    - 1번 섬을 기준으로 BFS를 통해 최단거리의 다른 섬(그룹)을 찾으면 1번 그룹에 병합 (Union-Find 개념)

    * 탐색 할 때는 가로/세로 방향 유지

* Union-Find 알고리즘 참고 : https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

소스코드

#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
 
struct node{
    pair<int,int> cur;
    int cnt_bridge, is_vertical;
    node(pair<int,int> cur, int  cnt, int is_v) : cur(cur), cnt_bridge(cnt), is_vertical(is_v)  {};
};
 
int n,m, dx[4]= { -1,1,0,0}, dy[4] = {0,0,-1,1}, arr[11][11];
bool visited[11][11][2];
vector< pair<int,int> > island[7];
 
void find_island(int idx, int y,int x){
    visited[y][x][0] = 1;
    island[idx].push_back(make_pair(y,x));
    arr[y][x] = idx+1;
    for(int i=0;i<4;i++){
        int ny = y + dy[i], nx = x+dx[i];
        if(ny>=0 && nx >=0 && nx < m && ny < n){
            if(!visited[ny][nx][0] && arr[ny][nx]){
                find_island(idx, ny, nx);
            }
        }
    }
}
 
void push_queue(queue< node >& q, int island_idx=1){
    int idx = island_idx-1; // 1번 그룹 
 
    for(int i=0; i< island[idx].size(); i++){
        q.push(node(island[idx][i], 0, -1));
    }
    // printf("push queue #%d, queue_size : %d\n", island_idx, q.size());
}
 
void Union(int found_island_idx){
    int& idx = found_island_idx;
    for(int i=0;i<n; i++){
        for(int j=0; j<m;j++){
            if(arr[i][j] == idx){
                island[0].push_back(make_pair(i,j));
                arr[i][j] = 1;
            }
        }
    }
 
    // printf("union between 1 and %d\n\n", idx);
    // for(int i=0;i<n; i++){
    //     for(int j=0; j<m;j++){
    //         printf("%d ",arr[i][j]);
    //     }
    //     printf("\n");
    // }
}
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0; j<m; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    int cnt_island = 0;
    for(int i=0; i<n;i++){
        for(int j=0; j<m;j++){
            if(!visited[i][j][0] && arr[i][j]){
                find_island(cnt_island, i,j);
                cnt_island += 1;
            }
        }
    }
 
    // printf("\n");
    // for(int i=0; i<n;i++){
    //     for(int j=0; j<m;j++){
    //         printf("%d ", arr[i][j]);
    //     }
    //     printf("\n");
    // }
    // cnt_islend-1 edges are needed to connect all island
    int ans = 0, edges = 0;
    for(int i=0; i<cnt_island-1; i++){
        memset(visited, 0, sizeof(visited));
        queue< node > q;
        push_queue(q, 1); 
 
        while(!q.empty()){
            node cur = q.front(); q.pop();
            int cury = cur.cur.first, curx = cur.cur.second;
 
            // another island check
            if(arr[cury][curx] > 1 && cur.cnt_bridge >= 2) {
                // printf("found another island#%d at (%d,%d): %d\n", arr[cury][curx], cury,curx, cur.cnt_bridge);
                int island_idx = arr[cury][curx];
                ans += cur.cnt_bridge;
                edges += 1;
                Union(island_idx);
                break;
            }
 
            // cannot pass through another island
            if(arr[cury][curx] > 1){
                continue;
            }
 
            if(cur.is_vertical == -1){
                visited[ cury ][ curx ][0] = visited[ cury ][ curx ][1] = 1;
            } else {
                visited[ cury ][ curx ][cur.is_vertical] = 1;
            }
 
            // build  bridge to search island
            for(int d=0; d<4;d++){
                int ny = cury + dy[d], nx = curx + dx[d];
                if(ny >= 0 && nx >=0 && nx < m && ny < n && arr[ny][nx] != 1 && !visited[ny][nx][cury!=ny]){
                    if( cur.is_vertical == -1 ){ // all directions
                        q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), cury != ny));
                    } else if (cur.is_vertical == 1 && cury != ny){
                        q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), 1));
                    } else if (cur.is_vertical == 0 && cury == ny) { // horizontal
                        q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), 0));
                    }
                }
            }
        }
    }
    printf("%d\n", (ans == 0 || edges != cnt_island-1) ? -1 : ans);
    return 0;
}
 

www.acmicpc.net/problem/1305

위 문제는 길이가 N 인 광고판에 문자열 길이가 L 인 광고가 왼쪽 쉬프트를 하며 무한히 나타날 때, 가능한 문자열의 최소 길이를 구하는 문제이다. 즉, 광고판 길이가 6이고 현재 광고판의 문자열이 "aabaaa" 일때, 가능한 문자열 후보는 "aaba", "aaab", "abaa", "aabaa", "abaaa" 등 다양하지만, 가장 짧은 길이는 4이다.

이 문제는 KMP 알고리즘에서 사용하는 pi 배열을 이용하여 풀 수 있다. pi 배열은 접두사(prefix) 와 접미사(suffix)가 같은 부분 문자열 중 가장 길이가 긴 것을 저장한다.

"ABADABC" 라는 문자열이 있을 때, pi는 다음과 같이 저장된다.

KMP는 이 pi배열을 이용해 문자열 검색의 시간 복잡도를 O( |S| * |P| ), (S : 전체 문자열, P : 전체 문자열에서 찾고자하는 패턴(검색) 문자열) 에서 O( |S|+|P| ) 로 줄이는 알고리즘이다.

1305 광고문제는 검색까지는 필요없고, Pi만 배열만 있으면 풀 수 있다.

길이가 N인 광고판과 길이가 L (L <= N) 인 문자열이 있을 때, 앞의 X개의 문자열(진한 파란색)은 광고 문자열 L번째 문자 뒤에 반복된다.

즉, N길이의 광고판 문자열에 대해 pi 를 구한 후, N-pi[N]을 구하면 답을 구할 수 있다.

소스코드

소스는 백준님 풀이 방식을 기반으로 구현했습니다.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
vector<int> get_pi_array(string s){
    int n = s.size();
    vector<int>pi(n);
    pi[0] = 0;
    int j = 0;
    for(int i=1; i < n; i++){
        while(j>0 && s[i] != s[j]){
            j = pi[j-1];
        }
        if(s[i] == s[j]){
            pi[i] = j + 1;
            j += 1;
        } else {
            pi[i] = 0;
        }
    }
    return pi;
}
 
int main(){
    int n;
    string s;
    cin >> n >> s;
    vector<int> pi = get_pi_array(s);
    cout << n - pi[n-1] << '\n';
    return 0;
}

관련 사이트:

bowbowbow.tistory.com/6

m.blog.naver.com/kks227/220917078260

https://www.acmicpc.net/problem/10826

이 문제는 BOJ2407 조합 문제와 같이 피보나치 10000 의 자릿수가 2000 이 넘어가기 때문에 c++ 표준 자료형의 범위로는 표현할 수 없다. 마찬가지로 string 덧셈으로 풀 수 있는데, 이전 BOJ2407 번에서 구현한 string 덧셈이 비효율적이라 시간초과가 난다. 따라서 string 덧셈과정에서 역순으로 += 연산을 최대한 이용할 수 있도록 구현하여 시간제한 안에 풀 수 있도록 구현하였다.

새롭게 안 사실인데, 피보나치 4 문제의 질문 게시글 에서 문자열의 덧셈 방법 s = s + "string" 과 s += "string" 이 다르다는 것을 설명한다. 첫 번째 방법(s = s + "string") 은 string 을 새롭게 복사하기 때문에 O(s.size()^2) 의 시간이 걸린다고 한다. 두 번째 방법은 단순히 이어 붙이기 때문에, 시간적으로 매우 차이가 날 수 있다.

소스코드

https://www.acmicpc.net/problem/1516

이 문제는 위상정렬로 풀 수 있는 문제이다. 위상 정렬은 주로 게임에서 스킬트리와 같은 즉, 선행되어야 하는 작업이 있을 때의 순서를 어떻게 처리해야 빠른지를 풀 때 사용하는 알고리즘이다. 위상정렬의 구현은 그래프 구조에서 in-direction 의 갯수를 저장하는 배열이 가장 핵심이다. 즉 어떤 노드 K 번에 들어오는 간선의 수가 3개가 있을 때, ind[K] = 3 처럼 저장한 뒤, ind[i] 값이 0인 정점부터 큐(queue)에 넣고 순차적으로 탐색해가면 된다.

위 그림으로 설명하면

 1. ind 값이 0 인 1번 3번 노드가 queue에 넣는다.
 2. 큐에 가장 앞에 있는 노드를 방문(1 번) 한 후, 이 노드에 연결된 (2 번으로의)간선을 돌면서 ind[ graph[cur][next] ] 의 값을 -1 해준다.
     ( 그림에선 2번으로의 간선이므로, ind[2]--; )
 3. 만약 2번의 과정을 통해서 ind 값이 0 이 되면(ind[ graph[cur][next] ] == 0) 해당 노드를 queue에 push 한다.
 4. 2~3번을 반복

소스코드

https://www.acmicpc.net/problem/2407

이 문제는 100 C 50 조합 값이 long long int 를 벗어나는 약 30자리 수 정도이기 때문에, 다른 방법으로 덧셈을 계산해야 한다. 따라서 덧셈을 위해 string 클래스를 이용해 문자열끼리의 더하기를 구현하였다.

다음은 100_C_n 의 조합의 결과 : 

(100C1) : 1 + 99 = 100
(100C2) : 99 + 4851 = 4950
(100C3) : 4851 + 156849 = 161700
(100C4) : 156849 + 3764376 = 3921225
(100C5) : 3764376 + 71523144 = 75287520
(100C6) : 71523144 + 1120529256 = 1192052400
(100C7) : 1120529256 + 14887031544 = 16007560800
(100C8) : 14887031544 + 171200862756 = 186087894300
(100C9) : 171200862756 + 1731030945644 = 1902231808400
(100C10) : 1731030945644 + 15579278510796 = 17310309456440
(100C11) : 15579278510796 + 126050526132804 = 141629804643600
(100C12) : 126050526132804 + 924370524973896 = 1050421051106700
(100C13) : 924370524973896 + 6186171974825304 = 7110542499799200
(100C14) : 6186171974825304 + 38000770702498296 = 44186942677323600
(100C15) : 38000770702498296 + 215337700647490344 = 253338471349988640
(100C16) : 215337700647490344 + 1130522928399324306 = 1345860629046814650
(100C17) : 1130522928399324306 + 5519611944537877494 = 6650134872937201800
(100C18) : 5519611944537877494 + 25144898858450330806 = 30664510802988208300
(100C19) : 25144898858450330806 + 107196674080761936594 = 132341572939212267400
(100C20) : 107196674080761936594 + 428786696323047746376 = 535983370403809682970
(100C21) : 428786696323047746376 + 1613054714739084379224 = 2041841411062132125600
(100C22) : 1613054714739084379224 + 5719012170438571889976 = 7332066885177656269200
(100C23) : 5719012170438571889976 + 19146258135816088501224 = 24865270306254660391200
(100C24) : 19146258135816088501224 + 60629817430084280253876 = 79776075565900368755100
(100C25) : 60629817430084280253876 + 181889452290252840761628 = 242519269720337121015504
(100C26) : 181889452290252840761628 + 517685364210719623706172 = 699574816500972464467800
(100C27) : 517685364210719623706172 + 1399667836569723427057428 = 1917353200780443050763600
(100C28) : 1399667836569723427057428 + 3599145865465003098147672 = 4998813702034726525205100
(100C29) : 3599145865465003098147672 + 8811701946483283447189128 = 12410847811948286545336800
(100C30) : 8811701946483283447189128 + 20560637875127661376774632 = 29372339821610944823963760
(100C31) : 20560637875127661376774632 + 45764000431735762419272568 = 66324638306863423796047200
(100C32) : 45764000431735762419272568 + 97248500917438495140954207 = 143012501349174257560226775
(100C33) : 97248500917438495140954207 + 197443926105102399225573693 = 294692427022540894366527900
(100C34) : 197443926105102399225573693 + 383273503615787010261407757 = 580717429720889409486981450
(100C35) : 383273503615787010261407757 + 711793649572175876199757263 = 1095067153187962886461165020
(100C36) : 711793649572175876199757263 + 1265410932572757113244012912 = 1977204582144932989443770175
(100C37) : 1265410932572757113244012912 + 2154618614921181030658724688 = 3420029547493938143902737600
(100C38) : 2154618614921181030658724688 + 3515430371713505892127392912 = 5670048986634686922786117600
(100C39) : 3515430371713505892127392912 + 5498493658321124600506947888 = 9013924030034630492634340800
(100C40) : 5498493658321124600506947888 + 8247740487481686900760421832 = 13746234145802811501267369720
(100C41) : 8247740487481686900760421832 + 11868699725888281149874753368 = 20116440213369968050635175200
(100C42) : 11868699725888281149874753368 + 16390109145274293016493707032 = 28258808871162574166368460400
(100C43) : 16390109145274293016493707032 + 21726423750712434928840495368 = 38116532895986727945334202400
(100C44) : 21726423750712434928840495368 + 27651812046361280818524266832 = 49378235797073715747364762200
(100C45) : 27651812046361280818524266832 + 33796659167774898778196326128 = 61448471214136179596720592960
(100C46) : 33796659167774898778196326128 + 39674339023040098565708730672 = 73470998190814997343905056800
(100C47) : 39674339023040098565708730672 + 44739148260023940935799206928 = 84413487283064039501507937600
(100C48) : 44739148260023940935799206928 + 48467410615025936013782474172 = 93206558875049876949581681100
(100C49) : 48467410615025936013782474172 + 50445672272782096667406248628 = 98913082887808032681188722800
(100C50) : 50445672272782096667406248628 + 50445672272782096667406248628 = 100891344545564193334812497256
(100C51) : 50445672272782096667406248628 + 48467410615025936013782474172 = 98913082887808032681188722800
(100C52) : 48467410615025936013782474172 + 44739148260023940935799206928 = 93206558875049876949581681100
(100C53) : 44739148260023940935799206928 + 39674339023040098565708730672 = 84413487283064039501507937600
(100C54) : 39674339023040098565708730672 + 33796659167774898778196326128 = 73470998190814997343905056800
(100C55) : 33796659167774898778196326128 + 27651812046361280818524266832 = 61448471214136179596720592960
(100C56) : 27651812046361280818524266832 + 21726423750712434928840495368 = 49378235797073715747364762200
(100C57) : 21726423750712434928840495368 + 16390109145274293016493707032 = 38116532895986727945334202400
(100C58) : 16390109145274293016493707032 + 11868699725888281149874753368 = 28258808871162574166368460400
(100C59) : 11868699725888281149874753368 + 8247740487481686900760421832 = 20116440213369968050635175200
(100C60) : 8247740487481686900760421832 + 5498493658321124600506947888 = 13746234145802811501267369720
(100C61) : 5498493658321124600506947888 + 3515430371713505892127392912 = 9013924030034630492634340800
(100C62) : 3515430371713505892127392912 + 2154618614921181030658724688 = 5670048986634686922786117600
(100C63) : 2154618614921181030658724688 + 1265410932572757113244012912 = 3420029547493938143902737600
(100C64) : 1265410932572757113244012912 + 711793649572175876199757263 = 1977204582144932989443770175
(100C65) : 711793649572175876199757263 + 383273503615787010261407757 = 1095067153187962886461165020
(100C66) : 383273503615787010261407757 + 197443926105102399225573693 = 580717429720889409486981450
(100C67) : 197443926105102399225573693 + 97248500917438495140954207 = 294692427022540894366527900
(100C68) : 97248500917438495140954207 + 45764000431735762419272568 = 143012501349174257560226775
(100C69) : 45764000431735762419272568 + 20560637875127661376774632 = 66324638306863423796047200
(100C70) : 20560637875127661376774632 + 8811701946483283447189128 = 29372339821610944823963760
(100C71) : 8811701946483283447189128 + 3599145865465003098147672 = 12410847811948286545336800
(100C72) : 3599145865465003098147672 + 1399667836569723427057428 = 4998813702034726525205100
(100C73) : 1399667836569723427057428 + 517685364210719623706172 = 1917353200780443050763600
(100C74) : 517685364210719623706172 + 181889452290252840761628 = 699574816500972464467800
(100C75) : 181889452290252840761628 + 60629817430084280253876 = 242519269720337121015504
(100C76) : 60629817430084280253876 + 19146258135816088501224 = 79776075565900368755100
(100C77) : 19146258135816088501224 + 5719012170438571889976 = 24865270306254660391200
(100C78) : 5719012170438571889976 + 1613054714739084379224 = 7332066885177656269200
(100C79) : 1613054714739084379224 + 428786696323047746376 = 2041841411062132125600
(100C80) : 428786696323047746376 + 107196674080761936594 = 535983370403809682970
(100C81) : 107196674080761936594 + 25144898858450330806 = 132341572939212267400
(100C82) : 25144898858450330806 + 5519611944537877494 = 30664510802988208300
(100C83) : 5519611944537877494 + 1130522928399324306 = 6650134872937201800
(100C84) : 1130522928399324306 + 215337700647490344 = 1345860629046814650
(100C85) : 215337700647490344 + 38000770702498296 = 253338471349988640
(100C86) : 38000770702498296 + 6186171974825304 = 44186942677323600
(100C87) : 6186171974825304 + 924370524973896 = 7110542499799200
(100C88) : 924370524973896 + 126050526132804 = 1050421051106700
(100C89) : 126050526132804 + 15579278510796 = 141629804643600
(100C90) : 15579278510796 + 1731030945644 = 17310309456440
(100C91) : 1731030945644 + 171200862756 = 1902231808400
(100C92) : 171200862756 + 14887031544 = 186087894300
(100C93) : 14887031544 + 1120529256 = 16007560800
(100C94) : 1120529256 + 71523144 = 1192052400
(100C95) : 71523144 + 3764376 = 75287520
(100C96) : 3764376 + 156849 = 3921225
(100C97) : 156849 + 4851 = 161700
(100C98) : 4851 + 99 = 4950
(100C99) : 99 + 1 = 100

소스코드

먼저 용어를 간단히 정리하자면, LCS(Longest Common Subsequence) 로 Subsequence 는 부분 수열이기 때문에, 꼭 연속적인 문자열일 필요가 없다. 만약 substring 이면 연속적인 문자열이다.

O(N^2)

https://www.acmicpc.net/problem/9251

DP 정의는 다음과 같다.

dp[p][q] : 첫 번째 문자열 p, 두 번째 문자열 q 위치까지의 LCS 길이

  if string_1 [p] == string_2 [q]:
       dp[p][q] = dp[p-1][q-1] + 1
  else :
       dp[p][q] = max( dp[p-1][q], dp[p][q-1] )

 위 dp 정의에 따라 두 문자열의 dp 배열 저장 값(그림)을 보면 이해하기 쉽다.

# Top-down

# Bottom-up

# 9251 LCS 소스 코드

O(N^2), LCS 문자열 출력

LCS 문자열까지 출력하기 위해선 dp 의 마지막 인덱스(dp[s1.length()-1][s2.length()-1]) 부터 0,0 까지 이동해가며, 문자열을 추적해야한다.

https://www.acmicpc.net/problem/9252

9252 LCS 2 소스코드

BOJ 1958 LCS 3

https://www.acmicpc.net/problem/1958

이 문제는 문자열 3개의 LCS 문제이며, dp를 2차원에서 3차원으로 확장하여 풀면 된다.

O(n log n) 방법

https://www.acmicpc.net/problem/13711

이 문제는 n 의 길이가 100,000 까지 이므로, 기존의 O(n^2) 방법으로는 풀 수 없다. O(n log n)으로 풀기 위해선 조건이 필요한데, 문제에 쓰여있듯이 하나의 문자는 한 번만 나타나야 한다. 한 번씩 나타날 때, 이 문제를 LIS 로 응용해서 풀 수 있는데, 방법은 다음과 같다.

 1. 수열 A 의 값 A[i] 을 인덱스 배열 C에 저장한다. C[ A[i] ] = i
 2. 수열 B의 값을 A 값에 따른 인덱스 배열로 치환한다. B[i] = C[ B[i] ]
 3. B 배열에 LIS 를 구한다.

즉, A 값의 인덱스로 B 배열 값을 치환한 뒤, LIS 를 구하면 두 문자열의 LCS가 된다. 

이 문제 시리즈는 출력 값이 길이만 출력하는지, 긴 수열 또한 출력해야 하는지에 따라 풀이 방법이 달라지고, n 조건에 따라 풀이 방법이 달라진다.

1 단계 O(n^2), 가장 긴 수열의 길이만 출력

https://www.acmicpc.net/problem/11053

이 문제는 입력 조건 n 의 크기에 따라 풀이 방법이 달라지고, 먼저 11053 번 문제는 n 조건이 1000 까지 이므로 n^2 만에 풀이 가능하며, 이전 배열값을 다시 참조하면서, 가장 긴 값을 저장하면 된다.

2 단계 O( n log n), 가장 긴 수열의 길이만 출력

https://www.acmicpc.net/problem/12015

 두 번째 문제는 1 단계 문제와 같이 길이만 출력하지만, n의 조건이 크기 때문에 O(N^2)만에 해결할 수 없다. 따라서 이 문제는 1번 문제 풀이에서 가장 긴 수열의 길이를 탐색해가는 과정을 log n으로 줄여야 풀 수 있다. 

 풀이 방법은 하나의 벡터를 정의하여, 가장 마지막 값이 현재 탐색하는 값보다 클 경우 이진 탐색을 통해 현재 탐색 값이 들어갈 위치를 찾아 수정한다. 주의할 점은 이렇게 풀었을 때, 정의한 벡터 안의 값이 가장 긴 부분 수열이라고 보장하지 않는다.

3단계, O(N^2) 수열까지 출력

https://www.acmicpc.net/problem/14002

이 문제는 가장 긴 수열의 길이와 더불어 긴 수열까지 모두 출력해야 한다. 위에서 말했듯이 2단계 풀이로는 가장 긴 수열이라고 보장하지 않기 때문에 풀 수 없다. 다행히 이 문제는 다시 n 조건이 작아 졌기 때문에, 각 배열 값을 참조하면서 현재까지 가장 긴 수열들을 모두 저장할 수 있다.

4단계 O(n log n), 수열까지 출력

https://www.acmicpc.net/problem/14003

마지막은 n 조건도 커지고, 정답 수열까지 출력해야 하는 문제이다. 이 문제를 풀기 위해선 2번째 문제 풀이를 응용하여 lower_bound(이진탐색)으로 찾은 인덱스 값을 따로 저장해 풀 수 있다. 마지막 출력 시 뒤에서 부터 정답 수열 길이 값과 매칭되는 인덱스 값을 순차적으로 찾으며 출력하면 된다.

결국 4단계 풀이 방법만 기억하고 있으면, 모두 풀 수 있다.

이 문제는 동적계획법(DP)으로 풀 수 있는 문제이다. 그 이유는 완전한 알약 갯수와 반쪽 짜리 알약 갯수가 주어질 때, 문자열의 경우의 수는 일정하기 때문이다. 따라서 DP는 다음과 같이 정의 할  수 있다.

dp[w][h] = 완전한 알약이 w 개 있고,  반쪽 짜리 알약이 h 개 있을 때, 문자열의 경우의 수

dp[w][h] = dp[w-1][h+1]  +  dp[w][h-1]

Top-Down

Bottom-Up

이 문제는 초기화만 잘 해준다면 Top-Down 방식과 코드가 큰 차이가 없이 Bottom-Up 또한 꽤 직관적인 코드가 짜여진다.

전체 소스 코드

이 문제는 다이나믹 프로그래밍(동적계획법, DP) 문제이다. 나는 평소에 Top-down 방식으로 구현하는 것이 익숙해, bottom-up 방식의 구현을 잘 구현하지 못한다.. 그래서 bottom-up 방식으로도 구현하는 연습해야겠다고 생각해서 오랜만에 DP 문제를 찾았다.

DP 는 큰 문제를 작은 문제로 나누어푸는데, 분할정복과 다른 점은 DP는 작은 문제로 나누어 풀 때, 작은 문제들의 결과가 항상 동일하고 반복이 일어난다. 작은 문제들의 일정한 결과를 이용해 큰 문제를 해결하는 과정이라고 볼 수 있다. 따라서, 작은 문제들의 일정한 결과 값을 저장하기 위해 Memoization 을 하며, 같은 작은 문제를 만났을 때 이미 한 번 해결했던 문제라면 저장해놓은 값을 이용해 반복 수행 횟수를 줄일 수 있다.

Top-Down

먼저  Top-Down 방식의 풀이에서는, DP를 다음과 같이 정의한다.

dp[p][q] = q 만큼의 무게를 들 수 있을 때,  p 번째의 물건을 선택해 얻을 수 있는 최대의 가치

이렇게 정의하면, 

dp[p][q] = max( dp[p-1][q] ,  dp[p-1][ q - weight[p] ] + value[p] )

처럼 p 번째 물건을 선택하지 않은 경우와 선택한 경우 모두 고려할 수 있다.

기저조건(재귀의 탈출조건) 은 p 번째 물건이 0~n-1 번의 물건 개수 범위를 넘어설 때이다. Top-down 방식의 구현은 다음과 같다.

Bottom-Up

다음은 반복문을 이용해 구현하는 Bottom-Up 방법으로 풀어보면, 마찬가지로 2차원의 배열이 필요하다. 익숙치 않아서 시간이 꽤 걸렸다.

DP의 정의는 같으며, 내가 구현한 방식은 다음과 같다.

위 문제의 예제는 너무 쉽기 때문에, 다음 예제를 이용해 설명하면 다음과 같다.

4 20
6 13
2 5
3 9
10 20

4개의 물건이 있으며 무게는 7 까지 가능하기 때문에, 배열은 dp[4][7] 크기가 필요하다.

dp 에는 i 번째 물건까지 고려했을 때, w 무게에서의 최대 가치를 저장한다. 

즉,

무게는 0~20 까지 모두 출력되었다.  dp[1] 은 첫 번째 물건만을 고려했을 때 까지의 가능한 최대 가치를 보여주며, dp[2]는 두 번째 물건 까지 고려했을 때의 가치이다. 두 번째 물건의 무게는 2로 인덱스 2번 부터 무게 5가 채워지며, 무게 6부터는  첫 번째 물건의 가치가 더 크기 때문에 13이 유지되며, 두 무게를 합친 8 무게부터는 두 가치를 합친 값이 저장되기 시작한다. 

전체 소스 코드

N과 M 수열 문제 시리즈를 하나의 포스트에 정리하려 한다.

수열을 출력하는데, 중복 숫자의 뒤집힌 수열을 포함하는지에 따라 구현 방법이 달라진다.

BOJ 15649 N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

이 문제는 같은 숫자의 뒤집힌 수열을 포함한다(ex: 1 4,  4 1)

재귀함수를 이용해 백트래킹으로 1~N 까지 숫자를 순차적으로 M개 출력하여 풀 수 있다.

N과 M(1) 소스코드

BOJ 15650 N과 M (2)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

이 문제는 같은 숫자의 뒤집힌 수열을 포함하지 않는다. 한 번 나온 숫자의 조합은 한 번만 출력된다.

이런 문제는 순열로 풀 수 있다.

N과 M (2) 소스코드