2️⃣ 구현(Implementation)

[heydoy]

아이디어를 코드로 바꾸는 구현

코딩테스트에서 구현(implementation)은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

알고리즘 문제 해결 시, 문제를 읽고 > 풀이방법을 고민하고 > 프로그래밍 언어로 정확히 구현해야 정답처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고있어야 하며 문제 요구사항에 벗어나지 않는 답안 코드를 실수없이 작성해야한다.

문제해결 분야에서 구현 유형의 문제는 ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미. 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성속도(타자)가 빠른 사람을 ‘피지컬이 좋다'고 이야기하는데 구현유형의 문제는 ‘피지컬을 요구하는 문제'라고 할 수 있다.

구현하기 어려운 문제는 예를 들어, 알고리즘은 간단한데 코드가 지나치리만큼 길어지는 문제, 특정 소수점까지 출력해야하는 문제, 문자열이 입력으로 주어질 때 문자 단위로 끊어서 리스트에 넣는(파싱하는) 문제 등이 까다로운 구현 유형 문제라고 할 수 있다.

예를 들어 파이썬 코딩테스트에서 N개의 원소가 있는 리스트에서 R개의 원소를 뽑아 한줄로 세우는 모든 경우(=순열)를 구해야하는 문제를 만나면, 무작정 기능을 전부 작성하기보다는 파이썬의 itertools와 같은 표준 라이브러리로 쉽게 짜는 방법이 있다.

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 구현유형으로 묶어서 다루고 있다. 완전탐색은 모든 경우의 수를 주저없이 다 계산하는 해결방법이고 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 의미한다.

[heydoy]

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

C/C++에서 변수의 표현 범위

정수형(integer)을 표현할때는 int 자료형. 이 자료형의 크기는 4바이트. Int 자료형이 다룰 수 있는 범위보다 큰 수는 long long, 이보다 더 큰수의 경우 BigInteger 클래스를 구현하거나 이용.

자바의 경우 BigInteger를 표준 라이브러리로 지원하지만 C++는 표준 라이브러리에 포함되어 있지 않다. 코딩테스트 중 이를 직접 작성하기는 어렵기 때문에 보통은 검색해서 외부 라이브러리 형태 그대로 가져와 사용한다. 대체로 long long 에서 다룰 수 있는 수보다 더 큰 정수를 처리하는 문제는 잘 처리되지 않는다.

반면 파이썬(3.7 + 기준)에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. 따라서 파이썬을 이용할 경우 자료형의 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 괜찮다. 다만 파이썬에서 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라 연산결과가 원하는 값이 나오지 않을 수 있다.

파이썬에서 리스트 크기

파이썬에서 리스트 이용 시 코딩테스트의 메모리 제한을 고려해야한다. 보통 코딩테스트에서 128MB ~ 512MB로 메모리를 제한하는데 알고리즘 문제중에는 수백만개 이상의 데이터를 처리해야하는 문제가 출제되곤 한다. 예를 들어 파이썬에서는 정수 데이터를 사용할 때 별도 자료형을 명시해줄 필요가 없지만 시스템 내부적으로는 아래 표와 유사한 크기만큼 메모리를 차지한다.

보통은 이런 문제가 드물기 때문에 일반적인 코딩테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야한다는 점 정도만 기억하면 된다.

채점 환경

실제 온라인 저지 서비스에서 채점 환경 시스템 제한은 기관마다 문제마다 조금씩 다르며 출제자가 빠르게 동작하는 프로그램을 원한다면 시간제한은 더욱 짧을 것이다. 보통 코딩 테스트환경에서는 시간 제한 및 메모리 제한 정보가 적혀있다.

• 시간제한 : 1초 (1000ms)
• 메모리제한: 128MB

파이썬은 C/C++에 비해서 속도가 느리다. 그래서 파이썬을 선택할 경우 C/C++에 비해 2배의 수행시간 제한을 적용하기도 한다. 2020년 파이썬 3.7 기준으로 코드가 1초에 2,000만번의 연산을 수행한다고 가정하고 문제를 풀면 실행시간 제한에 안정적이다.

시간제한이 1초고 데이터 갯수가 100만개인 문제가 있다면 일반적으로 시간 복잡도는 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야한다. 실제로 N = 1,000,000일때 Nlog2N은 약 20,000,000 이기 때문이다.

구현 문제에 접근하는 방법

구현 측면에서 초보자 기준 언어별 난이도 체감은 아래와 같다.

자동채점 방식을 이용하는 코딩테스트 환경에서는 점점 Pypy3를 지원하는 곳이 늘고 있다. Pypy3는 파이썬3의 문법을 그대로 지원하며 대부분 파이썬 3보다 실행속도가 더 빠르다. 특히 반복문이 많을 수록 속도가 차이 나는데 Pypy3의 실행속도는 때로 C/C++와 견줄 만큼 빠르다. 대략 1초에 2,000만번에서 1억번 정도의 연산을 처리할 수 있다고 기억하자. 따라서 코딩테스트 환경에서 Pypy3를 지원하는지 확인하고 이를 이용하도록 하자.

API 개발 문제도 구현 유형과 맞닿아 있다. 예를 들어 카카오 공채 때 API 개발 문제가 출제된 적이 있는데 이때 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 했다. 이런 기능을 구현해야할 때 파이썬은 매우 간결하고 직관적인 코드의 라이브러리를 사용할 수 있어 더 유리하다.