1장: 문제 해결과 프로그래밍 대회

1.1 도입

세상에는 프로그래머라는 하나의 직업명으로 부르기 힘들 만큼 다양한 종류의 프로그래머들이 있습니다. 같은 직업을 가졌지만 SI 프로그래머, 데이터베이스 프로그래머, 웹 프로그래머와 게임 프로그래머는 모두 전혀 다른 환경에서 다른 언어와 도구를 써서 프로그램을 작성하고, 전혀 다른 문제를 고민합니다. 과연 이런 분야 간의 차이를 뛰어넘는 좋은 개발자의 조건이 존재할까요?

프로그래밍은 문제 해결이다

프로그래밍을 하기 위해서는 많은 것을 알아야 합니다. 아무 생각 없이 키보드를 두드리는 것처럼 보이는 프로그래머의 머릿속에는 자신이 사용하고 있는 프로그래밍 언어의 특성, 프로그램이 동작할 하드웨어와 운영체제에 관한 지식, 사용하고 있는 라이브러리들에 대한 유의사항들이 회오리치고 있습니다. 프로그램이 사용할 수 있는 최대 메모리와 사용자가 답답해하지 않게 하기 위한 시간 제한도 유의해야 하고, 이 와중에 가능한 한 재사용성이 높은 간결한 코드를 작성해야 합니다.

이렇게 많은 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력은 분야를 막론하고 좋은 프로그래머가 되기 위해 필수적입니다. 이 책에서는 이런 능력을 문제 해결 능력이라고 부릅니다. 프로그래머가 사용하는 언어나 라이브러리, 알고리즘에 대한 지식들이 퍼즐의 조각이라면 문제 해결 능력은 적재적소에 퍼즐 조각을 배치하고 이들을 연결해서 큰 그림을 만드는 능력이라고 할 수 있습니다.

그러나 문제 해결 능력을 훈련하기란 굉장히 어렵습니다. 문제 해결 능력은 추상적인 기술이기 때문입니다. 자기 계발을 하고 싶은 프로그래머들은 새로운 언어와 프레임워크, 개발 방법들을 계속 배워 나가지만 이들을 조합하는 방법에 대해서는 배울 곳이 없습니다. 단지 경험이 생기면서 나아질 것이라고 막연히 짐작할 뿐입니다.

좋은 프로그래머가 되기 위한 좀더 나은 방법은 없을까요?

1.2 프로그래밍 대회

프로그래밍 대회에 참가하는 것은 문제 해결 기술을 연마하기에 가장 좋은 방법이라 할 수 있습니다. 다양한 종류의 프로그래밍 대회들이 있지만, 이 책에서 다루는 프로그래밍 대회들은 주로 짧은 요구사항을 제시하고, 이에 맞는 프로그램을 시간 안에 빠르게 작성하는 능력을 겨루는 대회입니다. 이때의 요구사 항이란 현업에서 접하는 형태의 요구사항이 아니라 대개 ‘어떤 값을 읽어들여 어떤 값을 계산하는 프로그램을 작성하시오.’라는 형태를 갖습니다.

프로그래밍 대회를 접해 본 적이 없는 분을 위해 간단한 문제를 하나 예로 들 어 보겠습니다.

문제: 록 페스티벌 (난이도: 하, 문제 ID: FESTIVAL)

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 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

프로그래밍 대회에서 배울 수 있는 것들

