이 포스트는 책 '이것이 코딩 테스트다'를 토대로 작성하였습니다.

구현

• 코딩 테스트에서 구현(Implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.
• 구현 유형의 문제는 '풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.

어떤 문제가 구현하기 어려운 문제일까?

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 특정 소수점 자리까지 출력해야 하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제

구현이 핵심이 되는 알고리즘 종류

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

---

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

메모리 제한

• 파이썬에서 리스트를 사용할 때 메모리 제한을 신경써야 한다!
• int형 리스트의 길이가 100만일 때 메모리 사용량은 약 4MB라는 것을 기억하자.
• 리스트를 여러 개 선언하고, 그중에서 크기가 1000만 이상인 리스트가 있으면 메모리 제한 때문에 테스트에 통과하지 못할 수 있다.

시간 제한

• 일반적인 기업 코딩 테스트 환경에서는 파이썬을 제출한 코드가 1초에 2천만 번의 연산(2 * 10^7)을 수행한다고 가정하면 무리없이 문제를 풀 수 있다.
• 만약 제한 시간이 1초이고 데이터의 개수가 100만개라면 O(NlogN)의 시간 복잡도를 가진 알고리즘으로 문제를 풀어야 한다.