개발 블로그

문제 링크 : https://acmicpc.net/problem/15989

3
4
7
10

4
8
14

풀이 방법

[1]

1

=> 1가지

(0가지 일 수도 있는지?...)

[2] 

1 + 1

=> 1가지

[3]

1 + 1 + 1

2 + 1

=> 2가지

[4]

1 + 1 + 1 + 1

2 + 1 + 1 , 2 + 2

3 + 1

=> 4가지

[5]

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 , 2 + 2 + 1

3 + 1 + 1, 3 + 2

=> 5가지

[6]

1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1, 2 + 2 + 2

3 + 1 + 1 + 1, 3 + 2 + 1

3 + 3

=> 7가지

[7]

1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1 + 1, 2 + 2 + 2 + 1

3 + 1 + 1 + 1 + 1, 3 + 2 + 1 + 1, 3 + 2 + 2, 

3 + 3 + 1

=> 8가지

[8]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1), (2 + 2 + 2+ 2)

(3 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 1)

(3 + 3 + 1 + 1), (3 + 3 + 2)

=> 10가지

 [9]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1), (3 + 3 + 2 + 1)

(3 + 3 + 3)

=> 12가지

 [10]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1), (2 + 2 + 2+ 2 + 2)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1)

(3 + 3 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1), (3 + 3 + 2 + 2)

(3 + 3 + 3 + 1)

=> 14가지

 [11]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1 + 1), (3 + 3 + 2 + 2 + 1)

(3 + 3 + 3 + 1 + 1), (3 + 3 + 3 + 2)

=> 16가지

6부터 2씩 증가-> fail!!!

==========================

dp[n,k] : 1,,,k 를 활용해 n을 만드는 방법의 수로 가정하고 각 값을 구해보자. 

===========================================

• dp[n,1] = 1
• dp[n,2] = n/2(몫만) + 1
• dp[n-3] = dp[n-1, 1] +dp[n-2, 2] + dp[n-3, 3]   = 1 + {(n-2)/2} + 1 + dp[n-3,3]

import java.util.Scanner;

public class BOJ_15989_123더하기4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[][] dp= new int[10001][4];

        for(int n = 0; n<=10000; n++){
            dp[n][0] = 0;
            dp[n][1] = 1;
            dp[n][2] = n/2 + 1;
        }
        dp[1][2] = 1; dp[1][3] = 1;
        dp[2][2] = 1; dp[2][3] = 2;
        dp[3][2] = 2; dp[3][3] = 3;
        dp[4][2] = 3; dp[4][3] = 4;
        
        for(int i = 5; i<=10000; i++){
            dp[i][3] = 2 + (i-2)/2 + dp[i-3][3];
        }


        int n;
        for(int i = 0; i<T; i++){
            n = sc.nextInt();
            System.out.println(dp[n][3]);

        }
    }
}

문제 링크 : https://www.acmicpc.net/problem/1759

import java.util.*;

public class BOJ_1759_암호만들기 {

    static boolean[] visited;
    static char[] arr;
    static int L, C;
    static boolean chk(String str){
        int cnt1 = 0; //모음
        int cnt2 = 0; //자음
        for(int i = 0; i<str.length(); i++){
            if(str.charAt(i)=='a' || str.charAt(i)=='e' || str.charAt(i)=='i' || str.charAt(i)=='o' || str.charAt(i)=='u'){
                cnt1++;
            }
            else cnt2++;
            if(cnt1>=1 && cnt2>=2) return true;
        }
        return false;
    }

    static void dfs(int start, String str){
        if(str.length()==L){
            if(chk(str)){
                System.out.println(str);
                return;
            }

        }
        for(int i = start; i<C; i++){
            if(visited[i]==false){
                str = str + arr[i];
                visited[i] = true;
                dfs(i+1, str);
                str = str.substring(0, str.length()-1);
                visited[i] = false;
            }
        }


    }



    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        L = sc.nextInt();
        C = sc.nextInt();
        arr = new char[C];
        visited = new boolean[C];


        for(int i = 0; i<C; i++){
            arr[i] = sc.next().charAt(0);
            visited[i] = false;
        }
        Arrays.sort(arr);
        String initStr = "";

        dfs(0, initStr);

    }
}

문제 링크 : https://www.acmicpc.net/problem/2748

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

접근 방법

처음에는 재귀 함수로 풀었는데 시간 초과가 났다.

그래서 DP로 풀었는데 dp[]의 자료형을 int 형으로 지정해서 오답으로 처리됐다. F(90) = 2,880,067,194,370,816,120 이므로 dp[]는  long long 형으로 선언해줘야한다. 

F(45) = 1836311903
F(46) = 2971215073
이므로 n = 46부터 int형 범위를 넘어간다. 

* long long(8byte) : –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 
* long (4byte) : –2,147,483,648 ~ 2,147,483,647

