우주를 항해하는 탐험가

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

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

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. 처리 시간 단축에 신경쓰자.

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

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

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