화투의 개발 블로그

[문제 링크]

다익스트라 알고리즘을 사용하면 된다.

다익스트라 알고리즘에 대한 설명은 다음 포스트를 참조하자

http://hsp1116.tistory.com/42

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#define MAX 987654321
using namespace std;
vector<vector<pair<int, int> > > adj;
int n, m, x;
typedef pair<int, int> node;
struct cmp {
    bool operator()(node x, node y) {
        return x.second > y.second;
    }
};
void dijkstra(int x) {
    priority_queue<node, vector<node>, cmp> pq;
    vector<int> dist(n+1,MAX); dist[x] = 0;
    pq.push(make_pair(x,0));
    for(int i=1; i<=n;i++){
        if(i!=x) pq.push(make_pair(i,MAX));
    }
    while(!pq.empty()){
        int u = pq.top().first;
        int d = pq.top().second; pq.pop();
        if(d > dist[u]) continue;
        for(int i = 0; i<adj[u].size(); i++){
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push(make_pair(v,dist[v]));
            }
        }       
    }
    for(int i = 1; i<=n; i++){
        printf(dist[i] == MAX? "INF\n": "%d\n",dist[i]);
    }
    
}
int main() {
    scanf("%d %d %d", &n, &m, &x);
    adj.resize(n + 1);
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back(make_pair(v, w));
    }
    dijkstra(x);
}

[문제 링크]

LCS2는 다음 포스트에 있는 내용과 같다.