의문) long형으로 선언해도 백준은 정답으로 처리돼서 테스트케이스에 n=90이 없나 싶었는데,

         VsCode에서도 F(90)이 정상적으로 출력된다. 이론상으로는 long long 이 맞는데 정답 처리 되는 이유를 잘 모르겠다.

#include <iostream>
using namespace std;

long long dp[91]={0,};

int main()
{
    int n; cin >> n;
    
    dp[0] = 0; dp[1] = 1;
    for(int i = 2; i<=n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n];
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/12865

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

접근 방법

이 문제는 유명한 '배낭 문제(https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C)' 이다.

DFS를 이용한 완전탐색으로 풀었더니 시간초과가 났다. DP로 빠르게 풀어보자.

i = 1 부터 N 까지

1) 해당 물건을 배낭에 담았을 때와

2) 배낭 리미트 K를 넘어가서 해당 물건을 담지 않았을 때를

고려하여 검사를 진행한다.

DP[i][k] : 1번째 물건부터 i번째 물건까지 고려했을 때, 담을 수 있는 가장 최대 가치라고 하자.

그리고 예제에 주어진 입력으로 아래 이차원배열 DP를 채워보자.

먼저 limit가 1일 때는 아무것도 담을 수 없다. 물건들 무게가 모두 1이 넘기 때문이다. 그래서 limit=1인 열은 모두 0으로 채운다.

limit = 2일때도 마찬가지이다. 

그리고 W[3]은 무게가 3이기 때문에 담을 수 있다. V[3] = 6이므로, DP[3][2]을 6으로 채워준다. 

limit = 3일 때

: W[1]과 W[2]는 담을 수 없다. limit 3을 넘어가기 때문이다. 0으로 채워준다. 

그리고 W[3]은 무게가 3이기 때문에 담을 수 있다. V[3] = 6이므로, DP[3][2]을 6으로 채워준다. 

그러면 네번째 물건까지 고려했을 때, 담은 물건의 최대 가치는 어떻게 될까?

W[4]는 5이기 때문에 네번째 물건은 담을 수 없다. -> 그렇기 때문에 4번째 물건까지 고려하기 직전인 3번째 물건까지 고려했을 때 최대 가치인 DP[3][3]을 DP[4][3]에도 넣어주면 된다. 

limit = 4일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 없다. DP[1][4]에는 0을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. DP[2][4]에는 두번째 물건의 가치 "V[2] = 8"을 채워준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건을 고려했을 때, 즉 두번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[3][4]에는 DP[2][4]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 없다. 그래서 세번째 물건까지 고려했을 때의 값인 DP[3][4]를 DP[4][4]에도 넣어준다. 

limit = 5일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 없다. DP[1][5]에는 0을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. DP[2][5]에는 두번째 물건의 가치 "V[2] = 8"을 채워준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건을 고려했을 때, 즉 두번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[3][5]에는 DP[2][5]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 있다. V[4] = 12로, 이 값은 세번째 물건까지 고려했을 때 가치인 8보다 크기 때문에 DP[4][5]는 12로 채워준다. 

limit = 6일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 있다. DP[1][6]에는 V[1] = 13을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. 그런데 V[2] =8이고, 이것은 첫번째 물건까지 고려했을 때, 즉 첫번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[2][6]에는 DP[1][6]의 값을 그대로 넣어준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건까지 고려했을 때 보다 가치가 더 적기 때문에 DP[3][6]에는 DP[2][6]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 있다. V[4] = 12로, 이 값은 세번째 물건까지 고려했을 때 가치인 13보다 작기 때문에 DP[4][6]는 DP[3][6]의 값을 그대로 채워준다. 

limit = 7일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 있다. DP[1][7]에는 V[1] = 13을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. 그런데 V[2] =8이고, 이것은 첫번째 물건까지 고려했을 때, 즉 첫번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[2][7]에는 DP[1][7]의 값을 그대로 넣어준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 이때, 이전과는 다르게 한번 더 생각해야한다!!!

왜냐하면 만약 무게가 3인 세번째 물건을 담으면, 백팩은 무게 4가 남게 된다.

그 남은 무게에서 최대 가치는-> "limit=4이고 두번째 물건까지 고려했을 때"인 DP[2][4]가 된다. 

그리고 만약 무게가 3인 세번째 물건을 담지 않으면, 두번째 물건까지 고려했을 때의 최대 가치인 DP[2][7]의 값을 DP[3][7]에도 채워주면 된다. 

즉, 정리하면 아래 두 경우 중 더 큰 값을 DP[3][7]에 채워준다.

case 1) W[3]을 담을 경우 : DP[3][7] = DP[2][7 - W[3]] + V[3]

case 2) W[3]을 담지 않을 경우 : DP[3][7] = DP[2][7]

