JArchive 프로그래밍 일기

문제

팩토리얼 백준 10872번

리뷰

정수 N(0 ≤ N ≤ 12)가 주어진다. 이때, N!을 출력하는 프로그램을 작성하는 문제다.

0! 은 0이라고 틀리게 알아서 처음에 풀 때 틀렸다. 질문게시판 FAQ 글 읽고 알았다.

0! 은 1이다

그 이유는 다음과 같다.

4! = 4 x 3 x 2 x 1 
    = 4 x (4-1)!
    = 4 x 3!

위의 논리를 1 팩토리얼에 적용해본다.

1! = 1 x (1-1)!
    = 1 x 0! = 1
    = 1! 은 1이다.  ( 1! = 1 )
    따라서 0! == 1 

코드

#include <iostream> 
using namespace std;

int main(void){

    int N = 0;
    long long answer = 1;
    cin >> N;

    for(int i = 1; i <= N; i++){
        answer = answer * i;    
    }
    cout << answer;

    return 0;    
}

문제

스타트와 링크 백준 14889번

리뷰

N개 중에 중복없이 N/2 개를 고른다. N과 M 문제를 다시 풀어보고 이 문제를 풀었다.

1 2 3 4 번 사람이 있으면, (총 인원 4명)

1 2 이렇게 두 명만 A팀으로 고르면 3 4 는 자동으로 B팀으로 정해진다.

그리고 1 2 를 고르면 다음에는 1 3 을 선택해야 한다.

그런데 두 명을 고르는데, 3번 사람 부터 고를 때는. 3 1 이 아니라 3 4 를 골라야 한다.

3번 사람을 고른 상태에서는, 4번 사람만 고를 수 있다.

앞서 고른 수보다 큰 수를 골라야 1 3, 3 1 처럼 중복 없이 고를 수 있다. N과 M 2에서 풀었던 코드의 구조를 따왔다. (조합)

N/2 명을 고르면 팀이 나눠진 것이다.

그 다음에는 벡터 A, B 에 숫자를 넣어두고, power 배열의 인덱스를 이용해서 능력치의 합을 구한다.

abs 함수로 절대값을 구해 처리했고 min 함수로 차이의 최소값를 계산했다.

코드

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;

int N; 
int ch[21]; // 사람 선택 할 때 중복 방지  
int map[21][21];
int mindiff = 2e9;

void go(int index, int cnt){

    if(cnt == N/2){ //  N/2만큼 골랐다면, 팀 나눈다.  

         vector<int> S, L;
         int Ssum = 0, Lsum = 0;

         for(int i = 0; i <N; i++){ // 팀 나눠서 벡터에 담는다.  
             if(ch[i]) S.push_back(i);
             else L.push_back(i);
        }

        for(int i = 0; i < S.size(); i++){ // 팀별로 능력치 합  
            for(int j = i+1; j < S.size(); j++){
                Ssum += (map[S[i]][S[j]] + map[S[j]][S[i]]);
                Lsum += (map[L[i]][L[j]] + map[L[j]][L[i]]);
            }
        }

        mindiff = min(mindiff, abs(Ssum-Lsum) ) ; // 차이값 갱신 
        return;
    }

    for(int i = index; i < N; i++){ // index 자리의 사람 선택 
        if(ch[i]) continue; // 이미 선택한 사람이면 지나감 

        ch[i] = 1; // 선택 
        go(i+1, cnt+1); // 다음 사람 선택하러 재귀호출 
        ch[i] = 0; // 선택 안 함.
    }

}

int main(void){

    cin >> N;

     for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
             scanf("%d", &map[i][j]);
        }
    }

     go(0, 0);

     cout << mindiff;

    return 0;
} 

문제

Two Dots 백준 16929번

리뷰

처음에 BFS로 시도했는데, 문제의 에제 입출력 4개중에 3개만 맞아서 멘붕이 왔다.

3 4
AAAA
ABCA
AADA // 이건 사이클이 없는데. "Yes"를 출력한다... 

그래서 사이클 관련 질문게시판 글을 읽고 DFS로 시도해봤다.

시작지점을 목적지점 삼아서 탐색을 했다.

사이클은 시작점과 끝점이 같다고 생각할 수 있다.

그런데, 시작점 부터 방문 배열에 1로 체크해두면, 방문 안 해본 곳을 찾아서 탐색하기에는 시작점이자 끝점에 되돌아갈 수 없다. 그래서 이미 방문했더라도, 목적지인지 검사했다. 

