우주를 항해하는 탐험가

이 문제를 접하기 전까지는 Java로 문자열(String)을 다룰 때,

indexOf()와 charAt()만 잘 쓸 수 있다면 천하무적일 것이라 생각했다.

한창 프로젝트 기획 단계인 터라 바쁜 시기이지만, 점심시간에 문제의 지문을 얼핏 보았을 때에는 매우 간단해 보였다.

점심시간이 끝나기 전에 마쳐야겠다는 마음으로 아래와 같이 중첩 for문을 작성하여 가볍게 예제를 모두 패스하였다.

// 일부 발췌
String S = br.readLine();
String P = br.readLine();
br.close();
int L = S.length();
int l = P.length();
boolean flag = false;
outer: 
for(int i=0;i<L-l+1;i++) {
		for(int j=0;j<l;j++) {
			char now = P.charAt(j);
			if(S.charAt(i+j)==now) {
				flag = true;
			} else {
				flag = false;
				break;
			}
			if(j==l-1)
				break outer;
		}
}

그렇게 신속하게 제출 버튼을 눌러 버렸는데.....

나의 가뿐하고 후련하던 미소는, 28%에서 갑작스럽게 마주한 시간 초과 판정으로 인해 모두 무너져 버리고 말았다.

아니.. 대체 왜??

갑작스런 슬픔을 뒤로하고 프로젝트에 전념한 나는 집으로 돌아온 뒤

이 문제가 나를 거부한 이유가 무엇일지에 대해 다시 처음부터 생각하기 시작했다.

시간 초과가 뜬다면 항상 데이터 크기나 범위를 체크하는 것이 기본.

그래서 다시 확인해보니.... 무려 문자열의 최대 길이가 백만 단위이다.

내 기존 코드로 백만 단위 문자열 두 개의 일치 여부를 구하려 했다면 연산 횟수는 총 백만x백만...?

대략 연산 1억회에 순수하게 1초 정도의 시간이 소요된다고 하는데, 이 경우 무려 1조회의 연산이 필요하다.

아무 생각 없이 시간복잡도 O(n*m)짜리 알고리즘부터 사용해버린 나 자신을 반성하는 시간을 가졌다.

그렇다면 저렇게 어마무시한 규모의 문자열은 어떻게 다루어야 하는 걸까? 하는 마음으로 잠시 구글신께 기도하니,

KMP Algorithm이라는 어마어마한 가르침을 얻게 되었다.

K, M, P는 각각 어느 위대한 과학자들 이름에서 첫글자를 따온 것이라고 한다.

무려 세명이 머리를 맞대어 만든 알고리즘이란 과연 어떤 느낌일까? 아니나 다를까 역시 어려운 내용이었다.

하지만 감사히도, 나와 같은 중생들을 위해 친절한 가르침을 주시는 분들이 여럿 계셨다.

가장 큰 가르침을 얻은 분의 포스팅 링크를 아래와 같이 남긴다.

기존에 내가 사용한 방식처럼 중첩 for문으로, 길이가 백만인 두 문자열의 일치 여부를 무식하게 검증했다면

시간복잡도가 무려 O(백만x백만)=1조나 된다는 것은 이미 한번 언급한 바 있다.

KMP 알고리즘의 효용성은, 두 문자열을 각각 별도의 for문만 사용하여 검증할 수 있다는 데에 있다.

시간복잡도로 따진다면 O(n+m)=O(백만+백만)=2백만으로, 연산 횟수를 무려 50만배(!!)나 줄일 수 있다.

어떻게 이런 매직이 가능한 것일까.

처음 이해하기까지는 상당히 어려움이 있었지만, 직접 코드에 적용해서 돌려보며 생각하니

조금씩 깨달음을 얻을 수 있었다.

문제에서 주어진 것은 특정한 문자열 패턴 P와, 그 패턴의 존재 여부를 찾을 문자열 S이다.

