uang's blog

먼저 용어를 간단히 정리하자면, 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) 소스코드

이 문제는 유명한 퍼즐인 스도쿠를 구현하면 된다.

스도쿠가 풀리는 입력만 주어지기 때문에 퍼즐을 완성하는 알고리즘만 잘 구현한다면 꽤 쉽게 풀 수 있다.

실제 스도쿠 퍼즐을 사람이 풀기 위해선 다양한 전략, 기법이 필요하지만 컴퓨터가 풀기 위해선 가능한 숫자들을 다 try & error 하는 식으로 해도 빠르게 풀 수 있기 때문에, 백트래킹 + 주먹구구식 대입으로 구현하면 될 것 같다.

문제는 효율적인 백트랙킹을 위해 데이터를 어떤식으로 저장해야 하는가이다.

각 빈칸에 1~9 의 숫자가 들어갈 수 있는지 확인을 위해, row(열), col(행), box(정사각형) bool 타입 배열에 이미 들어간 숫자를 저장하였고, 각 빈칸에 들어갈 수 있는 모든 숫자 후보들을 다 저장하기 위해 2차원 벡터를 이용하였다.

vector< vector< pair< pair<int,int> ,int> > > v;

안쪽 pair<int,int>      : y,x 좌표

바깥쪽 pair의 second : 가능한 숫자 후보

이렇게하면 안쪽 벡터는 같은 빈 칸의 가능한 모든 숫자 후보를 모두  저장할 수 있다.

데이터만 잘 저장해놓으면 재귀함수를 이용해 쉽게 백트래킹을 구현하여 풀 수 있다.

소스코드

#include<stdio.h>
#include<vector>
using namespace std;

int board[10][10];
bool cols[10][10], rows[10][10], box[10][10];
vector< vector< pair< pair<int,int> ,int> > > v;

bool chk(int y,int x, int num){
    if(rows[y][num] || cols[x][num] || box[3*(y/3) + (x/3)][num]){
        return false;
    }
    return true;
}

bool solve(int p){
    if(p == v.size()){
        return true;
    }

    for(int i=0; i<v[p].size(); i++){
        int y = v[p][i].first.first, x = v[p][i].first.second, num = v[p][i].second;
        if(chk(y,x,num)){
            rows[y][num] = cols[x][num] = box[3*(y/3)+(x/3)][num] = true;
            board[y][x] = num;
            
            if(solve(p+1)){
                return true;
            }
            
            rows[y][num] = cols[x][num] = box[3*(y/3)+(x/3)][num] = false;
            board[y][x] = 0;
        }
    }
    return false;
}
int main(){
    
    for(int i=0;i<9;i++){
        for(int j=0;j<9; j++){
            scanf("%d", &board[i][j]);
            if(board[i][j] != 0){
                rows[i][board[i][j]] = cols[j][board[i][j]] = box[3*(i/3) + (j/3)][board[i][j]] = true;
            }
        }
    }
    for(int i=0;i<9;i++){
        for(int j=0;j<9; j++){
            if(board[i][j] == 0){
                vector< pair< pair<int,int>, int> > tmp;
                for(int num=1; num<=9; num++){
                    if(chk(i,j, num)){
                        tmp.push_back(make_pair( make_pair(i,j), num));
                    }
                }
                v.push_back(tmp);
            }
        }
    }

    solve(0);

    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            printf("%d ",  board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

이 문제는 BFS 를 이용해 푸는 미로 문제의 응용버전이라고 볼 수 있다.

이 문제만의 특징은 'A'~'F' 의 문이 있고, 문을 열기 위해선 각 알파벳에 맞는 소문자 'a'~'f' 열쇠를 가지고 있으면 통과할 수 있다.

다행히 문과 열쇠의 종류가 6개 밖에 안되기 때문에, 비트마스크를 이용해 저장할 수 있고

주의할 점은 지나온 길을 다시 가지 않기 위한 visited 변수는 키의 보유 상황에 따라 갈 수 있는 길이 다르기 때문에 이를 고려해야한다.

 소스코드

 풀이 방법

이 문제는 두 지점 사이의 최소 거울 수를 구하는 문제로, 평소 두 지점의 최단거리를 구할 때 사용하는 BFS 를 응용해 "거리" 대신 "거울 수(방향 전환이 일어나는 수)" 를 사용하여 풀 수 있다고 생각했다.

단순 좌표 (y, x) 뿐만 아니라, 사용된 거울 수 및 이동해온 방향 정보가 필요하므로 새로운 구조체를 정의한다.

struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};

이동해온 방향(p_dir)을 저장하는 이유는 거울이 사용되는 지점이 방향이 전환되는 시점이기 때문에, 현재 좌표가 어느 방향에서 왔는지 확인하기 위해 필요하다.

이 구조체를 이용해 사용된 거울 수(num) 이 가장 작은 순으로 queue 에서 가져오기 위해 우선순위 큐를 사용한다.

 우선순위 큐의 Comparator 정의

내가 정의한 구조체에서 max-heap 으로 사용할지  min-heap 으로 사용하지 결정하기 위해 compartor를 정의해야 한다.

방법은 구사과 님의 블로그에 자세히 설명돼있다.

풀이에 사용된 방법은 구조체를 이용해 operator() 를 정의해 사용했다.

struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};

