구현(Implementation): 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
구현 문제는 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.
<aside> 💡 Problem → Thinking → Solution
</aside>
흔히 구현 유형의 문제는 ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제’를 의미한다.
구현은 특히 문법이나 코드 작성 속도가 중요하다. 예를 들어 순열을 구하는 문제가 있을 때 파이썬 문법을 잘 아는 사람은 intertools와 같은 표준 라이브러리로 쉽게 짤 수 있을 것이다.
이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 ‘구현’ 유형으로 묶어서 다루고 있다.
전통적으로 프로그래밍 언어에서 정수형을 표현할 때는 int 자료형을 주로 사용하며 이 자료형의 크기는 4바이트다. 특히 C/C++, 자바 등을 이용해 코딩할 때는 int 자료형을 필수적으로 이용한다.
…
리스트 크기 제약에 대해 알아보자. 파이썬에서 여러 개의 변수를 사용할 때는 리스트를 이용한다. 파이썬에서 리스트를 이용할 때에 고려해야 할 사항이 있다. 바로 코딩 테스트의 메모리 제한이다.
대체로 코딩 테스트에서는 128~512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다. 이럴 때는 메모리 제한을 염두에 두고 코딩해야 한다. 파이썬은 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자. 리스트를 여러 개 선언하고, 그중에서 크기가 1000만개 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없는 경우가 있다는 점을 기억하자.
보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 문제의 길이를 보고 지레 겁먹는데, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.