(당연히 S는 P에 비해 길이가 같거나 길어야 한다.)

KMP 알고리즘에서는 문자열 P의 맨 앞 문자 n개와, 맨 뒤 문자 n개가 같아질 수 있는 최대 n값을 먼저 구한다.

처음에는, 이것도 결국 문자 하나하나 검색해야 하는 것이 아닐까?

이것으로 어떻게 S를 검증할 수 있다는 것일까? 하는 생각이 들었다.

하지만 실제로 코드를 작성해 보며 차근차근 과정을 검토해 보니 아래와 같았다.

(S의 길이 : L, P의 길이 : l)

int[] table = new int[l];
int index=0;
for(int i=1;i<l;i++) {
        
	if(index>0 && P.charAt(i)!=P.charAt(index)) { // (1)
		index = table[index-1];
	}
            
	if(P.charAt(i)==P.charAt(index)) { // (2)
		index++;
		table[i]=index;
	}
}

위 코드에서의 index는 결과적으로 현재 검증 진행 중인 P의 접두사 길이를 의미한다.

예를 들어 현재 index=2이라면, for문의 이전 원소(i-1)부터 앞쪽으로 길이 2만큼의 문자열이

P의 가장 앞쪽에 있는 문자 2개와 동일하다는 것이다.

(ex : abcdeabc에서 i=5인 경우 나타나는 a는 해당 문자열 맨 앞(i=0)의 문자 a와 동일하다.

i=6인 경우의 문자 b는 해당 문자열 두번째(i=1)에 위치하는 문자 b와 동일하다.

그런데 i=5의 문자 a도 i=0의 문자 a와 동일하므로, i=5~6의 문자열은 i=0~1의 문자열과 같다.

따라서 i=6 시점에서 확인할 수 있는 해당 문자의 가장 긴 접두사의 길이는 2이다.)

따라서 P의 앞쪽에서부터 하나씩 세어간 문자들과 현재 조사중인 문자들의 순서가 같다면,

접두사의 길이가 길어지고 있다고 판정할 수 있다.

단, 중간에 순서가 서로 다르다는 것을 찾게 된다면 접두사의 길이를 더는 늘릴 수 없다.

따라서 접두사의 길이가 index-1일 때 접두사의 가장 끝에 있는 문자가 현재 문자와 같은지를 대신 검증한다.

같다면 패턴의 처음부터 다시 일치 여부를 검증할 필요 없이,

해당 지점(index-1)에서의 index 값, 즉 접두사의 길이를 다시 도출하여 이어 검증하면 된다.

(ex: index=7일 때, table[6]=3이라면 index=3부터 검증)

만일 일치하지 않는다면, 그냥 처음부터 검증을 다시 시작해야 한다.

이 경우 접두사의 길이는 0이 되어 버리므로, 다시 index=0으로 초기화하는 수밖에 없다.

이 과정을 계속하여 패턴의 '진짜' 접미사가 되는 지점과 처음 마주친다면, 이 지점부터 index는 다시 1이 될 것이다.

만일 문자열 검색이 모두 끝날 때까지 index가 초기화되지 않고 일정 값을 가진다면,

해당 문자열 P는 유효한 접두사-접미사가 존재한다고 볼 수 있다.

(+ 만일 for문의 i가 0부터 시작한다면 똑같은 문자열 두개를 처음부터 비교하는 모양새가 된다.

따라서 index값은 P의 길이인 l과 항상 같아진다.)

같은 얘기를 계속 반복하는 것 같지만...

P 맨 앞 문자열과, P의 첫 번째 문자열을 제외한 모든 지점부터

앞쪽으로 최대 몇 칸까지의 문자열이 겹칠 수 있는지를 판정하여 table array에 기록하는 것이 핵심이라 보면 된다. 

여기까지만 확인하여도, S와 P를 비교하는 과정을 자연스럽게 유추할 수 있다.

