구현

코딩 테스트 및 온라인 저지 사이트에서 자주 접하게 되는 문제 유형들 중 하나가 구현 문제입니다.

구현 문제란, 머릿속에 있는 알고리즘을 코드로 옮기는 과정을 의미합니다. 엄밀히 말하자면 모든 문제가 구현 문제인 셈입니다.

구체적으로, 구현 문제는 프로그래밍 언어의 기본 문법구조와 자료구조를 이용하여, 특정 문제를 해결하는 문제입니다.

 

몇 개의 예시를 들면 다음과 같습니다:

브론즈 5 - 별 찍기 - 1: www.acmicpc.net/problem/2438

골드 5 - 빗물: www.acmicpc.net/problem/14719

골드 4 - 아기 상어: www.acmicpc.net/problem/16236 (삼성전자 기출 문제)

골드 2 - 2048 (Easy): www.acmicpc.net/problem/12100 (삼성전자 기출 문제)

 

이런 문제들의 공통점이라면, 문제의 요구 조건, 메모리 및 시간 제한 등을 정확히 파악하여야 하며, 예외 처리까지 고려해야 할 점들이 많다는 점입니다.

이것을 정확히 생각해 내는 것이 중요하며, 이를 코드로 옮겨서 정확히 구현하는 것도 마찬가지로 중요합니다. 따라서 많은 연습이 필요한 유형이라고 할 수 있습니다.

어려운 문제라면 아주 큰 수를 다루는 문제 (Python을 이용하는 경우 제외), 조건과 예외 처리가 많아 코드가 길어지는 문제, 특정 소수점 자리까지 출력하는 문제, 문자열을 입력받은 후 한 문자 단위로 끊는 (parsing을 해야 하는) 문제 등이 있겠습니다.

 

많은 경험과 연습이 필요한 이유가 이것인데, 접해보지 않은 유형의 문제를 만나면 당황할 수밖에 없기 때문입니다.

또, 연습을 통해 사용하는 언어의 라이브러리 등에 익숙해져 있어야 합니다. C++을 예로 들면, <string> STL은 사실 char을 여러 개 이어 붙인 array와 같은 형태입니다. string hello = "world" 인 변수 hello가 있다면, Array와 마찬가지로, hello[2]는 "r"을 가리킵니다. 이러한 사실 자체가 생소하다면 문자열 파싱이 나오는 문제에서 많은 시간이 소요될 수밖에 없을 것입니다.

 

구현은 크게 두 유형으로 나눌 수 있습니다.

"완전 탐색" 은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미합니다.

"시뮬레이션" 은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미합니다.

 

구현 문제를 접하기에 앞서, 몇 가지 확인하고 가야 할 점이 있습니다.

1. 변수의 표현 범위

C/C++, Java 등을 이용하는 경우 각 변수의 표현 범위에 대해 아주 잘 이해하고 있어야 합니다.

가장 흔하게 쓰는 int 변수의 경우, -2,147, 483,648 ~ 2,147, 483,647까지 나타낼 수 있습니다. 이보다 더 큰 수를 표현하고 싶다면 long long 와 같은 다른 변수를 사용해야 합니다.

long long보다 더 큰 숫자를 담을 변수를 만들려면 BigInteger 클라스를 구현하거나 이용해야 합니다. 이는 Java에서는 STL로 지원하지만, C++는 STL에 포함되어 있지 않습니다. 따라서 인터넷에서 검색하여 외부 라이브러리의 형태로 이용해야 합니다. 다행히 코딩 테스트에서는 이런 문제는 잘 출제되지 않지만, BOJ 등에서 문제를 풀 때는 이러한 사실을 알아둬야 하는 경우가 있습니다.

Python은 작성자가 직접 자료형을 지정할 필요가 없으며, 변수가 기본적으로 매우 큰 수를 담을 수 있습니다.

 

2. 메모리 제한

이 문제는 특히 Python에서 신경 써야 하는 문제입니다.

Python에서는 list를 이용하여 여러 개의 변수를 사용하는데, 수백만 개 이상의 데이터를 처리해야 하는 경우 문제가 될 수 있습니다. 특히 크기가 1000만 이상인 list가 있다면 메모리 제한이 걸리지는 않는지 반드시 확인해야 합니다.

다행히 이런 문제 역시 드문 편입니다. 

 

코딩 테스트는 보통 온라인으로 문제가 채점되며, 시간 제한과 메모리 제한이 걸려 있습니다.

보통 시간 제한: 1초, 메모리 제한: 128MB 등으로 명시되어 있습니다. 알고리즘을 작성할 때 시간 복잡도를 고려해야 하는데, 이는 간과하기 쉬운 부분입니다. 시간 제한을 확인하지 않고 문제를 풀었는데 잘못된 방법으로 접근하여 시간 제한에 걸린다면 아주 치명적인 실수가 될 것입니다. 시간 제한과 데이터의 갯수를 확인한 후 어느 정도의 시간 복잡도를 가지는 알고리즘으로 작성해야 풀 수 있을지 예측해보도록 합니다.

 

구현 문제는 언어마다 난이도의 차이가 존재합니다. Python은 구현 난이도는 쉽지만 프로그램 실행 시간은 긴 편이며, 반대로 제가 주로 이용하고 있는 C++는 프로그램 수행 시간은 짧지만 구현 난이도가 어려운 편입니다. 코딩 테스트에서 API 개발 문제가 나오는 경우가 있는데, 이 때 특히 구현 난이도와 직면하게 됩니다.

 

*본 글은 "나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬" (한빛미디어, 2020)" 를 참고하여 작성하였습니다.