구현
아이디어를 코드로 바꾸는 구현
코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다.
그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다. 하지만 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다.
우리는 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있을까? 그렇지 않다. 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현해냈을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.
흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 실제 ACM-IPC, Google Code Jam 등의 대회에 자주 참가하는 사람들이 이 구현 유형의 문제들을 보면 '알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는 게 좋다'라고 설명하곤 한다. 흔히 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도(타자)가 빠른 사람을 '피지컬이 좋다'라고 이야기하는데, 구현 유형의 문제는 그런 의미에서 '피지컬을 요구하는' 문제라고도 할 수 있다. 예를 들어 알고리즘 문제 풀이를 전략 시뮬레이션 게임과 비교하면 우리가 스타크래프트와 같은 게임을 할 때, 게임에서 이길 전략을 완벽히 짰다고 해보자.
하지만 마우스를 빠르게 움직이지 못한다면 게임에서 패배할 게 뻔하다.
그렇다면 어떤 문제가 구현하기 어려운 문제일까? 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제 등이 까다롱누 구현 유형의 문제라고 할 수 있다. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다. 물론 경험이 많은 프로그래머에게는 쉬울 수 있으나 초보자 입장에서는 프로그래밍 언어의 문법부터가 익숙하지 않기에 더 어렵게 느껴질 수밖에 없다.
그렇기에 실제로 코딩 테스트에서 구현 문제를 만나면 당황할 수 있다. 어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있기 때문이다. 또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다. 예를 들어 파이썬으로 코딩 테스트에 응시했는데, N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야 하는 문제를 만나면 어떻게 할까? 무작정 기능을 전부 작성할 수도 있다. 하지만 파이썬의 itertools와 같은 표준 라이브러리로 쉽게 짜는 방법도 있다. 이는 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법이다. 이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현'유형으로 묶어서 다루고 있다. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 둘 다 구현이 핵심이 되는 경우가 많기 때문에 이 두 유형을 모두 묶어서 구현 장에서 다루고 있다.
코딩 테스트에서는 어떤 환경에서 문제를 풀어야 하는지를 알고 그 환경에 맞게 프로그래밍 언어를 적절히 사용하여 구현하는 일이 중요하므로, 먼저 테스트 채점 시스템의 제약에 대해 설명한 후 문제를 다루겠다.