구현이란?

머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정

기본적으로는 어떤 문제를 풀든 간에 소스 코드를 작성하게 되고, 작성된 코드는 시간/메모리 제한 사항울 충족해야 한다. 그러므로 이 유형은 모든 유형의 문제를 포함하는 개념이기도 한다. 또한 문제를 잘 풀이하기 위해서는 프로그래밍 언어에 능숙하고 코드 작성 속도가 좋은 것이 유리하므로 피지컬을 요구한다고 볼 수 있다.

이 책에서는 구현 유형을 별도의 챕터로 분류하여 알고리즘을 설계하고 제시된 조건에 맞게 코드로 작성하기 위해 알아야 내용들을 다룬다.

구현 유형에는 완전 탐색, 시뮬레이션 유형이 존재한다.

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

구현 시 고려해야 할 제한 사항

시간 제한

시간 제한을 충족하기 위해서는 작성할 알고리즘의 시간 복잡도를 파악하고, 이 시간 복잡도가 1초 동안 얼마나 많은 연산을 할 수 있는지 알고 있어야 한다. 시간 복잡도마다 어느정도의 연산을 할 수 있는지는 아래 링크를 참고하자.

• 시간 복잡도별 연산량

코드를 완성하고 보면 알고리즘을 처리하기 위한 순서마다 여러개의 시간 복잡도가 발생할 수 있다. 예를 들어

1. 데이터 정렬 시간 복잡도 - O(logN)
2. 정렬된 데이터를 처리하기 위한 시간 복잡도 - O(N)
3. 2번의 결과를 후처리하기 위한 시간 복잡도 - O(NlogN)

크게 3가지로 나뉠 경우에 가장 큰 차수인 O(NlogN)을 작성한 알고리즘의 시간 복잡도로 정하면 된다.

메모리 제한

메모리 제한을 충족하기 위해서는 각 자료형들의 크기와 범위를 알고 있어야 한다. 특히 파이썬은 기본 타입들도 다 클래스로 구현되어 있기 때문에 다른 언어들에 비해 메모리 사용량이 더 많은 편이다. 예를 들면 java에서 int는 4byte지만 파이썬에서는 28byte다.
물론 대체적으로 여유있게 출제되는 편이므로 일반적인 상황에서는 초과될 일이 거의 없다. 하지만 간혹 입력값이 매우 클 경우에는 메모리 제한에 걸릴 가능성이 있다. 그래서 itertools나 자료 구조를 적절히 활용하여 불필요하게 메모리를 낭비하지 않는 코드를 작성하는 것이 좋다.