아이디어를 코드로 바꾸는 구현
구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 당연히 프로그래밍이 이런 것 아닌가? 생각할 수 있다. 하지만 코딩 테스트에서 말하는 구현 유형의 문제란 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다.
구현 문제 유형은 다음과 같다.
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
그리고 풀이 유형은 두 가지로 묶을 수 있다.
- 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 방법
- 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법
구현 시 고려해야 할 메모리 제약 사항
파이썬에서 리스트 크기
코딩 테스트에서 메모리 제한이 있을 경우, 대체로 128 ~ 512MB로 제한하는데 이럴 때는 메모리 제한을 염두에 두고 코딩해야 한다. 파이썬에서는 정수 데이터를 사용할 때 int와 같은 별도의 자료형을 명시해줄 필요가 없지만, 시스템 내부적으로는 다음 표에서 보여주는 것과 유사한 크기만큼 메모리를 차지한다.
int 자료형 데이터의 개수에 따른 메모리 사용량 |데이터의 개수(리스트이 길이)|메모리 사용량| |——|—| |1,000|약 4KB| |1,000,000|약 4MB| |10,000,000|약 40MB|
하지만, 이런 제약이 있는 문제는 드물다.
채점 환경
코딩 테스트 환경에서는 다음과 같은 채점 시스템의 시간 제한 및 메모리 제한 정보가 적혀 있다.
- 시간 제한: 1초
- 메모리 제한: 128MB
파이썬을 선택했다면 자신의 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다. 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다. 실제로 N = 1,000,000일 때 Nlog2N은 약 20,000,000이기 때문이다.
구현 문제에 접근하는 방법
보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 문제의 길이를 보고 지레 겁먹는데, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.
특히, 파이썬은 구현 난이도가 낮은 언어로 문법만 익숙해지면 쉽게 문제를 풀 수 있다.
ref
이것이 취업을 위한 코딩 테스트다 with 파이썬
나동빈 유튜브 강의