개발 블로그

문제 링크 : 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/2064

문제

네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워크 주소’와 ‘네트워크 마스크’라는 두 개의 정보로 표현된다.

IP 주소는 네 개의 바이트로 구성되어 있으며, 각각을 10진수로 나타내고(앞에 0을 붙이지 않은 형태로) 사이에 점을 찍어 주소를 표현한다. 바이트이기 때문에 각각의 수는 0부터 255까지의 값을 갖게 된다. 네트워크 주소와 네트워크 마스크 역시 같은 형식으로 나타낸다.

IP 네트워크에 대해 올바르게 이해하기 위해서는 위와 같은 주소를 2진수로 이해하면 된다. 즉, 각각의 바이트를 8자리의 이진수로 나타내고, 이를 네 개 붙여놓은(앞에서부터) 32자리의 이진수를 생각해 보자. IP 네트워크에는 기본적으로 2m 개의 컴퓨터(혹은 IP 주소)가 할당될 수 있다. 이 경우의 네트워크 주소는 앞의 32-m 자리가 임의의 수(0 또는 1)로 구성되어 있고, 뒤의 m자리는 0으로 채워지게 된다. 네트워크 마스크는 앞의 32-m 자리가 1로 채워져 있고, 뒤의 m자리는 0으로 채워지게 된다. 이와 같은 IP 네트워크에는 앞의 32-m 자리가 네트워크 주소와 일치하는 모든 IP들이 포함되게 된다.

예를 들어 네트워크 주소가 194.85.160.176이고, 네트워크 마스크가 255.255.255.248인 경우를 생각해 보자. 이 경우, 이 네트워크에는 194.85.160.176부터 194.85.160.183까지의 8개의 IP 주소가 포함된다.

어떤 네트워크에 속해있는 IP 주소들이 주어졌을 때, 네트워크 주소와 네트워크 마스크를 구해내는 프로그램을 작성하시오. 답이 여러 개인 경우에는 가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.

입력

첫째 줄에 정수 n(1≤n≤1,000)이 주어진다. 다음 n개의 줄에는 각 컴퓨터의 IP 주소가 주어진다.

출력

첫째 줄에 네트워크 주소를, 둘째 줄에 네트워크 마스크를 출력한다.

접근 방법

1) 입력받은 각 ip 주소를 의미하는 문자열을 '.'를 기준으로 split 하여 inputIp[]에 넣는다. 다음 바이트 자리 숫자를 입력받을때는, 먼저 왼쪽으로 8비트를 shift한 뒤에 입력받은 숫자를 or 연산을 이용하여 inputIp[]를 갱신한다.

2) 주소의 4byte 즉 32bit에서 하나라도 다른 비트가 나온 첫 비트를 찾는다. 

   i                            31 ...     24 23... 16  15...      8   7...         0

  194.85.160.177 = 10000010 1010101 10100000 10110001

  194.85.160.183 = 10000010 1010101 10100000 10110111

  194.85.160.178 = 10000010 1010101 10100000 10110010

에서는, 첫번째부터 i = 31이라고 했을 때 i=31...3까지는 모두 비트가 일치하다가 i=2에서 일치하지 않는 비트가 처음으로 생긴다.

비트가 일치했던 i=31...3에 대해서는 subnet |= 1 연산을 통해서 

subnet : 11111111 11111111 11111111 11111000 (255.255.255.248) 를 만들어 놓는다.

4) print() 에 파라미터로 subnet & inputIp[0]를 넘겨서 네트워크 주소를 출력하고, 

subnet도 넘겨서 네트워크 마스크를 출력한다.

print() 가 동작하는 원리

for문에서 shift의 값은 24, 16, 8,0 순으로 변한다. 

그래서 32비트로 넘어온 num을 네파트로 나눠서 1byte씩 8비트의 수를 십진수로 출력하게 되는 것이다. 

