이 포스팅의 목표는 필자가 알고리즘을 공부하며 습득한 내용을 정리하는 데 있습니다. 따라서 틀린 내용이 있을 수 있습니다. 틀린 내용을 발견하신 경우 댓글로 지적해 주시면 감사하겠습니다.
1. 서론
구현Implementation은 엄밀히 말해 알고리즘은 아니다. 코딩 테스트에서의 구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정을 말한다. 이렇게만 말하면 '모든 코딩 테스트 문제가 구현 문제 아냐?'하는 의문을 제기할 수 있다. 맞다. 사실 우리가 '코딩 테스트'라고 말하는 모든 유형은 구현 문제다. 그러나 그중에서도 특히 풀이를 떠올리기는 쉽지만 이를 소스코드로 옮기기 까다로운 문제를 구현 유형의 문제라고 분류한다.
2. 까다로운 문제가 뭐야?
2-1. 구현 방법 자체가 떠오르지 않는 문제
백준이나 프로그래머스와 같은 코딩 테스트 문제 제공 사이트에서 문제를 풀다 보면, 어떻게 풀면 될지 감은 오는데 이걸 어떻게 소스코드로 표현해야 할지 모르겠을 때가 종종 있다. '내 방식대로 풀면 소스코드가 많이 길어질 것 같은데, 이렇게 푸는 게 맞나?'싶을 때도 있고, 단순히 프로그래밍 언어의 숙련도가 부족하거나 라이브러리 사용 경험이 부족해서 건드리지 못하는 경우도 있다.
2-2. 시간/공간 복잡도(Big-O)가 제한된 문제
또, '풀 수 있을 것 같은데?'하고 호기롭게 도전했다가 막히는 경우도 종종 있다. 이런 코딩 테스트 문제들은 문제의 난이도를 올리기 위해 각종 제약 조건을 거는데, 시간 제약과 공간 제약이 대표적이다. 때문에 내가 생각한 방식대로 풀고, 주어진 예제가 정답임에도 코드 제출을 하면 시간 초과나 메모리 초과라는 씁쓸한 결과가 나오곤 한다. (시간/공간 복잡도에 관한 포스트는 추후에...)
완전 탐색 문제와 시뮬레이션 문제가 위에 서술한 까다로운 속성들을 모두 가지고 있는 대표적인 구현 문제라고 할 수 있다. 완전 탐색은 모든 경우의 수를 전부 계산하는 방법이고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 그대로 수행하는 방법이다.
3. 극복을 위한 방법
3-1. 구현 방법이 떠오르지 않는 이유
어느 문제가 안 그렇겠냐마는, 그중에서도 특히 구현 유형의 문제는 사용하는 언어 자체의 숙련도가 문제 풀이 여부를 좌우한다고 해도 과언이 아니다. 예를 들어, 파이썬Python으로 문제 풀이를 할 때 각종 표준 라이브러리에 대한 지식이 없다면, N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑는 경우를 구해야 하는 순열Permutations문제를 만났을 때 당황할 수밖에 없다. 파이썬에서 제공하는 표준 라이브러리인 itertools 모듈을 사용하면 간단하게 끝날 일인데 말이다.
3-2. 시간과 공간을 정복하기 위해서는
우선, 나는 코딩 테스트에서 메모리 초과가 나는 경우는 드물다고 생각한다. 대부분의 경우 메모리 초과보다 시간 초과가 먼저 발생하기 때문이다. 게다가, 메모리 초과가 자주 날 수 있는 문제는 채점하는 서버에도 부하가 크기 때문에 취업을 위한 코딩 테스트에선 메모리 초과 걱정을 할 필요는 없다고 본다 (물론 이는 내가 C/C++이나 자바가 아닌 파이썬으로 코딩 테스트를 준비해서일 것이다). 따라서 나는 공간보다 시간 복잡도를 우선해서 생각하는 편이다.
코딩 테스트에는 풀이 시간이 제한되어 있다는 점을 직시하고, 코드를 작성하기 전에 시간 복잡도를 우선적으로 고려해야 이 제약을 극복할 수 있겠다. 문제에서 주어진 시간/메모리 제한을 확인하지 않고 문제부터 본 뒤에 '풀 수 있겠는데?'하고 덤볐다간 열심히 작성한 코드도 날리고, 시간도 날리는 불상사가 생기기 때문이다. 그렇다. 내 이야기다.
기타 시간 절약 방법
나는 파이썬을 이용하여 코딩 테스트를 준비하고 있으므로 파이썬을 기준으로 설명하겠다.
PyPy3 사용하기
백준과 같은 문제 풀이 사이트에서는 Python3 외에도 PyPy3를 지원하는 경우가 있다. PyPy3는 Python3의 문법을 그대로 지원하면서도 실행 속도는 더 빠르다. 따라서 Python3으로 통과하지 못했던 코드가 PyPy3에서는 통과되는 경우가 종종 있다. 혹시 기업 코딩 테스트를 응시할 때 PyPy3가 따로 존재한다면 이를 응시하는 것도 방법이겠다.
input()대신 sys.stdin.readline() 사용하기
파이썬에서 테스트 케이스를 입력받을 때 흔히 input()을 사용하는데, 파이썬 표준 라이브러리인 sys 모듈의 stdin을 사용하면 입력 속도가 빨라진다.
4. 결론
이래저래 장황하게 설명했지만 결국 구현 문제의 핵심은 숙련이라고 생각한다. 위에서 언급한 구현 문제의 특징은 어떤 알고리즘에서든 나타날 수 있는 것이기 때문에, 실제 구현 문제를 만났을 때 당황하지 않도록 관련된 많은 문제를 풀어 보아야겠다.
5. 참고
- 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020), p104-110.