http://hsp1116.tistory.com/37

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<char> output;
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(int m,int n){
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=m;i++){
        for(int j=1; j<=n;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[m][n];
}
void backTracking(int m, int n){
    if(m==0 || n ==0) return;
    if(cache[m][n] > cache[m-1][n-1] && cache[m][n] > cache[m][n-1] && cache[m][n] > cache[m-1][n]){
        output.push_back(input[n-1]);
        backTracking(m-1, n-1);
    }else if(cache[m][n] > cache[m-1][n] && cache[m][n] == cache[m][n-1]){
        backTracking(m, n-1);
    }else{
          backTracking(m-1, n);
    }
}
int main(){
    scanf("%s%s",input,compare);
    int m = strlen(compare), n = strlen(input);
    printf("%d\n",LCS(m,n));
    backTracking(m,n);
    for(int i=output.size()-1;i>=0;i--)
        printf("%c",output[i]);
}

[문제 링크]

LCS는 다음 포스트에 있는 내용과 같다.

http://hsp1116.tistory.com/37

#include <cstdio>
#include <algorithm>
#include <cstring>
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(){
    int n = strlen(compare), m = strlen(input);
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=n;i++){
        for(int j=1; j<=m;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[n][m];
}
int main(){
    scanf("%s %s",input,compare);
    printf("%d\n",LCS());
}

공통 부분 수열이란, 두 문자열이 공통으로 가지고 있는 부분 수열을 말한다.

예를 들어 문자열

문자열 A : CDABE

문자열 B : CDEGT

가 있다면,

공통 부분 수열은

{},{C},{D},{E},{C,D},{D,E},{C,E},{C,D,E}

일 것이다.

1. 최장 공통 부분 수열 길이 구하기

최장 공통 부분 수열은 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 말한다.

위 예제 최장 공통 부분 수열은{C,D,E}이고, 길이가 3이다.

최장 증가 부분 수열은 또한 다음과 같은 정의를 따른다. 각 점화식을 에제를 들어 확인해보자.

(1) Ai != Bj

두 문자열 CDABE,CDEGT의 최장 공통 부분 수열을 구한다고 해보자.

여기서 맨 마지막 문자인 E와 T가 각각 다르므로 다음과 같은 경우를 고려 할 수 있다.

1. 최장공통부분 수열이 E로 끝나는 경우.

이 경우 K는 최장 공통 부분 수열에 아무련 영향을 끼치지 않으므로 없어도 상관 없다.

즉 LCS(i,j) = LCS(i,j-1)이다.

2. 최장 공통 부분 수열이 T로 끝나는경우

이 경우 E가 최장 공통 부분 수열에 아무런 영향을 끼치지 않으므로 지워도 상관없다.

이 경우엔 LCXS(i,j) = LCS(i-1,j)이다 

3. 둘 다 해당이 되지 않는 경우.

둘 다 지워도, 하나만 지워도 최장 증가 부분 수열에 영향을 끼치지 않는다. 따라서 고려 할 필요가 없다.

두 문자가 일치하지 않을 때, 최소 둘 중 하나는 최장 공통 부분 수열에 영향을 끼치지 않으므로 둘 중 하나를 지워도 상관없다.

즉 둘 중 하나를 지웠을 때의 더 큰 LCS가 LCS(i,j)이다.

따라서 LCX(i,j) = max(LCS(i-1,j),LCS(i,j-1))임을 알 수 있다.

(2) Ai == Bj

두 문자열 CDABE CDE라고 가정해보자. 맨 뒤의 문자 E가 설 일치하는데, 공통 문자인 E는 최장 공통 부분 수열에 반드시 포함될 것이다.

따라서 이 두 문자열을 지운다면, 최장 공통 부분 수열에서 또한 E가 사라질 것이라는 것을 알 수 있다.

즉 최장 증가 부분 수열의 길이 또한 1 감소하므로, LCX(i,j) = LCS(i-1,j-1) + 1이다.

이제 위 공식을 이용하여 구현하면 된다. 각 인덱스는 현재 문자열의 길이라고 생각하면 된다.

맨첨 1행, 1열들은 모두 0으로 치워지는데 이는 빈 수열을 뜻한다. 빈 수열과 문자열의 최장 증가 부분 수열은 0이기 때문이다.

밑은 앞서 확인한 공식으로 작성한 테이블이다.

LCS(5,5)=3으로, 최장 공통 부분 수열의 길이는 3임을 알 수 있다.

int LCS(string& input, string& compare){
    int cache[1001][1001];
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=compare.length();i++){
        for(int j=1; j<=input.length();j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[compare.length()][input.length()];
}

1. 최장 공통 부분 수열 구하기

이는 우리가 구한 2차원 배열을 역추적 하여 구할 수 있다.

최장 증가 부분 수열을 찾는 공식을 잘 고려해 보자.

우리가 찾아야 하는건 Ai == Bi인 문자이다.

Ai == Bj일 때 LCS(i,j) = LCS(i-1,j-1) + 1였는데. 이를 고려해 역추적 해나가면 된다.

다만 또 고려할 것이 있는데, LCX(i,j) = max(LCS(i-1,j),LCS(i,j-1))의 경우이다.

Ai != Bj일 지라도, LCS(i,j) = max(LCS(i-1,j),LCS(i,j-1))를 통해 LCS(i-1,j-1) + 1가 도출 될 수 있다.

따라서 LCS(i-1,j), LCS(i,j-1)이 둘 다 LCS(i,j)보다 작으면서, LCS(i-1,j-1)이 LCS(i,j)보다 작은 경우가 Ai==Bj일 때이다. 

즉 LCS[i][j] > LCS[i-1][j-1] && LCS[i][j] > LCS[i][j-1] && LCS[i][j] > LCS[i-1][j])를 조건으로 코드를 구현하면 된다.

밑은 해당 코드이며, output에 최장 공통 부분 수열 문자열이 저장된다.

string output;
void backTracking(int m, int n){
    if(m==0 || n ==0) return;
    if(cache[m][n] > cache[m-1][n-1] && cache[m][n] > cache[m][n-1] && cache[m][n] > cache[m-1][n]){
        //문자열 인덱스는 캐시 인덱스보다 1씩 더 작다. 
        output = input[n-1] + output;
        backTracking(m-1, n-1);
    }else if(cache[m][n] > cache[m-1][n] && cache[m][n] == cache[m][n-1]){
        backTracking(m, n-1);
    }else{
          backTracking(m-1, n);
    }
}

[문제 링크 : 1725 히스토그램]

[문제 링크 : 6549 히스토그램에서 가장 큰 직사각형]

[문제 링크 : FENCE]

예전에 내가 풀었던 방식은 분할정복이었는데.

스택 문제 복습 겸 스택으로 풀도록 노력하였다.

스택을 통해 스위핑 알고리즘으로 푼다는데 이에 대한 설명은 구종만님의 책에도 있지만 개인적으로 너무 이해가 힘들었다.

스택을 이용해서 풀 때, 가장 왼쪽부터 차례대로 스택에 삽입하여 문제를 해결해간다.

스택에 막대를 삽입하는 조건은 '삽입하려고 하는 막대가, TOP에 있는 막대의 높이보다 클 때'이다.

만약 다음에 삽입하려는 막대가 현재 스택 TOP에 있는 막대보다 작으면, TOP에 있는 막대 높이로 만들 수 있는 직사각형의 오른쪽 끝이 된다.

그 경우 top을 pop하여 너비를 구한다. pop하기 전에 있던 top의 값을 tmp에 저장한다고 해보자. pop후의 스택의 top값은 tmp 왼쪽의 tmp보다 작은 막대이므로, 이 직사각형의 왼쪽 끝이 된다.

즉 tmp의 높이로 만들 수 있는 직사각형의 크기 = h[tmp] * (right - stack.top - 1)

위의 로직을 이해했으면 같을 경우에 굳이 스택에 인덱스를 삽입하지 않는 이유도 이해가 갈 것이다.

반복문을 다 돌았을 때 스택에 값이 남아있으면 이는 최대 직사각형에서 오른쪽 끝이, 전체의 오른쪽 끝인 직사각형들이다. 위에서 구한 공식대로 그 값들을 구해 최대값을 찾으면 된다. 

이를 구현한 코드는 다음과 같다.

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
long long n, arr[100001];
long long histogram(){
    stack<long long> st;
    long long i,ret = 0;
    //스택에 왼쪽 끝 인덱스값을 미리 삽입해둔다. 
    st.push(-1);
    for(i=0; i<n;i++){
        //스택이 비어있지 않고,  
        while(!st.empty()&&arr[i]<arr[st.top()]){
            //right는 i 
            int tmp = st.top(); st.pop();
            if(!st.empty())
                //left는 st.top
                //left-right-1 너비, 높이 arr[tmp]의 직사각형 넓이 
                ret = max(ret, arr[tmp]*(i-st.top()-1));
        }
        //너비를 다 구하고 다음 판자를 스택에 삽입.
        st.push(i); 
    }
    //히스토그램을 끝까지 스택에 넣었는데도 안끝났다면
    //스택에 남아있는 판자들에서의 최대값을 구한다. 
    while(!st.empty()) {
        int tmp = st.top(); st.pop();
        if(!st.empty())
            ret = max(ret, arr[tmp]*(i-st.top()-1));
    }
    return ret;
}
int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&arr[i]);
    printf("%lld\n",histogram());
    
}   