(1<<8) -1 는 2^8에서 1을 뺀 수로 8비트가 1로 이루어진 수를 의미한다. 이 수와 & 연산을 한다는 것은 num>>shift의 값 중 8비트만 출력하겠다는 의미이다. 

//
//  SM_BOJ2064_IP주소.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//3:42
//

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;

void print(int num){    //num은 32비트 수 -> 8비트씩 끊어서 십진수로 출력해야함
    
    int shift = 24;
    for(int i = 0; i<4; i++, shift -= 8){
        cout << ((num>>shift) & (1<<8)-1);  //31bit->7bit... 24bit->0bit /// 23bit->7bit...
        if(i != 3) cout << '.';
    }
    cout << "\n";
}
int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    int n; cin >> n;
    string ip;
    
    //ip 주소 입력
    int inputIp[n];
    for(int i = 0; i<n; i++){
        cin >> ip;
        istringstream ss(ip);
        string tmp;
        while(getline(ss,tmp,'.')){
            inputIp[i] <<= 8;       //8비트 왼쪽으로 shift 해서 자리 만들고
            inputIp[i] |= stoi(tmp);    //or 연산
        }
    }
    
    int subnet = 0; //inputIp[n]들이 모두 어디 byte까지 같은지
    //각 바이트 자리끼리 비교해서 달라지는 비트 몇번 비트인지 확인
    int netAddr = 0;
    for(int i = 31; i>=0; i--){
        
        int bit = 1 << i;   //i만큼 왼쪽 shift -> &연산을 통해 오른쪽에서 i번째 비트를 뽑아 비교하기 위함.
        bool isContinue = true;
        for(int r=1; r<n; r++){
            if((inputIp[0] & bit) != (inputIp[r] & bit)){//기준은 첫번째로 입력한 ip 주소.
                isContinue = false;         //비트 달라지는 즉시 검사 중단.
                break;
            }
        }
        if(!isContinue) break;
        else {
            subnet |= bit;         //n개의 ip주소에 대해 해당 비트가 모두 같으면 1로 채워나감.
            
        }
    }
    
    //subnet : 11111111 11111111 11111111 11111000 (255.255.255.248)
    
    print(subnet & inputIp[0]); //뒤에 m개만(다른부분만) 0으로 만들고 앞의 32-m개는 inputIp[0]와 같게
    print(subnet);
    
    
    
    
    
    return 0;
}