boolean flag=false;
index=0;
for(int i=0;i<L;i++) {
	if(index>0 && S.charAt(i)!=P.charAt(index)) {
		index = table[index-1];
	}
	if(S.charAt(i)==P.charAt(index)) {
		if(index==l-1) {
			index = table[index];
			flag=true;
			break;
		} else {
			index++;
		}
	}
}

문자열 S의 특정 지점(어디든 무관하다)의 문자가 P의 index번째 문자와 같다면

S와 P 사이에 겹치는 문자열, 즉 P의 접두사 길이를 1씩 늘릴 수 있다.

만일 어느 지점에서 P의 '접두사' 길이가 P 자신과 같아진다면?

해당 지점으로부터 P의 길이 l 만큼의 문자열이 모두 P 전체 내용과 동일하다는 의미이다.

처음 table array 만드는 과정에서 여러차례의 멘붕을 겪은 결과,

그나마 S에서 P를 찾는 과정에 대해서는 빠르게 이해할 수 있었다.

S에서 현재 검색 중인 문자가 P의 현재 index 값과는 일치하지 않아도, 다른 위치의 값과 일치한다면

다음 문자는 P의 그 다른 위치의 값 다음 문자와 같은지 검증하면 된다.

이 과정에서 무의미한 반복문 사용이 획기적으로 줄어들 수 있게 된 것이다.

스스로도 쉽지 않은 개념이었기 때문에, 복습을 하는 과정에서 정리하고자 이 글을 작성한 것도 있다.

다행히 위와 같은 고난과 역경을 뚫고, 결국 맞았습니다!를 쟁취할 수 있었다.

나 역시도 며칠 후 다시 보면 이게 뭔 소리인가.. 싶을 것 같은 생각이 드는 탓에..ㅋㅋ

잊어버리기 전에 KMP 관련 문제들을 몇 개 더 도전해야겠다.

당신이 부족한게 아니에요.

이게 진짜 어려운 겁니다.

점화식을 구현하기 위해 사용하는 다이나믹 프로그래밍(Dynamic Programming; DP) 문제를 풀 때면,

무작정 케이스 별 경우의 수를 구해서 점화식을 찾는 것까지는 비교적 쉽게 되는 경우가 많았다.

하지만 왜 이 점화식으로 문제가 풀렸던 걸까? 라는 의구심이 사라지지 않는 경우도 종종 있었다.

그래서였는지 DP 문제를 풀 때마다 울렁증 비슷한 것이 항상 내 속 깊은 곳에 자리하곤 했다.

긴 추석연휴를 맞아 Solved.ac 티어 상승을 목표로 PS를 부지런하게 하며 보냈다.

그 와중 이 문제를 풀이하면서, 내 오랜 고민의 답은 의외로 가까운 곳에 있을지 모른다는 생각을 할 수 있게 되었다.

해당 문제는 아래와 같다.

1에서 11까지의 자연수를 1, 2, 3 세 가지 수의 합으로만 나타낼 수 있는 경우의 수의 총 가짓수를 구하는 문제이다.

각 수 간의 위치가 다른 경우도 모두 다른 경우로 취급한다.

처음 이 문제를 접근하는 과정에서 n=6인 케이스까지 직접 경우의 수를 하나하나 적어보면서 각 케이스별 가짓수를 구해 보았다.

이 과정에서, n=3인 케이스와 n=4인 케이스를 확인한 결과 점화식을 활용한 DP로 문제를 풀이할 수 있으리라는 확신이 들었다.

위 표를 기준으로 이전 케이스에 존재하는 경우의 수에 맨 뒤에 1을 하나 추가한 것들을 파란색으로, 아예 없던 케이스가 생겨난 경우를 붉은색으로 표시하였다.

따라서 까만색과 파란색 경우의 수 총합이 n=3일 때의 가짓수와 동일하고, 빨간색 경우의 수 총합이 순수하게 이전 케이스 대비 추가된 것과 같다.