일단 시작할 때 시작점 자체가 cnt 1개니까 1로 시작한다.

for(int i = 0; i  < N ; i++){  // 모든 지점에서 DFS 시작
    for(int j = 0; j < M ; j++){

        start_x = i; // 목적지 설정  
        start_y = j;

        DFS(i, j, 1); // 시작점에서 이미 cnt = 1 로 시작 

        if(stop_flag) break;
    }
} 

DFS를 시작하면, 방문 표시를 해두고, 상하좌우 4방향을 검사한다.

이 때, 아래의 3가지 조건을 만족하면 다음 칸으로 이동한다.

if(!boundary(next_x, next_y)) continue;  // 범위 내 인지  

if(B[start_x][start_y] != B[next_x][next_y]) continue; // 색깔이 같은지  

if(check[next_x][next_y] == 0){ // 미방문인지  

만약, 세번째 if 문에서 조건을 만족시키지 않고, 방문 했더라도, 목적지라면 탐색을 끝내야한다.

여기서 중요한 건 cnt가 4 이상인지도 함께 확인해야 한다는 것이다.

    if(check[next_x][next_y] == 0){ // 미방문인지  

        check[next_x][next_y] = 1;
        DFS(next_x, next_y, cnt+1); // 방문한다  
        check[next_x][next_y] = 0;

    }else{ // 목적지인지

        if(next_x == start_x && next_y == start_y && cnt >= 4){  // 4번 이상 움직여서 목적지 도달 
        stop_flag = true; // 탐색 끝!
        return;
    }
} 

맞는데 왜틀리지 ㅠㅠ 하고 골머리썩다가 BOJ 질문게시판에 글올려서 고수분들의 도움을 받았다. 정말 감사했다.

속시원했다.

코드

#include <iostream> 
#include <queue>
#include <algorithm>  
using namespace std;

int N, M;   // 행, 열  
char B[51][51]; //지도  
int check[51][51]; //방문 표시 지도

bool stop_flag = false;
int start_x, start_y; // 시작점을 '목적지'로 이용한다.  

// 4방향 
int dx[5] = {-1, 1, 0, 0}; 
int dy[5] = {0, 0, -1, 1};


// 지도 범위 내에 있는지 확인
bool boundary(int i, int j){   
    return (i >= 0 && i < N && j >= 0 && j < M) ? 1:0;
} 

void DFS(int now_x, int now_y, int cnt){ 

    if(stop_flag) return;

    check[now_x][now_y] = 1; // 방문  

    for(int i = 0; i<4; i++){ // 4방향 확인 

        int next_x = now_x + dx[i];
        int next_y = now_y + dy[i];

        if(!boundary(next_x, next_y)) continue;  // 범위 내 인지  

        if(B[start_x][start_y] != B[next_x][next_y]) continue; // 색깔이 같은지  

        if(check[next_x][next_y] == 0){ // 미방문인지  

            check[next_x][next_y] = 1;
            DFS(next_x, next_y, cnt+1); // 방문한다  
            check[next_x][next_y] = 0;

        }else{
            // 목적지인지  
            if(next_x == start_x && next_y == start_y && cnt >= 4){  // 4번 이상 움직여서 목적지 도달 
                stop_flag = true;
                return;
            }
        } 

    }

} 

int main(void){
     // freopen("input.txt", "rt", stdin);
     cin >> N >> M; 

    for(int i = 0; i <N; i++){
        for(int j = 0; j < M; j++){
            cin >> B[i][j];
        }
    }  // 입력받기 끝 

    string res = "";


    for(int i = 0; i  < N ; i++){  // 모든 지점에서 DFS 시작
        for(int j = 0; j < M ; j++){

            start_x = i; // 목적지 설정  
            start_y = j;

            DFS(i, j, 1); // 시작점에서 이미 cnt = 1 로 시작 

            if(stop_flag) break;
        }
    } 

    if(stop_flag) cout << "Yes";
    else cout << "No";

    return 0;    
}

문제

섬의개수 백준 4963번

리뷰

미로 탐색 문제와 비슷했다.

지도에서 땅은 1이고 바다는 0으로 표기되어 있다. 여기서 섬의 개수를 구한다.

이중 for문으로 모든 지점에서 BFS를 시작한다. 땅을 발견할 경우에만 BFS를 시작한다.

핵심은 땅을 발견했을 때, 그 인접한 (가로,세로,대각선) 땅은 전부 바다로 바꾸고 ( 탐색하며 발견한 1은 0으로. ) 끝내는 것이다.

그 지점의 BFS가 종료되면 섬 개수를 하나 센다. cnt + 1

설계 하고 코딩하고 디버깅 하는데 1시간 정도 걸렸다.

코드

#include <iostream> 
#include <queue>
#include <cstring> // memset()
#include <algorithm> // min(), pair STL
#define M_MAX 50
using namespace std;

int M[M_MAX+1][M_MAX+1]; //지도  
int w, h; // 너비, 높이  

// 8방향 
int dx[10] = {-1, -1, -1, 0, 0, 1, 1, 1}; 
int dy[10] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 지도 범위 내에 있는지 확인
bool boundary(int i, int j){   
    return (i >= 0 && i < h && j >= 0 && j < w) ? 1:0;
} 

void BFS(int x, int y){  // 시작점 땅 기준으로 근처 땅을 전부 바다로 만든다. 

    queue<pair<int,int>> q;

    q.push({x, y}); // 시작점 푸시  
    M[x][y] = 0; // 방문 표시  

    while(!q.empty()){ // 1 땅  0바다 

        int now_x = q.front().first;
        int now_y = q.front().second;
        q.pop();

        for(int i = 0; i < 8; i++){ // 8방향 검사  

            int next_x = now_x + dx[i];
            int next_y = now_y + dy[i];

            if(boundary(next_x, next_y) ){ // 범위 내부이면  

                if(M[next_x][next_y] == 1){ // 땅이라면 

                    q.push({next_x, next_y}); // 방문한 좌표 큐에 넣기  
                    M[next_x][next_y] = 0; // 바다로 만든다  
                }
            }
        }
    }

}

int main(void){

    while(1){

        // w, h  (열, 행)
        cin >> w >> h;

        if(w==0 && h==0) break;

        // 지도 입력받기  
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> M[i][j];
            }
        } 

        int cnt = 0; // 섬의 개수  

        for(int i = 0; i < h; i++){  // 시작점 탐색 ( 땅 찾기 )
            for(int j = 0; j < w; j++){

                if(M[i][j] == 1){ // 땅 발견  
                    BFS(i, j); 
                    cnt++;
                } 

             }
        } 
        cout << cnt << '\n';    

        memset(M, 0, sizeof(M)); // M배열 초기화
    }

    return 0;    
}

