화투의 개발 블로그

문제 링크 : 알고스팟 NQUEEN

문제 링크 : 백준 N-QUEEN

N-Queen문제, 즉 여왕말 문제는 백트래킹 관련으로 정말 유명한 문제이다. 백트래킹이란 그냥 다음 탐색을 진행하는데, 그 탐색이 유망하지 않으면 무시하고 돌아가서다시 탐색한다는 것(백트래킹,되추적) 이다.

출처 위키피디아

여왕말에서 유망한 탐색인지 아닌지를 검사하는 조건은 정말 간단하다. 그냥 지금까지 고른 말의 위치 중에서 같은 열에 속하는 게 있는지, 혹은 대각선에 위치하는 게 있는지 검사하고 있으면 이 탐색을 무시하고(가지치기하고) 되돌아가 다음 탐색을 진행(백트래킹)한다.

끝까지 도달하였으면, 가능한 경우를 찾은 것이므로 카운트를 증가 시키고 반환하여 다른 경우를 찾는다.

밑은 이 풀이에 해당하는 코드이다.

#include <cstdio>
#include <cmath>
int n, t, a[13], count=0;
//이 위치에 여왕 말을 놓을 수 있는지, 즉 유망한지 체크한다. 
bool check(int cur) {
    //0부터 이 행까지 모두 조사한다. 
    for (int i = 0; i<cur; i++) {
        //열이 같은 것이 있거나, 대각선 범위 내에 있으면 불가능한 경우므로 false을 리턴 
        if(a[i]==a[cur] || cur-i==std::abs(a[cur]-a[i])){
            return false;
        }    
    }
    return true;
}
void nqueen(int cur) { 
    //기저사례 : 끝에 도달하였으면 카운터를 증가 시키고 반환한다. 
    if(cur==n-1) {
        count++;
        return; 
    }
    //아직 끝에 도달하지 않았으면 다음 위치를 찾는다. 
    for(int i=0;i<n;i++){
        a[cur+1] = i;
        //이 위치가 유망한지 검사, check이 참이면 다음 여왕 말을 찾고, 못 찾으면 백트래킹한다.
        if(check(cur+1)){
            nqueen(cur+1);
        }
    } 
}
int main() {
    scanf("%d",&t);
    while(t--){
        count = 0;
        scanf("%d", &n);
        nqueen(-1);
        printf("\n%d\n",count);
    }   
}

근데 이렇게 가지치며 나가는 것보다 더 빠른 방법이 있는 것 같다. 좀 더 공부가 필요한듯하다..

문제 링크 : MORSE

문제 링크 : DICT

두 문제 다 같은 개념의 문제이다. 책을 보고도 쉽게 이해가 되지 않아서 머리가 아팠다...

MORSE문제에서의 -를 DICT의 a, o를 DICT의 b로 생각하고 풀면 된다.

이 문제는 k번째 위치에 있는 값을 출력하는 문제인데, 물론 일일이 사전 순서대로 출력하다가, 완성된 부호가 k번째 부호가 아니면, 그 다음 순서의 부호를 찾는 

무식하게 푸는 방법으로도 해결은 가능하다. 근데 문제는 k의 범위가 1억이다. 그냥 무식하게 풀었다가는 시간이 초과될 가능성이 높다.

그래서 여기서 해결하는 방법은, '현재 조합하려는 경우의 수가 찾고자 하는 순서보다 크면 패스, 작으면 찾아나가는' 방법이다.

예를 들어 n개의 -와 m개의 o로 조합을 하는 경우의 수는 이다. 수학을 안한지 오래되어 순열 조합을 까먹어서 기억을 더듬느라 머리가 아팠는데, 복수 순열로 n,m개씩 있을 때, 이를 늘어놓는 경우의 수가이고, 이게  이기 때문이다. 그냥 조합으로 이해하면 될 것 같은데 일단 이렇게 이해하고 넘어갔다...

즉, 현재 구하려는 수가 지금 조합하려는 부호의, 전체 조합 범위에 들어있지 않으면 현재의 구하는 조합의 경우에는 존재하지 않기 때문에, 그 이후는 검색할 필요가 없다는 것이다.

코드 작성 전에 간단한 예를 들어보자.

'-' 2개와 'o' 2개로 조합하는 부호에서, 4번째 수를 찾는다고 하자. 저 요소들로 조합이 가능한 개수는 4C2로, 6가지가 가능하다. 즉, 4번째는 현재 전체 갯수 6개보다 작으므로, 아직 구할 수 있다.