아직 명확한 규칙을 확인하진 못했지만, 이전 케이스의 값과 영향을 주고받을 것은 분명하였기에 케이스 별 가짓수를 저장하는 배열을 만들고 세부 알고리즘을 수정하였다.

이렇게 저렇게 단순 반복을 계속하던 도중, 문득 지금까지 적어둔 모든 경우의 수를 아래와 같이 분류할 수 있지 않을까? 하는 생각이 들었다.

어떻게 이런 결과가 나올 수 있었을까?

원리는 매우 간단하다.

n=3인 모든 경우의 수에 3을 더한다면, 이는 모두 n=6인 경우의 수에 해당한다.

n=4, n=5인 경우도 마찬가지로, 각각 2와 1을 모든 경우의 수에 더해준다면 당연히 모든 수의 합은 6이 된다.

예를 들자면, n=3 케이스의 경우의 수 중 하나인 (2, 1)의 끝에 3을 추가한 경우, (2, 1, 3)이라는 경우의 수가 만들어진다.

(2, 1, 3)의 모든 수 합을 구한다면 2+1=3에 3을 더한 결과가 되어 2+1+3=6을 만족하게 된다.

따라서 아래와 같이 해당 케이스의 점화식을 정리할 수 있다.

a(n) = a(n-1) + a(n-2) + a(n-3)

점화식이 나온 이상 코드로 구현하는 것은 시간문제이다.

import java.io.*;

public class N9095 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		int[] arr = new int[12];
		arr[1]=1;
		arr[2]=2;
		arr[3]=4;
		for(int j=0;j<T;j++) {
			int n=Integer.parseInt(br.readLine());
			for(int i=4;i<=n;i++) {
				if(arr[i]==0) {
					// 1, 2, 3만 사용하므로 세 개 수에 대해서만 관리하면 됨
					// 끝에 1을 붙이는 케이스 : arr[i-1]
					// 끝에 2를 붙이는 케이스 : arr[i-2]
					// 끝에 3을 붙이는 케이스 : arr[i-3]
					arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
				}		
			}
			bw.write(arr[n]+"\n");
		}
		br.close();
		bw.flush();
		bw.close();
	}
}

결과는 깔끔하게 '맞았습니다' 였다.

단순히 코딩하는 법을 익히는 것이 아닌, 왜?를 생각하고 고민하는 과정에서 더욱 큰 성장의 기회를 가질 수 있는 것 같다.

보람찬 추석연휴였다 :)

몇 개월 전부터 처음 본격적으로 알고리즘 문제들을 풀기 시작하면서, 여러 차례의 고난이 나를 찾아왔다.

큰 수 연산, 반복문 시간 복잡도 해결, 데이터 타입 별 처리 조건 등

CS 관련 지식이 부족했던 나로서는 이런 기본적인 요소 하나하나를 이해하기 위해 많은 노력이 필요했다.

하지만 지나고 보니 이것들을 너무도 당연하다는 듯이 생각할 수 있게 된 것을 보면,

지금 내가 골머리를 앓고 있는 문제들도 언젠가 노력의 결과로 정복할 수 있으리라고 믿는다.

물론 새로운 문제들이 나를 찾아오겠지만, 받아들이리라 기꺼이.

아직도 햇병아리에 불과한 학생이지만, 지난 날을 짧게나마 되돌아 보았을 때 기억에 남았던 때를 하나 꼽는다면,

처음으로 소수 구하기 알고리즘을 만들었던 날이다.

학창 시절에 수학 공부를 소홀히 한 편은 아니었기에, 기본적인 소수(Prime Number)의 개념에 대해서는 기억하고 있었다.

단지 그것을 어떻게 구현할 것인가! 가 가장 큰 문제였던 것이다.

당시 내가 씨름하였던 문제를 간만에 찾아보니, 아래와 같다.

https://www.acmicpc.net/problem/1929

입력값의 최댓값이 무려 백만이다.