참고 : (https://donggod.tistory.com/88)

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

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

접근 방법

먼저 문제를 풀기 전에 조건의 3번, 4번에 적힌 문장 의미를 잘 이해해야 한다.

3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.

  는 결국 조건 4와 같이 연속 문자열의 양 끝이 그 어떤 문자로 이루어졌을 것이다.

 (W = "baa", K = 2  or W = "aaa", K=2  or W = "abaa", K = 2)

4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

   이 조건은 어떤 문자와 해당 문자가 같으므로, 역시 연속 문자열의 양 끝이 그 어떤 문자로 이루어졌을 것이다.

  (W = "baaabaab", K = 5)

start 인덱스를 정하고, start 인덱스를 기준으로 end 인덱스를 옮겨가면서 완전탐색을 하면 시간초과가 난다.

그래서 W의 모든 문자에 대해서가 아닌,

K개 이상 나온 알파벳을 후보로 정한 후에, 그 후보들에 대해서만 인덱스 검사를 해서 최소와 최대 길이를 구하면 된다.

먼저 예시인 W = "abaaaba", K=3에 대해 살펴보자.

크기가 26인 벡터 배열을 만든다음, W에서 해당 알파벳의 인덱스를 벡터에 저장한다. 

i=0일때의 W[0] = 'a'이므로 a를 의미하는 W[0]-97 = 0을 인덱스로 지정한다.

i=1일때의 W[1] = 'b'이므로 b를 의미하는 W[1] - 97 = 1을 인덱스로 지정한다.

이제 벡터배열을 돌면서 크기가 K이상인 벡터에 대해서만 검사를 진행한다.

문자열에 K개가 포함되야 하므로, 검사는 (벡터크기 - K + 1) 번 진행한다. 즉 j = 0부터 j = vecList[i].size() - K 까지 검사한다. 

또한 K개를 포함하는 연속문자열의 길이를 구하기 위해서는, 

vecList[i][j+K-1] - vecList[i][j] + 1

와 같이 구할 수 있다.

위의 i = 0일 때, 벡터 {0,2,3,4,6}을 예로 들어보면 

3-0 +1 = 4 (aaba)

4-2 +1 = 3 (aaa)

6-3 + 1 = 4 (aaba)

와 같이 구할 수 있다. 

//
//  문자열_BOJ20437_문자열게임2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/09.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

int main(){
    
    int T;
    cin >> T;
    
    vector<int> vecList[26];

    for(int test_case = 1; test_case <=T; test_case++){
        string W;
        int K;
        cin >> W >> K;
        
        int mini = 100000;
        int maxi = 0;
        for(int i = 0; i<26; i++) vecList[i].clear();
        for(int i = 0; i<W.length(); i++){
            int num = W[i] - 97;    // 's' = 18
            vecList[num].push_back(i);      //해당 문자의 인덱스를 넣음.
        }
       
        for(int i = 0; i<26; i++){
            int vsize = (int)vecList[i].size();
            if(vsize >= K){ //조건을 만족하는 후보 알파벳들만 고려해서 탐색함으로써 시간 초과 해결.
                for(int j = 0; j<=vsize - K; j++){  //최소 K개를 포함해야 하므로, 만약 vsize=5이고, K=3이면 j=0,1,2까지만 검사하면 됨.
                    mini = min(mini, vecList[i][j+K-1] - vecList[i][j] + 1);
                    maxi = max(maxi, vecList[i][j+K-1] - vecList[i][j] + 1);
                }
            }
        }
        
        if(mini == 100000 || maxi == 0) cout << -1 << "\n";
        else cout << mini << " " << maxi << "\n";
        
    }
    
    return 0;
}

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

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

접근방법

처음에는 문자열의 각 인덱스에 대해서 substr()를 호출해서 검사했는데, 시간초과가 났다.

그래서 KMP알고리즘을 이용하였다.

KMP 알고리즘을 사용하기 위해서는 주어진 문자열에 대해 먼저 Failure Function을 구해야한다.

*Failure Function 이란? 

  - KMP 알고리즘에서 mismatch 발생 시, 다음번에 비교해야 할 Pattern 상의 위치를 알려주는 함수.

  - Failure Function F(j) : index[0] ~ index[j] 까지 proper prefix와 proper suffix가 매치되는 최대 길이를 저장한다.

먼저 왼쪽 그림을 보면 쉽게 이해할 수 있다.

1) j = 5 에서 mismatch가 발생했다.

2) F[j-1] = F[4]를 확인한다. 

3) F[4] = 2 이므로 index = 0과 1에 해당하는 앞의 두 문자("ab"는 검사할 필요 없이 스킵한다.)

4)  index = 2 부터 재탐색한다.

* F[4] = 2 라는 것은 가장 길게 match 되는 p.p와 p.s 길이를 의미하기도 하지만, 다음 스텝에서 비교해야할 pattern의 index를 의미하기도 한다. 

Failure Function을 구하는 코드는 아래와 같다.

void FailFunc(string pattern){
	int len = pattern.length();
    int j = 0;
	vector<int> failVec(len, 0);	//0번 인덱스는 무조건 0
    
    for(int i = 1; i<len; i++){
    	while(j>0 && pattern[i] != pattern[j]){		//j = 0이거나 mismatch 발생하면 -> 비교 시작 지점(j) 위치 조정. 
		j = failVec[j-1];
        }
        
        if(pattern[i] == pattern[j]) failVec[i] = ++j;		//일치하면 계속 i와 j 증가시켜나감.
    }
}

이제 위의 코드에 따라 차근차근 "abaaba"의 Failure Function을 구해보자.