그럼 사전식 순서로 -를 하나 문장에 넣어 이어가보자. 그럼 이제 남은 요소는 '-' 1개와 'o' 2개이다. 이 요소로 가능한 개수는 3C1, 즉 3이다. 

이 말은 첫 글자가 -로 시작하는 문장이 3개(3C1)개라는 말이다. 4번째 문자는, 이 범위를 초과하므로 '-'로 시작하는 것이 아닌 'o'로 시작하는 부호임을 알 수 있다. 

이를 알았으니 이제 '-'가 아닌 'o'로 시작하는 문장중에서, 4-3C1=1번째 시작하는 문장을 찾으면 된다. 이를 지금가지와 같은 방식으로 풀이하면 'o--o'를 구할 수 있다.

밑은 위와 같은 로직으로 구하는 소스코드이다.

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1000000000+100;
int bino[201][201];

//파스칼의 삼각형으로 조합들을 미리 구해놓는다. 
void calcBino(){
    memset(bino,0,sizeof(bino));
    for(int i = 0; i<=200;++i){
        bino[i][0] = bino[i][i] = 1;
        for(int j = 1; j<i;++j)
            bino[i][j] = min(M, bino[i-1][j-1]+bino[i-1][j]); // 파스칼의 삼각형 점화식
    }
}
int skip;
void gen(int n, int m, string s){
    //기저사례1 : skip이 0보다 작으면 범위를 벗어난 것이므로 리턴한다. 
    if(skip <0) return;
    //기저사례2 : 더이상 조합할 요소가 없으므로 부호 완성. 
    if(n==0&&m==0){
        cout<<s<<endl;
        --skip;
        return;
    }
    //찾고자 하는 수가 현재 조합할수 있는 갯수를 넘어서면, 
    //현재 부호에 존재하지 않으므로 뛰어넘고 반환한다. 
    if(bino[n+m][n]<=skip){
        skip-=bino[n+m][n];
        return;
    }
    //각 요소가 존재하면 조합한다.  
    if(n>0)gen(n-1,m,s+"-");
    if(m>0)gen(n,m-1,s+"o");
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    skip = k-1;
    calcBino(); 
    gen(n,m,"");
}

위의 코드는 구하고자 하는 부호가 현재 범위에 포함되는 지의 여부를 재귀 호출로 넘어가서 검사하였지만, 이렇게 할 필요 없이 검사한 후 뛰어넘는 코드를 작성할 수 있다. 그 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int M = 1000000000+100;
int n,m,k,c,bino[201][201];
//파스칼의 삼각형을 통해 조합을 구해놓는다. 
void calcBino(){
    memset(bino,0,sizeof(bino));
    for(int i = 0; i<=200;++i){
        bino[i][0] = bino[i][i] = 1;
        for(int j = 1; j<i;++j)
            bino[i][j] = min(M, bino[i-1][j-1]+bino[i-1][j]); // 파스칼의 삼각형 점화식 
    }
}

int skip = 3;
string gen(int n, int m, int skip){
    //n이 더이상 없으면, o만 존재하므로 m을 반환한다. 
    if(n==0) return string(m,'o');
    
    //'-'를 선택했을경우의 조합의 범위 내에  구하고자 하는 부호를 포함되면
    //'-'를 추가하고 재귀호출한다. 
    if(skip<bino[n-1+m][n-1])
        return "-"+gen(n-1,m,skip);
    //포함되지 않으면 'o'를 추가하고, '-'가 가능한 수만큼 패스하여 다시 검사한다. 
    return "o"+gen(n,m-1,skip-bino[n+m-1][n-1]);
}
int main(){
    cin>>c;
    while(c--){
    cin>>n>>m>>k;
    skip = k-1;
    calcBino(); 
    cout<<gen(n,m,skip)<<endl;
    }
}

문제 링크

문제에서 풀이 방법을 가르쳐주었기 때문에 그냥 그 로직대로 따라가 풀었다. 코드 라인이 쓸대없이 길어져서 귀찮았던 것 같다.

나는 에라스토테네스의 체로 소수들을 전부 구하고 시작했는데, 풀고 보니 에라스토테네스의 체같은건 필요 없고, 그냥 평범하게 소수를 구하거나 그때그때 판별해도 상관없는 문제였다...