지금 생각하면 저정도 규모의 숫자에는 단순 for문 사용도 꺼려질 법 하지만, 당시의 나는 매우 용감했다.

그때의 내가 사용할 수 있는 언어는 오로지 C 뿐이었기 때문에, 아래와 같이 단순하게 코드를 짰다.

#include <stdio.h>

int main(void)
{
    unsigned int m, n;
    int t = 0;
    scanf("%d%d", &m, &n);   
    int TF[n*n]; 
    if (m<=2)
    {
        printf("2\n");
    }        
    for (int i = m ; i <= n ; i++)
    {
        for (int a = 0 ; a < n ; a++)
        {
            TF[a] = 0;
        }
        for (int j = 2 ; j < n ; j++)
        {
            if (TF[j] == 0)
            {
              if (i%j == 0)
              {
                  for (int k = 2 ; k < n/k ; k++)
                  {
                      TF[j*k] = 1;
                  }
                  break;
              }
              else if (i-1 == j)
              {
                  printf("%d\n",i);
              }
            }
        }
    }
    return 0;
}

최댓값 n이 백만까지 증가할 수 있는 조건임에도 무려 삼중(!!) for문을 사용하였고,

진행 중 Array index 값이 백만*백만으로까지 연산될 가능성이 있어 int type의 범위를 아득하게 초과하였다.

당연한 결과로 Segmentation Fault부터 발생하였다.

엎친데 덮친 격으로, 2부터 최댓값 n까지의 모든 자연수가 소수인지 아닌지 여부를 저장하는 배열마저도

Boolean array 사용법이 익숙하지 않았기에.. int array로 작성하여 판별하였다.

필요한 메모리만 생각해 보아도 숨이 막힌다.

(다만 이때부터 indent는 칼 같이 지켰다... 별도 Editor를 사용해서 코딩하던 시절은 아닌데도 말이다.)

이래서는 안되겠다는 생각으로 소수 알고리즘 관련한 글들을 여럿 읽었었다.

답을 미리 알고 싶진 않은 생각에 세부 코드를 읽어보진 않았고,

자연수 n가 n의 제곱근보다 같거나 작은 약수만을 가진다는 정리를 확인하여

sqrt를 활용하여 위의 무식한 코드에 그나마 백만 단위 숫자들끼리의 연산이 진행되지 않도록 막을 수 있었다.

그럼에도 (무려 C로) 시간 초과가 발생하는 것은 당연한 일이었다.

에라토스테네스의 체를 적용할까 하고 생각을 해보았지만,

당시 나의 구현 능력으로는 쉽게 해당 개념을 코드로 정리하기 어려웠다.

*

수차례의 좌절(?) 끝에 한동안 이 문제를 미루어 둔 채, 나는 Java를 새롭게 배우기 시작했다.

갓 Scanner와 System.out.println을 이용한 입출력 연습에 한창이던 시절에도

이 문제에 대한 머릿속의 묵직한 고민은 떠날 줄을 몰랐다.

처음 Java를 접하고 일주일 즈음 지나서, 다시 이 문제에 Java로 도전하였다.

C로만 코딩을 하다가 Java로 같은 알고리즘을 구현하려 할 때마다

아니 이걸 이렇게 쉽게 할 수 있었어??하는 허탈함과,

이걸 더 쉽게 해결할 수 있는 방법을 찾았기에 후련하다는 성취감이 함께 오갔다.

(이와 유사한 감정을 Python을 배우면서 다시 느끼고 있다.)

아래가 Java를 접하고 처음으로 해당 문제를 풀이한 코드이자, 처음으로 올바른 출력을 얻은 코드이다.

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);		
		int m = sc.nextInt();
		int n = sc.nextInt();
		double sqrtn = Math.sqrt(n);		
		int[] prime = new int[n+1];		
		if (m >= 1 && m < 3 && n >= 2 && n < 4)
			System.out.println("2");
		if (m >= 1 && n == 3)
			System.out.println("3");		
		for (int i = 2 ; i <= n ; i++) {
			for (int j = 2 ; j <= sqrtn ; j++) {
				if (i%j == 0) {
					if (prime[j] == 0 && i >= m) 
						System.out.println(i);
					for (int k = 1 ; k <=sqrtn ; k++) {
						prime[j*k]++;
					}
					break;
				} else if (j == (int) sqrtn && i >= m) {
					System.out.println(i);
				}
			}
		}		
		sc.close();
	}
}