step 1) i = 1, j = 0에서 시작한다.

step 2) i = 1, j = 0 -> mismatch -> i++ (아직 j가 0 이므로 i만 증가)

step 3) i = 2, j = 0 -> match -> i++, ++j  -> F[2] = 1

step 4) i = 3, j = 1 -> mismatch -> j = F[1-1] = F[0] = 0

step 5) i = 3, j = 0 -> match -> F[i] = ++j -> F[3] = 1

step 6) i = 4, j = 1 -> match -> F[i] = ++j -> F[4] = 2

step 7) i = 5, j = 2 -> match -> F[i] = ++j -> F[5] = 3

이제 Failure Function을 이용해서 KMP알고리즘으로 전체 문자열에서 주어진 부분 문자열을 찾을 수 있는지 검사해보자.

수도코드는 위와 같다. Failure Function을 구하는 알고리즘과 유사하다.

match가 되었을 때, pattern을 가리키는 j가 문자열의 끝을 가리키고 있으면 부분 문자열을 찾은것이다! 

코드로 구현하면 아래와 같다.

bool KMP(string S, string P){
	vector<int> failVec = FailFunc(string P);
    int j = 0;
    for(int i = 0; i<S.length(); i++){
    	while(j>0 && S[i] != P[j]){					//mismatch면 Failure Function 참고
    		j = failVec[j-1];
    	}
        
    	if(S[i] == P[j]){
        	if(j == P.length() -1) return true;		//match인데 끝까지 검사한거면 
            else j+=1;								//아직 끝까지 검사 안 했으면 j 증가
        }
    }
   return false;
}

구현 코드

//
//  문자열_BOJ16916_부분문자열.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/09.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

vector<int> failFunc(string P){
    int plen = (int)P.length();
    vector<int> failVec(plen, 0);
    int j = 0;
    for(int i = 1; i<plen; i++){
        while(j>0 && P[i]!=P[j]){
            j = failVec[j-1];
        }
        if(P[i] == P[j]){
            failVec[i] = ++j;
        }
    }
    return failVec;
}

int KMP(string S, string P){
    vector<int> failVec = failFunc(P);
    int j = 0;
    
    for(int i = 0; i<S.length(); i++){      //S 길이 기준
        while(j>0 && S[i] != P[j]){
            j = failVec[j-1];
        }
        if(S[i] == P[j]){
            if(j== P.length()-1) return 1;      //P 길이 기준
            else j+=1;
        }
    }
    return 0;
    
}

int main(){
    
    string S, P;
    cin >> S >> P;
 
    N = (int)S.length();
    
    cout << KMP(S, P);

    return 0;
}

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

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

접근 방법

substr()함수를 이용해서 풀 수 있는 간단한 문자열 비교 문제였다. 그런데 생각보다 정답률이 낮아서 의아했는데 문제를 풀어보니 주의할 점을 고려해주지 않으면 오답처리되기 쉽다는 것을 알 수 있었다. 문제 조건을 꼼꼼히 확인하는것이 중요하다는 것을 새삼 깨달을 수 있게 해주는 문제였다. 주의할 점은 다음과 같이 두 개 정도 있다.

주의할 점 1)

문서의 길이가 단어 길이보다 작은 경우에는 예외 처리를 따로 해줘야 한다. 이 부분을 고려해주지 않아서 런타임 에러가 났다.

주의할 점 2)

일치하는 문자열을 찾은 뒤, 중복되지 않도록 단어의 길이만큼 문서를 스킵하기 위해 인덱스를 임의로 조정해주는데, 

이때 i+=wordLen이 아닌 i+=(wordLen -1)만큼만 증가시켜줘야한다.

왜냐하면 어짜피 for문 안에서 i++라는 증감식에 의해 인덱스가 1 증가하기 때문이다.