어쨌든 각 각 자리수를 바꿀수 있는 한도 내에서 바꾼 뒤, 해당 숫자의 이전 방문 여부와 에라스토테네스의 체로 구한 배열에서 소수인지 판별하고 큐에 넣어서 반복해주었다.

처음엔 그냥 숫자로만 풀이하려다가 숫자를 배열로, 배열을 숫자로 바꿔서 풀이하였다. 근데 바꾸나 마나였단 생각이 든다...

밑에는 풀이 코드이다.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue> 
using namespace std;
int t, x, y, a[10000] = { 0, }, visited[10000] = { 0, }, num[4];
typedef struct {
    int num, count;
}Prime;
queue<Prime> q;
//에라토스테네스의 체로 9999이하의 소수들을 모두 구한다. 
void era(int n) {
    int i;
    while (true) {
        for (i = 2; i <= n; i++)
            if (a[i] == 0) break;
        if (i>n) return;
        a[i] = 1;
        for (int j = 2; j*i <= n; j++) {
            if (a[i*j] == 0) {
                a[i*j] = 2;
            }
        }
    }
}
//배열을 숫자로 바꾼다.
int numToArr(){
    int ret=0;
    for(int i=0; i<4;i++){
        ret+=num[i]*pow(10,3-i);
    }
    return ret;
}
//자리수를 한번 바꾼 값이 소수인지 판별하고, 소수이면 큐에 넣는다.
void check(int i,int count){
    int k = i==0?0:1;
    int bak = num[i];
    while(num[i]-1>=1-k){
        num[i] -=1;
        int n = numToArr();
        if(a[n]==1&&visited[n]==0){
            Prime p1 = {n,count+1};
            visited[n]=1;
            q.push(p1);
        }
    }
    num[i]=bak;
    while(num[i]+1<=9){
        num[i] +=1;
        int n = numToArr();
        if(a[n]==1&&visited[n]==0){
            Prime p1 = {n,count+1};
            visited[n]=1;
            q.push(p1);
        }
    }
    num[i]=bak;
}
//너비우선 탐색.
int dfs() {
    Prime p = { x,0 };
    q.push(p);
    while (!q.empty()) {
        p = q.front(); q.pop();
        //값을 찾았으면 카운트값을 반환 
        if (p.num == y) return p.count;
        //숫자를 배열로 변경 
        for(int i=0;i<4;i++){
            num[i] = p.num/pow(10,3-i);
            p.num = p.num-num[i]*pow(10,3-i);
        }
        for(int i=0;i<4;i++){
            check(i,p.count);
        }
    }
    //못찾았으면 -1을 반환한다. 
    return -1;
}
int main() {
    era(9999);
    scanf("%d",&t);
    while(t--){
        scanf("%d %d", &x, &y);
        int ret = dfs();
        printf(ret==-1?"Impossible\n":"%d\n",ret);
        while(!q.empty())q.pop();
        memset(visited,0,sizeof(visited));
    }
}

문제 링크

소수와 관련된 다른 문제를 풀기위해 자세히 알아보게된 에라토스테네스의 체이다. 에라토스테네스의 체란 빠르게 소수들을 구하는 방법이다. 즉 특정수 n 이하의 모든 소수를 구하고 싶으면, n이하의 수중 합성수들을 지워나가면, 남은 숫자들은 소수가 된다는 것에서 착안한다.

먼저 2 이상의 가장 작은 수중, 아직 지우지 않는 수를 찾는다.  아직 하나도 지우지 않았으므로 2를 선택한다. 2는 소수이다, 그럼 2의 배수들은 전부 합성수들이므로, 2의 배수들은 모두 지워나간다.

그다음에 지워지지 않은 가장 작은 수는 3이다. 3은 소수이고, 3의 배수들은 전부 합성수이므로 3의 배수는 전부 지워나간다. 숫자를 다 지울때까지 반복한다.

이게 바로 에라토스테네스의 체이다. 

빠른 이해를 위한 이미지. 출처 위키피디아

이 문제는 에라토스테네스의 체처럼 소수를 구하는 문제와는 거리가 멀고, 에라토스테네스의 체가 어떤 순서로 숫자들을 지워나가고, 원하는 순서의 숫자를 구하는 문제이다. 그냥 이는 에라토스테네스의 체를 구현한 다음 해당 번째에서 출력하고 종료하면 되는 문제였다.

밑은 해당 소스코드이다.