결론은, case 1)에서 DP[3][7]은 8+6 = 14로서,

case 2)에서 DP[2][7]인 13보다 크기 때문에 

DP[3][7]에는 14를 채워준다. 

: 네번째 물건까지 고려했을 때도 위 상황과 같이 아래의 두 경우를 고려해서 적어주면 된다. 

case 1) W[4]를 담을 경우 : DP[4][7] = DP[3][7 - W[4]] + V[4]

                                                            = DP[3][7 - 5]       + V[4]  

                                                            = DP[3][7 - 5]       + V[4]

                                                            = 0                          + 12

case 2) W[4]를 담지 않을 경우 : DP[4][7] = DP[3][7] = 14

즉, DP[4][7] = max(12, 14) = 14.

점화식으로 표현하면 다음과 같다.

DP[i][k] (최대 k무게까지 담을 수 있고, 1~i번째 물건까지 고려했을 때, 최대 가치 합) ?

1) DP[i-1][k]                                                                                         (W[i] > k) : i번째 물건 무거워서 못 담을 때

2) max( DP[i - 1][k - W[i]]   +   V[i]  ,  DP[i-1][k] )                  (W[i] <=k and i>0) : i번째 물건 담았을 때

3) 0                                                                                                    (i = 0 and k = 0)                                                                        

//
//  DFS_BOJ12865_평범한배낭.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/08/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N, K;
int W[101] = {0,};
int V[101] = {0,};
int DP[101][100001];

void dp(){
    
    for(int limit = 1; limit<=K; limit++){
        for(int row = 1; row<=N; row++){
            //1. 담을 수 없을 경우
            if(W[row] > limit){
                DP[row][limit] = DP[row-1][limit];
            }
            //2. 담을 수 있는 경우
            else{
                DP[row][limit] = max(DP[row-1][limit - W[row]] + V[row]  ,  DP[row-1][limit]);
            }
        }
    }
    
}

int main(){

    cin >> N >> K;
    for(int i = 1; i<=N; i++){
        cin >> W[i] >> V[i];
    }
    
	//초기화
    for(int r=0; r<=N; r++)
    {
        DP[r][0] = 0;
    }
    for(int c = 0; c<=K; c++){
        DP[0][c] = 0;
    }

    dp();

    cout << DP[N][K];
    
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/1062

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

접근 방법

int형은 4byte( = 32bit) 이므로 0부터 (2^32 - 1)까지 표현할 수 있다. 

여기서 알파벳은 총 26개이므로 0번비트부터 25번 비트까지만 사용하므로 int 형 내에서 커버가능하다.

먼저 N개의 단어를 입력받는데, 이때 단어를 이루고 있는 알파벳을 체크해서 word[]에 비트마스크로 표시한다. 

ex) 0번째 단어가 "antarctica"라고 하면, 이 단어를 이루고 있는 알파벳 [a,c,i,n,r,t]를 아래와 같이 비트로 표현해서 word[0]에 저장한다.

그 다음으로 K의 값을 따진다.

case 1) 5보다 작으면 N개 단어 모두 읽지 못하게 될 것이다. 왜냐하면 N개의 단어들 중에 최대한 많이 읽어야 하는데, 각 단어는 무조건 "a,n,t,i,c"가 포함된다고 했기 때문이다.

case 2) 만약 K가 26이면 모든 알파벳을 알고 있으므로 N개의 단어 모두 읽을 수 있다.

case 3) K가 5도 아니고 26도 아니면 chcked 변수를 초기화한뒤 DFS()를 호출한다.

cheked 변수는 이때까지 배운 알파벳들을 비트로 표현한 것이다.

DFS()에서는 완전탐색으로 26개의 알파벳 중에 K-5개를 선택하는 모든 경우를 따지게 된다. 단, 시간복잡도를 줄이기 위해 start 파라미터를 이용해서 중복조합을 구했다. (a,b를 선택하는 경우나 b,a를 선택하는 경우나 같기 때문이다.)

toPick이 0이 되면, 즉 배워야할 알파벳을 다 선택했으면, 그 알파벳들로 읽을 수 있는 단어가 N개 중 몇개인지 카운트한다. 

알파벳을 선택하는 조합을 바꿀 때마다 "읽을 수 있는 단어 수의 최대값"을 갱신한다. 

모든 경우를 따진 뒤 최대값을 출력한다.

//
//  비트_BOJ1062_가르침.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int checked;
int word[50];   //N 최대 50개
int N, K;

int maxi = 0;

