화투의 개발 블로그

[문제 링크]

이전 Coder's high 제출 문제다.

어려운 문제는 아니고 그냥 조건만 맞추면 되는 문제인데, 자꾸 조건을 중간에 빼먹어서 문제였다.

처음엔 그냥 월별, 요일별로 조건문에 때려넣어서 했는데 코드가 너무 안예뻐서... 그냥 다 상수처리해서 정리하였다.

#include <iostream>
#include <string>
using namespace std;
int testcase;
const int monthEnd[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
const int monthBefore[12] = {31,31,28,31,30,31,30,31,31,30,31,30};
const string dowArr[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
int main(){
    cin>>testcase;
    while(testcase--){
        int cur,m,d,dowIdx;
        string dow;
        cin>>m>>d>>dow;
        for(int i = 0;i<7;i++){
            if(!dow.compare(dowArr[i])){
                dowIdx = i;
                break;
            }
        }   
        for(int i = 0; i < 7; i++){
            cur = d-(dowIdx-i);
            cur = cur<1?monthBefore[m-1] + cur : (cur>monthEnd[m-1]?cur-monthEnd[m-1]:cur);
            printf("%d ",cur);
        }
        printf("\n");
    }
} 

[문제 링크]

예전 Coder's high 제출 문제라고 한다. 처음에 기하 문제인 줄 알고 머리를 싸맸지만 알고보니 정말 간단한 문제였다.

각 고기 별로만 뒤집을 생각만 하고 있었는데.

그냥 고기판 전체를 뒤집으면 모든 고기가 뒤집힌다. (약간 낚시성 문제인거같다.. 예제 출력부터가... 물론 조건에 모든 경우는 다 가능하다고 설명하긴 했다만...)

#include <cstdio>
int testcase,H,W;
char Grill[11][11],output[11][11];
int main(){
    scanf("%d",&testcase);
    while(testcase--){
        scanf("%d %d",&H,&W);
        for(int height = 0; height<H; height++){
            getchar();
            for(int width = 0; width < W; width++){
                scanf("%c",&Grill[height][width]);
            }
            for(int width = W-1; width>=0; width--){
                printf("%c",Grill[height][width]);
            }
            printf("\n");
        }
    }
    
}

[문제 링크]

DFS 문제다. 각 방이 노드, 문이 간선인 무방향 그래프로 보고 DFS로 방문하며 출력을 하면 된다.

나는 인접리스트로 문제를 풀었는데,(인접배열로 하기엔 배열의 크기가 너무 크다.)

가장 낮은 번호의 방을 먼저 방문한다고 했으므로, 인접리스트를 정렬 한 뒤에 탐색을 진행하도록 하였다.

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
vector<vector<int> > graph;
vector<int> visited;
void dfs(int cur){
    printf("%d ",cur);
    sort(graph[cur-1].begin(),graph[cur-1].end());
    for(int i =0; i<graph[cur-1].size();i++){
        if(visited[graph[cur-1][i]-1]==0){
            visited[graph[cur-1][i]-1] = 1;
            dfs(graph[cur-1][i]);
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    graph.resize(n);
    visited.resize(n);
    for(int i = 0; i < m; i++){
        int a,b;
        scanf("%d %d",&a,&b);
        graph[a-1].push_back(b);
        graph[b-1].push_back(a);
    }
    visited[0] = 1;
    dfs(1); 
}

[문제 링크]

DP 문제이다. DP와 그리디 문제 예시로 유명한 '배낭 채우기'문제와 정말 유사한 문제이다.

배낭 채우기 문제와는 다른점은 메모이제이션 할 값이 실수형이라는 점인데, 여기서 소수 둘째자리까지만이라는 제한을 주었으므로,

이는 100을 곱해 자연수로 만든 후 처리가 가능하다.

다만 실수 자료형 부동소수점 문제로 오차가 있을 수 있으니 100을 곱한뒤 소수 첫째 자리에서 반올림해주어야 한다.

그렇게 변형한 금액으로 메모이제이션해 최대 값을 구하면 된다.

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

#include <cstdio>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
int n, c, cache[10001];
double m, p;
typedef pair<int, int> Candy;
Candy cd[5001];
int candyStore(int money) {
    int& ret = cache[money];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i <n; i++) {
        //남은 금액이 0 이상일 경우에만 비교. 
        if (money - cd[i].second >= 0) {
            int tmp = cd[i].first + candyStore(money - cd[i].second);
            ret = max(ret, tmp);
        }
    }
    return ret;
}
int main() {
    while (true) {
        memset(cache, -1, sizeof(cache));
        scanf("%d %lf", &n, &m);
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++) {
            scanf("%d %lf", &c, &p);
            cd[i] = make_pair(c, (int)(p*100+0.5));
        }
        printf("%d\n", candyStore((int)(m*100+0.5)));
    }
}

[문제 링크]

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

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

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);
    }
}