//
//  문자열_BOJ1543_문서검색.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int main(){

    string documents, word;
    getline(cin,documents);
    getline(cin, word);
    
    int ans = 0;
    
    int wordLen = (int)word.length();
    
    if(documents.length() < wordLen) cout << 0;	//1. 예외처리 해주지 않으면 런타임에러
    else{
        for(int i = 0; i<=documents.length()-wordLen; i++){
            
            if(documents[i] == word[0]){
                string sub = documents.substr(i, wordLen);
                if(sub==word){
                    ans++;
                    i += (wordLen -1);		//2. for문에서 어짜피 i증가되니까 여기서는 1 감소
                }
            }
        }
        
        cout << ans;
    }

    return 0;
}

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

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

접근 방법

처음에는 3중 포문을 돌면서 현재 문자열에 대해 n-1개의 전화번호를 다 돌면서 비교하는 완전탐색을 했는데 시간초과가 났다.

그러나 아래의 경우를 생각해보면 문자열을 sort() 한 뒤, 현재 문자열을 기준으로 삼고 현재 문자열이 바로 다음 문자열의 접두어가 되는지만 판단하면 시간 안에 해결할 수 있다. 

123

1234

134

=> NO

123

1245

13

=> YES

이때, 현재 문자열의 길이가 다음 문자열의 길이보다 길면 접두어가 될 수 없으므로 스킵하면 더욱 시간을 단축할 수 있다.

//
//  문자열_BOJ5052_전화번호목록.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int main(){
    int t; cin >> t;
    for(int test_case = 1; test_case<=t; test_case++){
        int n; cin >> n;
        string str;
        vector<string> vecStr;
        for(int i = 0; i<n; i++){
            cin >> str;
            vecStr.push_back(str);
        }
        sort(vecStr.begin(), vecStr.end());
        bool flag = true;
        for(int i = 0; i<vecStr.size()-1; i++){
            
            string cur = vecStr[i];
            string next = vecStr[i+1];
            flag = true;
            if(cur.length() > next.length()) continue;
            if(cur == next.substr(0, cur.length())){
                flag = false;
                break;
            }
        }
        if(!flag) cout << "NO\n";
        else cout << "YES\n";
    }

    return 0;
}

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

문제

B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

입력

첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36)

B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다.

출력

첫째 줄에 B진법 수 N을 10진법으로 출력한다.

접근 방법

입력한 문자열 N을 한글자씩 따라가면서 10진수로 변환해나간다.

해당 char 이 '0' ~ '9'인 경우와 'A'~'Z'인 경우로 나눠서 계산한다. 

//
//  문자열_BOJ2745_진법변환.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int main(){
    
    string N;
    int B;
    cin >> N >> B;
    
    int len = (int)N.length();
    int bit = len-1;
    
    int ans = 0;
    
    for(int i = 0; i<len; i++){
        
        char c = N[i];
        int num = 0;
        
        if(65<=c && c<=90) num = c - 55;    //'A' ~ 'Z'
        else num = c - '0';//'0' ~ '9'
        
        ans += num * pow(B, bit-i);
        
    }
    cout << ans;
\
    return 0;
}

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

문제

2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오.

입력

첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 주어진 수를 8진수로 변환하여 출력한다.

접근 방법

세자리씩 끊어서 8진수로 변환해야 하므로, 길이를 3의 배수로 맞춰준다.

str = "011001100"을 세자리씩 끊어서 생각해보자.

011 = 0*4 + 1*2 + 1*1 = 3

001 = 0*4 + 0*2 + 1*1 = 1

100 = 1*4 + 0*2 + 0*1 = 4

인 것을 확인할 수 있다. 

(16진수는 4자리씩 끊어서 생각하면 된다.)

//
//  문자열_BOJ1373_2진수8진수.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    string str; cin >> str;
    while(str.length() % 3 != 0){
        str = '0' + str;
    }

    for(int i = 0; i<str.length(); i+=3){   //i = 0, 3, 6, ,,
        int num = (str[i]-'0')* 4 + (str[i+1]-'0')* 2 + (str[i+2] - '0')* 1;
        cout << num;
    }
       
    return 0;
}