여전히 3중 for문+if문의 향연으로 엄청나게 느릴 것이 예상되는 구조이지만,

에라토스테네스의 체 개념 자체를 어느 정도 이해하기 시작했기에 작성할 수 있는 코드이기도 했다.

최댓값 n 미만의 모든 자연수를 한 번씩만 탐색하며, 소수인지 아닌지 여부 판별과 소수 출력을 동시에 진행하고 있다.

다만 시간복잡도 측면에서는 여전히 답도 없이 끔찍한 코드이기에

확실히 처리 시간이 C로 문제를 풀이하던 시절에는 생각하기 어려운 수준으로 증가하는 것을 알 수 있었다.

다른 Java 제출자들의 속도와 비교했을 때에도 나의 코드가 압도적으로 느린 것을 보고 솔직히 자존심이 상했던 나는,

어떻게 하면 이 코드가 더 빨라질 수 있을지를 고민했다.

이런저런 소스들을 찾다 보니 중첩 if문/for문의 존재만으로 처리 속도는 하염없이 길어질 수 있고,

그 외 입출력 방식도 영향을 끼칠 수 있음을 알았다.

다만 그 당시 나는 아직 Object를 다루는 법에 대해서 본격적으로 익히기 전이었으므로,

최대한 알고리즘 자체를 변화시켜 연산 횟수를 줄이기 위한 방법을 고심하였다.

이후 얻은 주요한 결론은, 소수 판별 로직과 소수 출력 로직을 분리해야 한다는 것이었다.

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		boolean[] prime = new boolean[n+1];
		prime[0] = true;
		prime[1] = true;
		for (int j = 2 ; j <= n ; j++) {
			for (int k = 2 ; k*j <= n ; k++) {
				prime[j*k] = true;
			}
		}
		for (int i = m ; i <= n ; i++) {
			if (prime[i] == false)
				System.out.println(i);
		}	
		sc.close();
	}
}

코드 길이부터가 매우 간결해졌다.

무려 이전 코드 대비 3배 이상 빠른 처리 속도를 보였다. (부끄럽지만 약 3.4초 -> 1초 수준이다.) 

먼저 2부터 최댓값 n까지의 모든 소수가 소수인지 아닌지부터 판별하여, 드디어 boolean array에 index별로 저장한다.

Boolean array를 처음 Java에서 생성하였을 때 모든 원소의 기본값은 false이므로,

소수가 아닌 수들을 index로 가지는 원소의 값을 true로 설정하였다. 따라서 0과 1에 미리 true라는 초기값을 주었다.

이후 최솟값 m부터 n까지만 for문을 다시 돌려서,

이 수가 소수인지 아닌지를 boolean array에 저장된 값들로만 간편히 판별하여 if문을 작동하였다.

이를 통해 그다지 어렵지 않고, 느리지 않게 int 범위 모든 자연수 범위의 소수들을 출력할 수 있게 되었다.

이때의 경험으로 몇 가지 교훈을 얻을 수 있었다.

1. 최종 결과를 한 번에 얻으려 하지 말자.
2. 내가 쓰는 데이터 타입의 범위를 항상 체크하자.
3. 처리 시간 단축에 신경쓰자.

여전히 나는 아직도 매일 새로운 문제들을 보며 씨름하고, 며칠 간 똑같은 실수를 반복하며 좌절하곤 한다.

하지만 늘 여유를 잃진 않는다.

우리는 답을 찾을 것이다. 늘 그랬듯이.