#include <cstdio>
int n,k,a[1001]={0,},i,count=0;
int main(){
    scanf("%d %d",&n,&k);
    while(count!=k){
        //지우지 않은 가장 작은 수를 찾는다. 
        for(i=2;i<=n;i++)
            if(a[i]==0) break;
        //다 찾았는데 i가 1000이라면 다 지웠으므로 탈출한다. 
        if(i==1000) break;
        //i번째 수를 1을 채워 지웠음을 표시하고, 차례로 그 배수를 지워나간다. 
        for(int j=1;j*i<=n;j++){
            //만약 지우지 않은 숫자이면 해당 숫자 카운트를 증가시킨다. 
            if(a[i*j]==0){
                a[i*j]=1;
                count++;
            }
            if(count==k){
                printf("%d",i*j);
                return 0;   
            }
        }
    }
}

문제 링크

greedy 문제이다. 풀이는 간단하다. 괄호 개수의 제한이 없기 때문에 '-'를 만나면, 다음 '-'를 만날 때까지 그 값들을 전부 더한 뒤 계산 값에서 빼주면 된다.

왜냐하면 괄호 앞에 '-'가 있을 경우, 분배 법칙으로 괄호 안의 양수 값들은 전부 '-'로 처리되기 때문이다. 

나는 처음에 '-'를 토큰으로 문자열을 전부 나눈 뒤, 전부 덧셈 연산 처리를 한 다음에 빼줘서 풀었다.

하지만 그럴 필요 없이 그냥 값들을 전부 더해주다가 '-'를 만나면 그때부터 전부 다 빼주면 된다. 어차피 첫 '-'뒤의 '+'들은 전부 분배 법칙으로 '-'가 될 것이며, 다음 '-'를 만나면 그 전에 괄호를 닫고 다시 열게 되기 때문이다.

우선 처음에 그냥 '-'를 기준으로 토큰을 나눈 뒤 풀었던 코드이다. 나눈 토큰 들을 '+'처리한 다음에 첫 문자열을 제외한 나머지 문자열들은 전부 빼줬다.

//-가 나오면, 그 때부터 다음 -가 나올때까지 전부다 괄호를 쳐버리면 된다.
//-를 토큰으로 문자열을 추출한다. 그 문자열 안에 있는 값들의 +연산을 모두 처리하면 된다. 
#include <cstdio>
#include <cstring>
#include <cstdlib>
char cal[51] = { 0, };
char ca[51][51] = {0,};
char* ptr;
int ret,i=0;
//+연산을 처리하는 함수 
int calculate(char* str) {
    int r = 0;
    char* ptr2;
    ptr2 = strtok(str, "+");
    r += atoi(ptr2);
    while (ptr2 = strtok(NULL, "+")) {
        r += atoi(ptr2);
    }
    return r;
}
int main() {
    scanf("%s", cal);
    //-를 토큰으로 분해하고, 각 문자열을 저장한다. 
    ptr = strtok(cal, "-");
    strcpy(ca[i++],ptr);
    while (ptr = strtok(NULL, "-")) {
        strcpy(ca[i++],ptr);
    }
    //분해한 문자열을 전부 +연산 처리를 하고, 첫 수를 제외한 나머지 수는 전부 뺄셈 처리를 한다. 
    ret=calculate(ca[0]);
    for(int j=1;j<i;j++){
        ret -= calculate(ca[j]);
    }
    printf("%d",ret);
}

이 코드만 봐도 알고 보면 첫 '-'이후의 값들은 전부 다 빼주면 된다는 걸 알 수 있다.

다음 코드는 이를 적용해 보았다.

#include <cstdio>
#include <cstring>
#include <cstdlib>
char cal[51] = { 0, };
char ca[51] = {0,};
char* ptr;
int ret,i=0;
//덧셈을 처리하는 함수. 전과 달라진건 -,+을 안가리고 전부 더해버린다. 
int calculate(char* str) {
    int r = 0;
    char* ptr2;
    ptr2 = strtok(str, "+-");
    r += atoi(ptr2);
    while (ptr2 = strtok(NULL, "+-")) {
        r += atoi(ptr2);
    }
    return r;
}
int main() {
    scanf("%s", cal);
    //첫 -를 기준으로 토큰을 나눈다. 
    ptr = strtok(cal, "-");
    strcpy(ca,ptr);
    //첫 - 이후의 문자열을 받는다. 
    ptr = strtok(NULL,"");  
    ret=calculate(ca);
    //첫 - 이후의 문자열은 전부 덧셈 처리한 뒤 빼준다. 
    if(ptr!=NULL)ret-=calculate(ptr); 
    printf("%d",ret);
}