문제

나이트의 이동 백준 7562번

리뷰

이동 횟수를 체스판 좌표에 저장하려고 한 방식이 실패했다.

왜냐하면 그 좌표를 지나간 경우가 하나가 아니기 때문이다.

큐에는 이동 좌표를 저장했다. 이동 횟수인 int cnt는 따로 관리했다. 범위 내부이고, 안가본 좌표라면, 체스판 해당 좌표에 cnt를 저장하려고 했다.

int M[M_MAX+1][M_MAX+1]; // 체스판  - 0이 아니면 (미방문시) cnt값을 저장

int cnt = 0; 

queue<pair<int,int>> q;    //좌표를 저장하는 큐 
M[tmpX][tmpY] = cnt;

그래서 큐에 좌표와 cnt를 함께 저장했다.

int M[M_MAX+1][M_MAX+1]; // 체스판   - 방문1 미방문0 만 구분 
int cnt = 0; 

// q : 현재 좌표{a,b}와 이동 횟수cnt 저장  
queue<pair<pair<int,int>,int>> q;    

q.push({{a, b}, cnt} ); // 현재좌표와 이동횟수 0 푸시  
M[a][b] = 1; // 현재좌표 방문표시

범위 내부이고, 안가본 좌표라면, 이동한 좌표 tmpX tmpY 이동횟수+1 을 큐에 푸시했다.

// 8 방향 확인  
for(int i = 0; i < 8; i++){ 

    int tmpX = nx + dx[i]; // 가볼 좌표  
    int tmpY = ny + dy[i];

    if(boundary(tmpX, tmpY)){ // 범위 내부이면 

        if(M[tmpX][tmpY] == 0){ // 안가봤다면 

            q.push({ {tmpX, tmpY}, cnt+1} ); // 큐에 이동한 좌표와 이동횟수+1 해서  푸시 
            M[tmpX][tmpY] = 1; //방문표시   
        }
    }
} 

큐에서 pop 했을 때의 좌표가 목적지 좌표라면, 바로 cnt를 return 하게 했다.

어려웠다. 나중에 다시 풀어봐야겠다.

코드

#include <iostream> 
#include <queue>
#include <cstring> // memset()
#include <algorithm> // min(), pair STL
#define M_MAX 300
using namespace std;


