구현

아이디어를 코드로 바꾸는 구현

 코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

 그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다. 하지만 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제 되기에 다른 알고리즘을 배우기 전에 먼저 다룬다.

 알고리즘 문제를 해결할 떄 문제를 읽고 풀이 방법을 고민한다. 이후 구현을 위해 프로그래밍 언어의 문법을 정확히 알고 있어야하고 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야한다.

 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다. 구현 유형의 문제들을 보면 알고리즘은 설계했는데 구현이 먼저 풀 수 있는문제가 없을 때 푸는 것이 좋다. 보통 프로그래밍 언어의 문법에 능숙하고  코드 작성 속도가 빠른 사람이 피지컬이 좋다라고 표현된다. 구현 유형의 문제는 피지컬을 요구하는 문제이다.

 구현 유형의 문제는 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱을 해야하는) 문제 등이 까다로운 구현 유형의 문제라고 할 수 있다. 대체로 사소한 조건 설정이 많은  문제일수록 코드로 구현하기가 까다롭다. 

 코딩 테스트에서 구현이 어렵다면 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 떄 불리하다. 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있다.

 대표적으로 두 가지 유형이 존재하는데 완전탐색, 시뮬레이션이 있다. 완전 탐색은 모든 경우의 수를 주저없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 의미한다, 둘 다 구현이 핵심이 되는 경우가 많기 때문에 이 두 유형을 모두 묶어서 구현 문제들이 나온다.

 

대표적인 문제들: 상하좌우, 왕실의 나이트, 게임 개발