// 중략

priority_queue< cell, vector<cell>, cmp > pq;

* 참고로 greater 는 작은 값을 먼저, less 는 큰 값을 먼저 리턴한다.

* a.num > b.num 는 greater 와 같고, a.num < b.num 은 less 와 같다.

이렇게 정의된 우선순위 큐를 이용하면, 시작지점에서 거울을 사용하지 않고 최대한 이동하여 탐색한 후,

거울  1개, 2개, k개 사용해서 이동할 수 있는 위치를 순차적으로 탐색할 수 있다.

 소스코드

#include<stdio.h>
#include<vector>
#include<queue>
 
using namespace std;
 
struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};
struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};
 
/*
bool operator<(const struct cell a, const strcut cell b){
    return a.num > b.num;
}
*/
int w,h, sy=-1,sx=-1, dy,dx;
int dix[4] = {-1,1,0,0}, diy[4] = {0,0, -1, 1};
char board[111][111];
bool visited[111][111];
bool dir_check(int a, int b){
    return (a<2 && b<2) || (a>=2 && b>=2)  || a == -1;
}
int main(){
    scanf("%d%d",&w,&h);
 
    for(int i=0;i<h;i++){
        scanf("%s", board[i]);
        for(int j=0;j<w;j++){
            if(board[i][j] == 'C'){
                if(sy != -1 && sx != -1){
                    dy = i, dx = j;
                } else {
                    sy = i, sx  = j;
                }
            }
        }
    }
    priority_queue< cell, vector<cell>, cmp > pq;
    // priority_queue< cell, vector<cell>, greater<cell> > pq;
 
    pq.push(cell(sy, sx, 0, -1));
    while(!pq.empty()){
        cell cur = pq.top();
        pq.pop();
        visited[cur.y][cur.x] = 1;
        if(cur.y == dy && cur.x == dx){
            printf("%d\n", cur.num);
            break;
        }
        for(int i=0;i<4;i++){
            int ny = cur.y + diy[i], nx = cur.x + dix[i];
            if(ny >=0 && nx >=0 && nx < w && ny < h) {
                if(!visited[ny][nx] && board[ny][nx] != '*'){
                    // printf("\tnext : (%d, %d) num : %d, is_plus? : %d\n", ny,nx, cur.num, !dir_check(cur.p_dir, i));
                    pq.push(cell(ny, nx, cur.num + (dir_check(cur.p_dir, i) ? 0 : 1), i));
                }
            }
        }
    }
    return 0;
}

"구간 합" 유형 + 값 수정 쿼리 가 있는 문제는 "세그먼트 트리" 를 이용해 풀어야 한다.

구간 합은 보통 prefix sum(psum) 배열을 이용해 [a, b] 의 구간합을 psum[b] - psum[a-1] 로 풀 수 있다.

하지만 구간 값이 변경되는 "K 개의 수정 쿼리"가 있을 때는, 매 수정마다 N 크기의 배열을 다시 계산해야하기 때문에,

전체 복잡도가 O(K*N) 이 된다.

세그먼트 트리는 

     Leaf node      : 배열 값

     Internal node : 자식노드들의 구간 합

을 저장하여, 수정을 O(logN) 만에, 구간 합 계산 또한 O(logN) 번 만에 수행할 수 있는 자료구조이다.

자세한 내용은 백준님 블로그에 설명되어 있다.

이 문제는 값 수정 쿼리가 있는 구간 곱을 계산하는 문제로, 세그먼트 트리를 이용해야하며, 합 대신 곱 연산으로 변경해주면 된다.

#주의할 점

* 곱 연산이기 때문에 발생하는 오버플로우 문제가 있다.

* update 를 하는 방식은 다양하지만, 이전 값과의 차이(difference) 값을 해당 노드마다 곱해주는 방식으로는 WA 를 받는다.

  - difference 값을 계산하면서 발생하는 나눗셈 연산이 문제의 조건인 1000000007 MOD 연산에 영향을 줄 수 있을 것 같다.

  - 따라서 잎 노드의 변경으로부터 다시 계산하는 방식으로 업데이트를 수행한다.

소스코드

