구현이란?
구현이란 머릿속에 있는 알고리즘을 실제 소스 코드로 바꾸는 과정이다. 어떤 문제를 풀더라도 소스 코드를 작성하는 과정은 필수이므로 '구현 문제' 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.
알고리즘 공부를 통해 문제에 대한 해법을 머릿속으로 떠올릴 수 있었다면, 이제 프로그래밍 언어의 기능들을 십분 활용하여 소스 코드를 작성해야만 한다.
코딩 테스트에서, 알고리즘은 대체로 간단하지만 막상 소스 코드로 쓰려면 어려운 문제들을 구현 유형의 문제라고 부른다.
구현 시 고려해야 할 제약 사항들
구현 시 고려해야 할 첫 번째 제약 사항은 바로 메모리이다. C/C++ 등에서는 변수를 선언할 때 자료형을 지정해야 하는데, 지정된 자료형에 따라서 저장할 수 있는 값의 크기가 달라진다. 이 점을 유의하여 변수를 선언하여야 한다. 또한, Python의 list 자료형 등 그 크기가 무한히 커질 수 있는 형태인 경우 메모리 용량 제한에 걸리게 될 수 있다는 점 또한 유념해야 한다.
두 번째 제약 사항은 바로 동작 속도인데, Python을 사용하는 경우 특히 더 그렇다. Python은 Interpreter 언어이기 때문에 Compiler 언어인 C/C++보다 느리다. 그래서 일부 경우에는 Python을 선택했을 경우에 2배의 제한 시간을 부여하기도 한다.
Python은 약 초당 2000만 번의 연산을 수행한다고 한다.
따라서 시간 제한이 1초이고, 데이터의 개수가 1,000,000개라면 일반적으로 시간 복잡도 O(n log n) 이하의 알고리즘을 사용하여 문제를 풀어야 한다. n = 1,000,000일 때 n log n ≃ 6,000,000이기 때문이다.