세상에는 프로그래머라는 하나의 직업명으로 부르기 힘들 만큼 다양한 종류의 프로그래머들이 있습니다. 같은 직업을 가졌지만 SI 프로그래머, 데이터베이스 프로그래머, 웹 프로그래머와 게임 프로그래머는 모두 전혀 다른 환경에서 다른 언어와 도구를 써서 프로그램을 작성하고, 전혀 다른 문제를 고민합니다. 과연 이런 분야 간의 차이를 뛰어넘는 좋은 개발자의 조건이 존재할까요?
프로그래밍을 하기 위해서는 많은 것을 알아야 합니다. 아무 생각 없이 키보드를 두드리는 것처럼 보이는 프로그래머의 머릿속에는 자신이 사용하고 있는 프로그래밍 언어의 특성, 프로그램이 동작할 하드웨어와 운영체제에 관한 지식, 사용하고 있는 라이브러리들에 대한 유의사항들이 회오리치고 있습니다. 프로그램이 사용할 수 있는 최대 메모리와 사용자가 답답해하지 않게 하기 위한 시간 제한도 유의해야 하고, 이 와중에 가능한 한 재사용성이 높은 간결한 코드를 작성해야 합니다.
이렇게 많은 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력은 분야를 막론하고 좋은 프로그래머가 되기 위해 필수적입니다. 이 책에서는 이런 능력을 문제 해결 능력이라고 부릅니다. 프로그래머가 사용하는 언어나 라이브러리, 알고리즘에 대한 지식들이 퍼즐의 조각이라면 문제 해결 능력은 적재적소에 퍼즐 조각을 배치하고 이들을 연결해서 큰 그림을 만드는 능력이라고 할 수 있습니다.
그러나 문제 해결 능력을 훈련하기란 굉장히 어렵습니다. 문제 해결 능력은 추상적인 기술이기 때문입니다. 자기 계발을 하고 싶은 프로그래머들은 새로운 언어와 프레임워크, 개발 방법들을 계속 배워 나가지만 이들을 조합하는 방법에 대해서는 배울 곳이 없습니다. 단지 경험이 생기면서 나아질 것이라고 막연히 짐작할 뿐입니다.
좋은 프로그래머가 되기 위한 좀더 나은 방법은 없을까요?
프로그래밍 대회에 참가하는 것은 문제 해결 기술을 연마하기에 가장 좋은 방법이라 할 수 있습니다. 다양한 종류의 프로그래밍 대회들이 있지만, 이 책에서 다루는 프로그래밍 대회들은 주로 짧은 요구사항을 제시하고, 이에 맞는 프로그램을 시간 안에 빠르게 작성하는 능력을 겨루는 대회입니다. 이때의 요구사 항이란 현업에서 접하는 형태의 요구사항이 아니라 대개 ‘어떤 값을 읽어들여 어떤 값을 계산하는 프로그램을 작성하시오.’라는 형태를 갖습니다.
프로그래밍 대회를 접해 본 적이 없는 분을 위해 간단한 문제를 하나 예로 들 어 보겠습니다.
커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다.
이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일 간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여 하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?
예를 들어 앞으로 6일 간 공연장을 빌리는 데 드는 비용이 각 {3, 1, 2, 3, 1, 2} 이라고 합시다. 이미 세 팀을 섭외했다고 하면, 3일 대신 4일 동안 공연을 진행 해서 평균 비용을 더 저렴하게 할 수 있습니다. 3일 동안의 평균 대여 비용을 최소화하는 방법은 2일째부터 4일째까지 공연장을 대여하는 것인데, 이때 하루 평균 (1+2+3)/3 = 2의 비용이듭니다. 반면 2일째부터 5일째까지 공연장을 대여하면 평균 비용이 (1+2+3+1)/4 = 7/4 밖에 되지 않습니다.
프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
입력의 첫 줄에는 테스트 케이스의 수 C(C≤100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 공연장을 대여할 수 있는 날들의 수 N(1≤N≤1000)과 이미 섭외한 공연 팀의 수 L (1≤L≤1000, L≤N)이 주어집니다. 그 다음 줄에는 N개의 숫자로 공연장 대여 비용이 날짜별로 주어집니다. 모든 비용은 100 이하의 자연수입니다.
입력에 주어지는 각 테스트 케이스마다 한 줄에 최소의 평균 대여 비용을 출력합니다. 10-7 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.
2
6 3
1 2 3 1 2 3
6 2
1 2 3 1 2 3
1.7500000000
1.5000000000
프로그래밍 대회의 문제들은 현업에서의 사양서와 아주 다르다는 것을 쉽게 알 수 있지요. 주목해 볼 만한 차이와 그들로부터 얻을 수 있는 장점들을 다음과 같이 정리할 수 있습니다.
이런 특성들은 프로그래밍 작업에서 문제 해결을 수련하기 위해 필수적인 요소만을 남겨 놓고 나머지를 전부 제외한 것이나 마찬가지입니다. 덕분에 프로그래밍 대회는 문제 해결을 공부하기에 아주 적합한 환경이라고 할 수 있습니다.
한 번쯤 해 볼 만하다고 느껴지나요?
프로그램의 수행 시간이 데이터베이스, 네트워크 접근 등이 아니라 CPU를 통한 계산에 대부분 소비된다는 말입 니다. ↩