int M[M_MAX+1][M_MAX+1]; // 체스판  
int M_LIMIT; // 체스판 크기 
int a,b, x,y; // 현재좌표, 목적좌표  

// 8방향 
int dx[10] = {1, 2, 2, 1, -2, -1, -2, -1}; 
int dy[10] = {2, 1, -1, -2, 1, 2, -1, -2};


// M_LIMIT 범위 내에 있는지 확인
bool boundary(int i, int j){   
    return (i >= 0 && i < M_LIMIT && j >= 0 && j < M_LIMIT) ? 1:0;
} 

int BFS(){

    int cnt = 0;

    // q : 현재 좌표{a,b}와 이동 횟수cnt 저장  
    queue<pair<pair<int,int>,int>> q;    

    q.push({{a, b}, cnt} ); // 현재좌표와 이동횟수 0 푸시  
    M[a][b] = 1; // 현재좌표 방문표시


    while(!q.empty()){

        pair<pair<int,int>,int> now = q.front();
        q.pop();

        int nx = now.first.first; // 현재 좌표  
        int ny = now.first.second; 
        int cnt = now.second; // 여기까지의 이동횟수 cnt 

        // 목적지라면 종료 
        if(nx == x && ny == y){
            return cnt;
        } 

        // 8 방향 확인  
        for(int i = 0; i < 8; i++){ 

            int tmpX = nx + dx[i]; // 가볼 좌표  
            int tmpY = ny + dy[i];

            if(boundary(tmpX, tmpY)){ // 범위 내부이면 

                if(M[tmpX][tmpY] == 0){ // 안가봤다면 

                    q.push({ {tmpX, tmpY}, cnt+1} ); // 큐에 이동한 좌표와 이동횟수+1 해서  푸시 
                    M[tmpX][tmpY] = 1; //방문표시   
                }
            }
        } 
    }
}

int main(void){

     int TC = 0;
     cin >> TC;

    while(TC--){
        cin >> M_LIMIT; // 체스판 크기(범위)
        cin >> a >> b >> x >> y; // 현재좌표, 목적좌표 
        memset(M, 0, sizeof(M)); // 체스판 0초기화 

         cout << BFS() << '\n';    
     }

    return 0;    
}

문제

사탕게임 백준 3085번

리뷰

기분이 엄청 좋다.

맞는데 왜틀리지.. 맞왜틀 중얼거리다가 드디어 채점창에서 "맞았습니다!" 를 봤다.

고생한 이유는 2가지다.

첫 째, 인접한 칸을 교환 후에, 전체 행, 전체 열을 검사하지 않아서 틀렸었다.

BOJ 질문게시판 글을 보다가 쿵 했다.

오른쪽과 교환한 경우, i행, j열, j+1열 이렇게 3 줄만 검사하면 되는줄 알았었다.

하지만 그게 아니었다. 그림그려보니까 다른 행과 열들도 영향을 받았다.

둘 째, 연속한 사탕개수 cnt를 세는데, max_cnt를 갱신하는 지점이 틀렸었다.

모든 행에서 연속한 사탕개수 cnt를 센다.

여기서 이중 for문 안에서 cnt를 잘 세놓긴 했다.

그런데, cnt 가 증가한 순간마다 max_cnt로 갱신해서 기억해줬어만 한다.

그렇지 않으면( 이중 for문이 끝나고 나서 max_cnt로 갱신하는 경우에는 ) , 똑바로 이중 for문 안에서 최대 cnt를 발견해놓고서도 max_cnt가 알 리가 없다.

읽고 도움을 받은 BOJ 질문게시판 글

인접한 칸을 교환하고 나서, 왜 전체 행, 전체 열을 전부 검사해야 하나?

예시 입력, 출력

질문게시판의 질문과 코드에서 나처럼 고민한 분들의 노고가 느껴졌다.

BOJ질문게시판에 글올리시고 답글 달아주시는 분들 모두 감사드린다. 항상 도움 받고 있다 :)

코드

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

// 사탕게임 (3085)

int N;
char B[51][51];
int max_num;

void swap(int i, int j, int d_flag){ // d_flag에 따라 아래 또는 오른쪽과 교환  

    char c = B[i][j];

    if(d_flag){ // 아래와 교환  
        B[i][j] = B[i+1][j];
        B[i+1][j] = c; 

    }else { // 오른쪽과 교환  
        B[i][j] = B[i][j+1];
        B[i][j+1] = c; 
    }
}