1. #include<stdio.h>
2. #include<vector>
3. #define MOD(x) ((x)%1000000007)
4. using namespace std;
5. typedef unsigned long long ull;
6. int n, m, k;
7. ull arr[1000001];
8.  
9. ull make_seg_tree(vector< ull > &v, int node, int start, int end){
10. if(start == end){
11. return v[node] = arr[start];
12. }
13. return v[node] = MOD( make_seg_tree(v, node*2, start, (start+end)/2) *
14. make_seg_tree(v, node*2+1, (start+end)/2 + 1, end));
15. }
16. ull update_seg_tree(vector<ull>&v, int node, int start, int end, int idx, ull val, bool was_zero) {
17. if( idx < start || end < idx) return v[node];
18.  
19. if(start == end) {
20. arr[idx] = val;
21. return v[node] = val;
22. } else {
23. return v[node] = MOD(update_seg_tree(v, node*2, start, (start+end)/2, idx, val, was_zero) *
24. update_seg_tree(v, node*2+1, (start+end)/2+1, end, idx, val, was_zero));
25. }
26. // v[node] = was_zero ? val : MOD((ull)(v[node] / arr[idx] * val)); // difference 를 이용한 수정
27. }
28.  
29. ull get_mul(vector< ull >&v, int node, int start, int end, int left, int right) {
30. if(right < start || end < left) return 1;
31. if(start==end) return v[node];
32. if(left <= start && end <= right){
33. return v[node];
34. }
35. return MOD( get_mul(v, node*2, start, (start+end)/2, left, right) *
36. get_mul(v, node*2+1, (start+end)/2+1, end, left, right));
37. }
38.  
39. int main(){
40. scanf("%d %d %d",&n,&m,&k);
41. for(int i=1;i<=n;i++){
42. scanf("%u",&arr[i]);
43. }
44. vector< ull > v(4*n);
45. make_seg_tree(v, 1, 1, n);
46.  
47. int a, b,c;
48. for(int i=0; i<m+k;i++){
49. scanf("%d %d %d",&a, &b, &c);
50. if(a == 1){
51. //update
52. bool was_zero = arr[b] == 0;
53. ull val = (ull)c;
54. update_seg_tree(v, 1, 1, n, b, val, was_zero);
55. arr[b] = val;
56. } else{
57. //get mul
58. printf("%u\n", get_mul(v, 1, 1, n, b, c));
59. }
60. }
61.  
62. return 0;
63. }

문제 정의

축구 팀 A와 B가 90분에 걸쳐 경기를 한다. 적어도 한 팀이 골을 소수로 득점할 확률을 구하라.

경기를 5분 간격으로 나누고, 처음 간격은 처음 5분이다.

A팀과 B팀이 이 간격에서 득점할 확률이 주어질 때, 경기가 끝난 후 적어도 한 팀이 골을 소수로 득점할 확률을 구하시오.

입력 예) 50 50

문제 풀이

이 문제는 DP로 풀 수 있습니다.

DP[p][a][b] : p번째 간격이 지났을 때, A팀이 a골, B팀이 b골을 넣었을 확률

즉, pa를 A가 넣을 확률, pb를 B가 넣을 확률이라고 할 때,

DP[p][a][b] = DP[p-1][a][b] * (1.0 - pa) * (1.0 - pb) +

DP[p-1][a-1][b] * pa * (1.0 - pb) +

DP[p-1][a][b-1] * (1.0-pa) * pb +

DP[p-1][a-1][b-1] * pa * pb

로 구할 수 있습니다.

소스코드

#include< stdio.h >
double dp[20][20][20];
int prime[7] = { 2,3,5,7,11,13,17 };
int isprime(int x) {
	for (int i = 0; i < 7; i++)
		if (x == prime[i])
			return 1;
	return 0;
}
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	
	double A = a / 100.0, B = b / 100.0;
	dp[1][0][0] = (1. - A) * (1. - B);
	dp[1][1][0] = A * (1. - B);
	dp[1][0][1] = (1. - A) * B;
	dp[1][1][1] = A*B;
	
	for (int p = 2; p <= 18; p++) {
		for (a = 0; a <= 18; a++) {
			for (b = 0; b <= 18; b++) {
				dp[p][a][b] = dp[p - 1][a][b] * (1. - A)*(1. - B);
				if (a != 0)
					dp[p][a][b] += dp[p - 1][a - 1][b] * A * (1. - B);
				if (b != 0)
					dp[p][a][b] += dp[p - 1][a][b - 1] * (1. - A) * B;
				if (a != 0 && b != 0)
					dp[p][a][b] += dp[p - 1][a - 1][b - 1] * A * B;
			}
		}
	}	
	double ans = .0;
	for(a=0;a<=18;a++){
		for (b = 0; b <= 18;b++) {
			if (isprime(a) || isprime(b))
				ans += dp[18][a][b];
		}		
	}
	printf("%.10lf\n", ans);
	return 0;
}