참고 : https://www.acmicpc.net/blog/view/12

[문제 링크]

스택을 이용하면 쉽게 푸는 문제이다.

나는 입력 받으면서 스택에서 체크하여 값을 출력하는 방식으로 풀었다.

값을 입력받으면, 스택을 체크한다. 스택을 체크해서 스택이 비었으면 그 탑 왼쪽에는 탑이 없는 것이므로 0을 출력한다.

탑이 있을 경우, 현재 입력받은 탑의 높이와, 스택의 top에 있는 탑의 높이를 비교한다. 만약 값의 크기가 현재 탑보다 작으면, 스택을 pop하여 다음 값을 다시 비교한다.

top에 저장된 높이 값이 현재 입력받은 높이값보다 같거나 클경우, 혹은 스택이 비었을 경우까지 이를 반복한다. top의 값이 같거나 클 경우에는 top의 인덱스를 출력하고, 비었으면 0을 출력한다.

그 다음에 현재 입력받은 값을 탑의 인덱스와 함께 스택에 push한다.

문제에 제시된 예제를 통해 예를 들어보겠다.

5
6 9 5 7 4

현재 스택은 비어있는 상태이다.

1. 먼저 6을 입력 받는다. 스택을 체크한다. 현재 스택에 삽입된 값은 없다, 콘솔에 '0'을 출력하고, 스택에 탑의 인덱스와 크기를 pair로 묶어 삽입한다.

출력 : 0

스택 : (1,6)

2. 그 다음 9를 입력받는다. 스택을 체크한다. top에 있는 값의 크기는 6이다. 현재 입력받는 9보다 작으므로 스택을 pop한다. 

출력 : 0

스택 :

그리고 다시 스택을 체크한다. 스택이 비어있다. 콘솔에 '0'을 출력하고, 입력받은 값을 삽입한다.

출력 : 0  0

스택 : (2,9)

3. 다음은 5이다. 스택을 체크한다. top에 있는 값은 9이고 현재 입력값보다 크다. top에 있는 인덱스를 출력하고 스택에 입력값을 push한다.

출력 : 0  0  2

스택 : (2,9)  (3,5)

4. 다음은 7이다. 스택을 체크한다. top에 있는 값은 5이고 현재 입력값보다 작다. 스택을 pop한다.

출력 : 0  0  2

스택 : (2,9)

그리고 다시 스택을 체크한다. top에 있는 높이 값은 9이다. 입력값인 7보다 크므로 top의 인덱스를 출력하고 스택에 push한다.

출력 : 0  0  2  2

스택 : (2,9)  (4,7)

5. 마지막으로 4이다. 스택 top을 체크하는데 top의 값은 7이고 입력값보다 크다. 인덱스를 출력하고 스택에 push한다.

출력 : 0  0  2  2  4

스택 : (2,9)  (4,7)  (5,4)

5번 반복했으므로 반복문이 끝나고 프로그램을 종료한다.

즉 스택에는 이전값중의 가장 큰 값과, 현재 값 사이에 있는 값들은 전부 없앤다고 보면 된다.

이를 구현한 코드는 다음과 같다.