void check(int i, int j, int d_flag){

    swap(i, j, d_flag); // 교환 

    int cnt = 1;

    // 모든 행의 가로 확인 
    for(int x = 0; x < N; x++){

        cnt = 1;
        for(int y = 0; y < N-1; y++){

              if(B[x][y] == B[x][y+1]){
                  cnt++;
                  max_num = max(max_num, cnt); // 갱신된 cnt 저장 
            }else{
                cnt = 1;
            }
        }
    }


    // 모든 열의 세로 확인 
    for(int x = 0; x < N; x++){

        cnt = 1;
        for(int y = 0; y < N-1; y++){
              if(B[y][x] == B[y+1][x]){
                  cnt++;
                  max_num = max(max_num, cnt); // 갱신된 cnt 저장 
            }else{
                cnt = 1;
            }
        }
    }

    swap(i, j, d_flag); // 제자리 돌려놓기  

} 

int main(void){

    cin >> N;

     for(int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
            cin >> B[i][j];
        }    
    } // 입력받음  

    for(int i = 0; i < N; i++){ // 탐색  

          for(int j = 0; j < N; j++){

             if(j+1 < N){ // 오른쪽과 교환 가능  
                check(i, j, 0);
            }

            if(i+1 < N){ // 아래와 교환 가능 
                check(i, j, 1);
            }
        }    
    } 

    cout << max_num;    

    return 0;    
}

문제

후위표기식2 백준 1935번

리뷰

문자열을 입력받아서 char C 배열에 넣는다.

A, B, C ... 에 순서대로 대응하는 숫자값을 벡터 v에 넣는다. 여기까지가 주어진 입력받기다.

문자열 C를 순회하는데,

연산자가 나오면 스택 st에서 숫자 2개를 pop 해서 연산하고, 그 연산 결과를 푸시 한다.

숫자 (A, B, C 같은 알파벳) 이 나오면, 스택 st에 푸시한다.

C B A 순으로 입력 들어오지 않으니까, 문자 'A' 에서 65를 빼면 v 의 인덱스가 나온다.

for(int i = 0; C[i] != NULL; i++){   // 문자열 C 순회 

        if(C[i] >= 'A' && C[i] <= 'Z'){ // 숫자면, push

            // C[i]에서 'A' ASCII 65를 뺀다. v의 인덱스 나옴. -> 앒파벳에 대응하는 num  
            st.push( v[C[i]-65] ); 

        }else{ // 연산자 만나면, 숫자 2개 pop 해서 연산   

            double b = st.top(); // 연산 순서에 유의해서 먼저 pop 한 것이 b 다. 
            st.pop();
            double a = st.top();
            st.pop();
            double ans = 0.0; // a와 b의 연산 결과를 저장할 ans 변수 

            if(C[i] == '*'){
                ans = a*b; 
            } // 연산자에 대응해서 연산 
              // ... 

             st.push(ans); // 연산 결과를 푸시  
        }
    } 

답은 계산 결과를 소수점 2째자리 까지 출력하는 것을 유의한다.

코드

#include <iostream> 
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// 후위표기식2  PostfixNotation2  (지아) 

int N;
char C[101];
vector<double> v;
stack<double> st;

int main(void){

    cin >> N;

     scanf("%s", &C);

     while(N--){ // 알파벳 N개 입력받기  (A부터 순서대로 N개 입력받는다) 
         int num = 0;
         cin >> num;
         v.push_back(num);
    } // 입력받기 끝 


    // 문자열 C 순회
    for(int i = 0; C[i] != NULL; i++){   

        if(C[i] >= 'A' && C[i] <= 'Z'){ // 숫자면, push

            // C[i]에서 'A' ASCII 65를 뺀다. v의 인덱스 나옴. -> 앒파벳에 대응하는 num  
            st.push( v[C[i]-65] ); 

        }else{
            // 연산자 만나면, 숫자 2개 pop 해서 연산   
            double b = st.top();
            st.pop();
            double a = st.top();
            st.pop();
            double ans = 0.0;

            if(C[i] == '*'){
                ans = a*b;
            }else if(C[i] == '/'){
                ans = a/b;
            }else if(C[i] == '+'){
                ans = a+b;
            }else if(C[i] == '-'){
                ans = a-b;
            }

             st.push(ans); // 연산 결과를 푸시  
        }
    } 

     printf("%.2f\n", st.top());  // 소수점 2째 자리까지 출력 유의! 

    return 0;    
}