프로그래밍 대회의 문제들은 현업에서의 사양서와 아주 다르다는 것을 쉽게 알 수 있지요. 주목해 볼 만한 차이와 그들로부터 얻을 수 있는 장점들을 다음과 같이 정리할 수 있습니다.

  1. 프로그래밍 대회에서 작성하는 프로그램들은 그래픽 인터페이스 등을 전혀 사용하지 않으며, 단순히 텍스트 파일을 읽어들이고 텍스트 파일을 출력합니다. 이렇게 군더더기가 없기 때문에 참가자는 다른 데 정신을 빼앗기지 않고 문제를 해결하는 데에만 집중할 수 있습니다.
  2. 명시적인 시간 제한과 메모리 제한이 있습니다. 프로그래밍 대회에서는 참가자가 제출한 프로그램이 평가용 입력을 처리하다가 제한 시간을 초과하거나 제한보다 많은 메모리를 사용하면 답의 정확성과 관련 없이 틀린 답으로 처리합니다. 그런데 많은 프로그래밍 대회 문제들은 계산 집중적1이기 때문에 적절한 알고리즘과 자료 구조를 사용하지 않으면 시간 제한 내에 동작하지 않습니다. 따라서 참가자는 제약 안에서 문제를 해결할 수 있는 알고리즘을 신중하게 설계해야 합니다. 때문에 프로그래밍 대회는 다양한 알고리즘 설계 기법과 자료 구조를 직접 사용해 볼 수 있는 계기가 됩니다. 잘 알려진 알고리즘들을 베껴 쓰기만 하면 해결할 수 있는 문제만 있는 것이 아니라 알고리즘에 사용된 원칙들을 이해하고 변형해야 풀 수 있는 문제들이 많이 출제되기 때문에 이런 주제들을 깊이 이해하는 데 큰 도움이 됩니다.
  3. 정답과 오답의 여부가 훨씬 명확히 가려집니다. 현업에서는 대개 코드의 정당성을 단위 테스트나 상호간 코드 리뷰로 검증하는데, 이런 방법으로는 잘 해봐야 한두 개의 입력을 가지고 프로그램을 시험해 보기 마련입니다. 그러나 대회에서는 훨씬 크고 다양한 입력에 대해 정답을 계산하는지 확인하므로 오류의 존재를 모르고 넘어갈 가능성이 훨씬 적습니다. 게다가 대부분의 프로그래밍 대회에서는 프로그램의 정답 여부를 대회가 끝난 뒤 바로 알려 주며, 일부 대회에서는 제출하자마자 알려주기도 합니다. 자신이 작성한 코드에 대해 이렇게 빠르고 객관적인 피드백을 받는 것은 예외 없고 정확한 프로그램을 짜는 아주 좋은 훈련이 됩니다.
  4. 제출한 프로그램의 실행 시간이나 메모리 사용량 관련 정보가 실시간으로 제공되기 때문에, 프로그램을 고쳐 가며 작은 변경이 프로그램의 효율성에 미치는 영향을 직접 체험해 볼 수 있습니다. 논리적 구조가 복잡한 프로그램의 수행 성능을 예측하는 데 익숙해지기 때문에 실무에서 퍼포먼스가 중요한 프로그램을 짜는 데도 큰 도움이 됩니다.
  5. 프로그래밍 대회에 제출하는 프로그램들은 대개 규모가 작아 각 문제를 풀 때마다 처음부터 다시 짜게 됩니다. 이런 특성은 평소 대형 프로젝트에서 간과했던 프로그램의 작은 부분에 집중할 수 있는 계기를 만들어 줍니다. 커다란 프로젝트에서 작업할 때는 코드의 구조를 변경하기도 어렵고, 큰 그림을 위해 프로그램의 우아함을 희생해야 할 때도 있습니다. 그러나 대회를 위한 작은 코드를 작성할 때는 이런 걱정 없이 간결하면서 우아한 프로그램을 짜는 데 시간을 투자할 수 있으므로, 좋은 코드를 작성하는 좋은 연습이 됩니다.
  6. 프로그래밍 대회에서는 여러 사람이 경쟁하는 환경에서 코드를 작성하게 됩 니다. 사람에 따라 경쟁은 실력을 늘리기 위한 좋은 동기가 되기도 합니다. 많은 프로그래밍 대회에서는 대회가 끝난 후 제출된 소스를 모두 공개한다는 점도 주목할 만합니다. 현업에서는 두 사람 이상이 같은 일을 하는 코드를 동시에 작성하는 일이 거의 없지만, 대회에서는 모든 사람이 같은 문제를 풀기 때문에 전세계의 고수 프로그래머들이 짠 코드를 직접 보고 자신이 짠 코드와 비교해 볼 수 있는 기회가 됩니다.

이런 특성들은 프로그래밍 작업에서 문제 해결을 수련하기 위해 필수적인 요소만을 남겨 놓고 나머지를 전부 제외한 것이나 마찬가지입니다. 덕분에 프로그래밍 대회는 문제 해결을 공부하기에 아주 적합한 환경이라고 할 수 있습니다.

한 번쯤 해 볼 만하다고 느껴지나요?

이상은 1장의 첫 부분입니다. 나머지는 책을 구입해서 봐주세요~

1.3 이 책을 읽는 방법

1.4 국내에서 참가할 수 있는 프로그래밍 대회

1.5 대회 준비를 위한 조언


  1. 프로그램의 수행 시간이 데이터베이스, 네트워크 접근 등이 아니라 CPU를 통한 계산에 대부분 소비된다는 말입 니다.