void DFS(int toPick, int start, int checked){    //증복조합
    
    if(toPick==0){  //배울 알파벳 골랐으면
        
        //그 알파벳들로 N개 단어 중 몇개 읽을 수 있는지 카운트해서 최대값 찾기
        int cnt = 0;
        for(int i = 0; i<N ;i++){
            if((word[i] & checked) == word[i]) cnt++;
        }
        if(maxi < cnt) maxi = cnt;
        return;
    }

    for(int i = start; i<26; i++){
        if((checked & (1<<i)) == 0){   //방문 안 한 경우에만
            checked |= (1<<i);
            DFS(toPick-1, i, checked);
            checked &= ~(1<<i);
        }
        
    }
}

int main(){
    
    cin >> N >> K;
    
    string str;
    for(int i = 0; i<N; i++){
        cin >> str;
        
        int num = 0;
        for(int j = 0; j<str.length(); j++){
            num |= 1 << (str[j] - 'a');
        }
        word[i] = num;
    }
    
    if(K<5) cout << 0;  //anta ~ tica 읽으려면 최소 a,n,t,i,c 5개 이상은 알고 있어야함
    else if (K==26) cout << N;
    else{
        
        //a, n, t, i, c 를 이미 알고 있음을 초기화.
        checked |= 1 << ('a'-'a');
        checked |= 1 << ('n'-'a');
        checked |= 1 << ('t'-'a');
        checked |= 1 << ('i'-'a');
        checked |= 1 << ('c'-'a');
        
        DFS(K-5, 0, checked);
        cout << maxi;
    }
 
    return 0;
}

문제 링크  : https://www.acmicpc.net/problem/4949

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

접근 방법

괄호의 짝을 찾는 문제는 스택 자료구조를 사용해서 쉽게 해결할 수 있다. 

1) 먼저 열린 괄호면 스택에 넣는다.

2) 닫힌 괄호면 스택의 top과 비교해서 짝이 맞으면 Pop한 뒤 탐색을 계속하고, 짝이 맞지 않으면 탐색을 즉시 종료한 뒤 no를 출력한다.

   이때, 만약 스택이 비었는데 닫힌 괄호가 들어올 경우도 예외처리를 해줘야한다! 

//
//  문자열_BOJ4949_균형잡힌세상.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/04.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool chkPair(char c1, char c2){
    if(c1=='(' && c2==')') return 1;
    if(c1=='[' && c2==']') return 1;
    return 0;
}

int main(){
    string str = "";
    
    while(true){
        getline(cin, str);
        if(str.length()==1 && str[0] == '.') break;
        
        stack<char> stk;
        bool flag = true;
        
        for(int i = 0; i<str.length(); i++){
            if(str[i] == '(' || str[i] == '[') {
                stk.push(str[i]);
            }
            if(str[i] == ')' || str[i] == ']') {
                
                if(stk.empty()){            //1. 아무것도 없는데 닫는 괄호면
                    flag = false;
                    break;
                }
                else{           //2. 스택에 열린 괄호 들어 있을 때,
                    //2-1. 짝 맞으면
                    if(chkPair(stk.top(), str[i])) stk.pop();
                    //2-2. 짝 안 맞으면
                    else {
                        flag = false;
                        break;
                    }
                }
            }
        }
        if(!flag) cout << "no\n";
        else{
            if(stk.empty()) {cout << "yes\n"; continue;}
            else cout << "no\n";
        }
    }
    
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/10953

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. A와 B는 콤마(,)로 구분되어 있다. (0 < A, B < 10)

출력

각 테스트 케이스마다 A+B를 출력한다.

접근 방법

A,B가 한 자리 정수이고 각 정수 사이에 항상 콤마가 낀 형식으로 입력이 주어지므로 문자열을 분리할 필요 없이 문자열의 인덱스에 접근하여 간단하게 해결할 수 있다. 

//
//  문자열_BOJ10953_A+B-6.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/04.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int main(){
    int T; cin >> T;
    string str = "";
    for(int i = 0; i<T; i++){
        cin >> str;
        int a = str[0]-'0';
        int b = str[2]-'0';
        cout << a + b << "\n";
    }
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/1991

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

접근 방법

value를 pair로 지정해서 각각 first 는 leftChild로, second는 rightChild를 설정해준다.

그 후 전위, 중위, 후위 탐색 알고리즘에 맞게 unordered_map의 key와 value를 이용해준다. 

//
//  Tree_BOJ19991_트리순회.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/01.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;

int N;
unordered_map<char, pair<char,char>> umap;

void preOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        cout << c;
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') preOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') preOrder(umap[c].second);
    }
    
}
void inOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') inOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') inOrder(umap[c].second);
        cout << c;

    }
    
}
void postOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') postOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') postOrder(umap[c].second);
        cout << c;

    }
    
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> N;

    for(int i = 0; i<N; i++){
        char p, n1, n2;
        cin >> p >> n1 >> n2;
        umap[p] = make_pair(n1, n2);
    }
    
    preOrder('A');
    cout << "\n";
    inOrder('A');
    cout << "\n";
    postOrder('A');

    
    return 0;
}