마지막으로는 다른 분 코드를 참조해 짜본, 라이브러리 함수를 쓰지 않고 배열을 하나하나 검사해서 짜는 코드이다.

#include <cstdio>
char cal[51] = { 0, };
int ret=0,n=0,i=0,flag=0;
int main() {
    scanf("%s", cal);
    while(cal[i] != 0){
        //숫자이면 
        if(cal[i] >='0' && cal[i]<='9'){
            //이전에 저장한 숫자의 자릿수를 하나 늘려주고 이 값을 더해준다. 
            n*=10;
            n+=cal[i]-'0'; 
        }
        //그 후 지금까지 숫자값들을 0으로 초기화해준다. 
        else{
            //-연산자를 만난적이 없으면, 즉 flag가 0이면 그냥 더해준다.
            if(flag==0) ret +=n;
            //-연산자를 만난적이 있으면, 즉 flag가 1이면 뺄셈처리한다.
            else ret-=n;
            //첫 -이면, 즉 -이고 flag가 0이면 flag를 1로 만들어준다. 
            if(cal[i]=='-'&&flag==0) flag=1;
            n = 0; 
        } 
        i++;
    }
    //마지막 숫자를 flag에 맞게 처리해준다. 
    if(flag==0) ret+=n;
    else if(flag==1) ret-=n;
    printf("%d",ret);
}

문제 링크

이렇게 로직 생각을 하고 처음에 코드를 작성하였다. 

#include <cstdio>
#include <algorithm>
int t,n,rank[100000][2],r1,r2;
int recruit(){
    //정렬한다. 
    for(int i = 0; i<n; i++){
        for(int j= 1;j<n-i;j++){
            if(rank[j][0]<rank[j-1][0]){
                std::swap(rank[j][0],rank[j-1][0]);
                std::swap(rank[j][1],rank[j-1][1]);
            }
        }
    }
    
    int min = rank[0][1],count = 1;;
    for(int i=0;i<n;i++){
        if(min>rank[i][1]){
            count++;
            min = rank[i][1];
        }
    }   
    return count;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        //각 사원의 등수 입력 
        for(int i =0; i<n;i++){
            scanf("%d %d",&rank[i][0],&rank[i][1]);
        }
        printf("%d\n",recruit());
    }
}

정렬은 그냥 편하게 버블 소트로 하였더니 시간 초과가 발생하였다. 이를 해결하려고 퀵소트로 바꿔서 다시 정렬을 해보았으나. 이 또한 시간 초과가 발생하였다. 

그러면 입력을 받은 후 정렬을 하는 것이 아니라, 입력 도중에 정렬을 할 필요가 있었다. 고민하던 차에 ,이 문제에서 애초에 '1위부터 N위까지 동석차 없이 결정된다고 가정'했으므로, 그냥 등수에 맞는 배열의 인덱스에다가 저장하면 될 일이었다. 

#include <cstdio>
using namespace std;
int t,n,rank[100001],rx,ry;
int recruit(){
    int min = rank[1],count = 1;
    for(int i=1;i<=n;i++){
        if(min>rank[i]){
            count++;
            min = rank[i];
        }
    }   
    return count;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        //각 사원의 등수 입력 
        for(int i =0; i<n;i++){
            //서류점수 등수 순서대로 면접 점수를 입력받는다. 
            scanf("%d %d",&rx,&ry);
            rank[rx] = ry; 
        }
        printf("%d\n",recruit());
    }
}

그렇게 코드를 다시 작성하였다. 다른 사람들의 코드를 보니 이 방법이나, 정렬 코드를 짜는 것이 아닌 STL의 sort를 통한 정렬은 시간 초과 없이 작동하는 것 같았다.

아마 테스트케이스중에 완전 역순으로 정렬된 테스트케이스가 있어 정렬에 n^2이 걸렸기 때문인 것 같았다. 이 경우에 대한 처리나 머지소트로 정렬했으면 시간초과가 안날것 같기는 하다.

어려운 문제는 아니었지만 너무 틀에 박힌 생각보다는 좀 더 폭넓게 생각하는 버릇이 필요한 것 같다는 생각이 든다..