#include <cstdio>
#include <stack>
#include <utility>
using namespace std;
int n, k;
stack<pair<int, int> > st;
int main() {
    scanf("%d", &n);
    for (int i = 1; i<=n; i++) {
        scanf("%d", &k);
        while (!st.empty()) {
            //스택의 top이 현재 입력값보다 크다면 신호 수신 가능이므로 
            if (st.top().second > k){
                //top의 위치를 출력하고 반복문을 탈출한다. 
                printf("%d ", st.top().first);
                break;
            }
            st.pop();
        }
        //스택이 비었으면 0을 출력한다. 
        if(st.empty()) printf("0 ");
        //그리고 현재 탑을 스택에 push 
        st.push(make_pair(i, k));
    }
}

[문제 링크]

문제 의도는 스택으로 푸는 문제이지만, 굳이 스택으로 풀지 않아도 되는 문제이다.

그냥 레이저를 만났을 때, 여는 괄호의 갯수 만큼 더해줘도 되지만, 여기서는 스택을 이용해서 풀어보겠다.

이 문제를 풀기 위해선, 닫는 괄호가 나타났을 때, 이 것이 레이저인지, 아니면 파이프의 끝을 나타내는 것인지 구별해야 된다.

구별하는 방법은 정말 쉽다, 닫는 괄호가 나타났을 때, 바로 전 문자를 체크해서 이게 여는 괄호인지 아닌지만 확인하면 된다.

즉 여는 괄호를 만나면 전부 스택에 push하다가, 닫는 괄호를 만나면 스택에서 pop하고 괄호가 레이저면 스택 사이즈만큼 더해주거나, 파이프 끝이면 1만 더해주면 된다.

위 사진으로 예를 들어보자. 

처음에 '('를 만나서 스택에 push한다, 그리고 두번째에 ')'를 만난다. 스택에서 '('를 pop한다. 이전 문자는 '('이므로 레이저이다. 결과값에 스택 사이즈(0)만큼 더해준다.

result += 0

그다음 '('를 4개 만난다. 스택에 '('가 4개 들어가고 스택 사이즈는 4이다. ')'를 만나서 스택을 pop한다. 바로 전이 '('이므로 이는 레이저이다. 결과값에 스택 사이즈(3)만큼 더해준다.

result += 3

바로 다음에 괄호를 다시 여닫고 스택을 그에따라 push,pop해준다. 레이저이므로 스택 사이즈(3)을 다시 더해준다.

result += 3

닫는 괄호를 만난다. 바로 전 문자는 ')'이므로 레이저가 아닌 파이프의 끝이다. 파이프 꼭다리가 남으므로 1을 더해준다.

result +=1

위의 방법을 계속 반복하면 된다. 나머지는 직접 해보자.

이를 구현한 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;
string str;
int pipe(const string& str){
    stack<char> st;
    int result=0;
    for(int i =0; i<str.length();i++){
        //여는 괄호면 스택에 넣는다. 
        if(str[i]=='(') st.push(str[i]);
        //닫는 괄호면 이 괄호가 레이저인지, 파이프 끝인지 알아본다.
        else{
            st.pop();
            //레이저면 
            if(str[i-1]=='(') 
                result += st.size(); //잘린 갯수 추가. 
            //파이프의 끝이면 
            else result++; //닫혀서 잘려진 갯수 추가. 
        }
    }
    return result;
}
int main(){ 
    cin >> str;
    cout<<pipe(str);
}

[문제 링크]

DP문제이다. 경로 모든 경로의 수를 구하는 미로 찾기와 같은 문제랑 다를게 없는데, 거기서 내리막으로만 갈 수 있다는 조건만 주면 되는 문제이다.

맵의 끝에 도달하면 1을 반환하고, 아닐 경우 0을 반환하여 경로의 갯수를 구한다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <cstring>
int m,n,arr[501][501];
int relPos[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int cache[501][501]; 
int dp(int y,int x){
    //기저사례 : 끝에 도달했으면 탈출 
    if(y==m && x==n) return 1;  
    int& ret = cache[y][x];
    if(ret!=-1) return ret;
    ret = 0;
    for(int c = 0; c<4; c++){
        int px = x + relPos[c][0];
        int py = y + relPos[c][1];
        //맵을 안넘어서고 내리막이면 
        if(px <=n && py<=m && px>=1 && py>=1&&arr[py][px] < arr[y][x])
            ret +=dp(py,px);
    }
    return ret;
} 
int main(){
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&m,&n);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&arr[i][j]);
        }
    }
    printf("%d",dp(1,1));
} 

경로 문제를 자주 보다보니 경로 문제는 이제 다 비슷비슷하다는 생각이 든다.