1. PS란 무엇인가

이 시리즈에서 다루는 PS는 컴퓨터과학 분야의 Problem Solving의 약자로, 대충 입력이 주어질 때 원하는 시행을 해내는 프로그램을 짜는 일이라고 생각하면 편하다. 이때 프로그램의 실행 시간과 사용 메모리에 제한이 걸려 있어, 이를 만족하는 선에서 가동하는 프로그램을 짜기 위해 우리는 알고리즘을 구상하게 된다.

---

한 게임을 예시로 들어보자. 게임이 시작하면, 참가자에게 1부터 20까지의 정수들로 이루어진 길이 100의 수열을 알려준다. 참가자에게는 큰 종이와 펜이 주어진다. 참가자는 수열을 들은 후 원하는 만큼 준비 시간을 가질 수 있다. 준비 시간이 끝나면, 참가자는 5초마다 한 번, 총 100번의 질문을 받게 된다. 질문은 "$i$번째 수부터 $j$번째 수까지의 합은 얼마인가요?"의 형식으로 주어진다(단, $i \leq j$).

 

이 게임에 참가해 모든 질문에 대답할 수 있겠는가? 일단 통상적인 방법으로는 불가능하다. 5초 만에 100번의 덧셈을 해야 하기 때문이다. 하지만 이런 방법은 어떨까?

 

[준비 시간]

1. 종이에 수열의 각 수를 일렬로 적는다.

2. 각 수 아래에 첫 번째 수부터 해당 수까지의 합을 계산해서 적어놓는다.

3. 첫 번째 수의 앞(0번째)과 그 아래에는 0을 적는다.

 

[질의응답]

$i$번째 수부터 $j$번째 수까지의 합을 구해야 할 때, $j$번째 수 아래에 쓰여 있는 수와 $i-1$번째 수 아래에 쓰여 있는 수의 차를 계산해 답한다.

 

조금만 생각해보거나, 직접 해본다면 위 방식이 왜 정당하며, 왜 빠른지 이해할 수 있을 것이다. 매 질문마다 한 번의 뺄셈으로 답을 구해낼 수 있기 때문이다! 이 방법을 사용한다면 이 게임에 자신있게 참가할 수 있을 것이다.

 

위 예시를 컴퓨터 프로그램에 똑같이 적용할 수 있다. 같은 게임을 컴퓨터에게 시키는데, 이번에는 수열의 길이가 100만이고 질문 역시 100만회 이루어진다고 하자. 그렇다면 나이브한 방법으로는 100만번의 질문에 각각 최대 약 100만번의 덧셈을 해야 하는 상황이 발생한다. 그렇다면 컴퓨터는 총 1조 번의 연산을 해야 한다. 컴퓨터가 1초에 수억 번 정도의 연산을 할 수 있다는 잘 알려진 사실을 고려하면, 이 프로그램은 모든 질문에 대한 답을 내기까지 몇 분씩이나 걸릴 것이다. 하지만 위에서 제시한 방법을 사용한다면 준비시간에 약 100만회, 각 질문당 1회의 연산을 사용하므로 총 최대 약 200만회의 연산만을 필요로 한다. 이는 충분히 1초 안에 실행이 완료되는 프로그램이 된다. 이때 프로그램의 실행에 1초라는 제한 시간이 걸려 있었다면, 첫 번째와 같은 프로그램은 통과하지 못하고 두 번째 프로그램만 통과할 수 있을 것이다. 이것이 PS가 이루어지는 기초적인 방식이다. 같은 결과를 내는 프로그램이라도 실행 시간에 유의미한 차이가 날 수 있고, 우리는 실행 시간을 제한 시간 이내로 줄이는 것을 목표로 한다. 이때 실행 시간을 줄이기 위해서 적절한 알고리즘을 구상하는 것이 PS에서 가장 중요한 부분이라고 할 수 있다.

---

숙제)

본격적인 내용에 들어가기에 앞서 솔브닥의 클래스 2를 조금 풀어보는 것을 추천한다.