[이코테] Chapter4-1 / 아이디어를 코드로 바꾸는 구현

피지컬로 승부하기

코딩 테스트에서 구현(Implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다. 하지만 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘을 배우기 전에 먼저 다루고자 한다.

우리는 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있을까? 그렇지 않다. 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어(파이썬)로 정확히 구현해냈을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

아이디어를 코드로

흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 실제 ACM-ICPC, Google Code Jam 등의 대회에 자주 참가하는 사람들이 구현 유형의 문제들을 보면 '알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는게 좋다'라고 설명하곤 한다. 흔히 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도(타자)가 빠른 사람을 보고 '피지컬이 좋다'라고 이야기하는데, 구현 유형의 문제는 그런 의미에서 '피지컬을 요구하는' 문제라고도 할 수 있다. 예를 들어 알고리즘 문제풀이를 전략 시뮬레이션 게임과 비교하면 우리가 스타그래프트와 같은 게임을 할 때, 게임에서 이길 전략을 완벽히 짯다고 해보자. 하지만 마우스를 빠르게 움직이지 못한다면 게임에서 패배할게 뻔하다.

그렇다면 어떤문제가 구현하기 어려운 문제일까? 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는)문제 등이 까다로운 구현 유형의 문제라고 할 수 있따. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다. 물론 경험이 많은 프로그래머에게는 쉬울 수 있으나 초보자 입장에서는 프로그래밍 언어의 문법부터가 익숙하지 않기에 더 어렵게 느껴질 수밖에 없다.

그렇기에 실제로 코딩 테스테어서 구현 문제를 만나면 당황할 수 있다. 어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있기 때문이다. 또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다. 예를 들어 파이썬으로 코딩 테스트에 응시했는데, N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한줄로 세우는 모든 경우(순열)를 구해야 하는 문제를 만나면 어떻게 할까? 무작정 기능을 전부 작성할 수도 있다. 하지만 파이썬의 itertools와 같은 표준 라이브러리로 쉽게 짜는 방법도 있다. 이는 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법이다. 

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

코딩 테스트에서는 어떤 환경에서 문제를 풀어야 하는지를 알고 그 환경에 맞게 프로그래밍 언어를 적절히 사용하여 구현하는 일이 중요하므로, 먼저 코딩 테스트 채점 시스템의 제약에 대해 설명한 후 문제를 다루겠다.

 

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

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

전통적으로 프로그래밍 언어에서 정수형(Integer) 을 표현할 때는 int 자료형을 주로 사용하며 이 자료형의 크기는 4바이트이다. 특히 C/C++, 자바 등을 이용해 코딩할 떄는 int자료형을 필수적으로 이용한다. 기본 자료형의 표현 범위는 -2,147,483,648 ~ 2,147,438,647인데 이 말은 int자료형으로 처리하면 2,147,438,647보다 큰 수를 처리할 수 없다는 의미이다. 

그렇다면 큰 수는 어떻게 처리해야 할까? 이럴 떄는 크기가 8바이트인 long long과 같은 자료형을 사용하는데, 이 또한 9,223,372,036,854,775,807보다 큰 수를 처리할 수 없다. 따라서 훨씬 큰 수를 담을 변수를 만들려면 흔히 BigInteger 클래스를 구현하거나 이용해야 한다.

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

C/C++와 자바에서 정수형 종류에 따른 범위

반면에 파이썬(3.7기준)에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. 따라서 파이썬을 이용하는 독자라면 자료형의 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 괜찮다. 실제로 기업 코딩 테스트뿐만 아니라 프로그래밍 대회에 참가할 때에도 파이썬을 선택했다면 정수형 변수의 연산 때문에 머리 아프게 고민해야 할 일은 거의 없을 것이다. 다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자.

 

파이썬에서 리스트 크기

이제 리스트의 크기 제약에 대해서 알아보자. 파이썬에서 여러 개의 변수를 사용할 때는 리스트를 이용한다. 파이썬에서 리스트를 이용할 때에 고려해야 할 사항이 있다. 바로 코딩 테스트의 메모리 제한이다. 대체로 코딩 테스트에서는 128~512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다. 이럴 때는 메모리 제한을 염두에 두고 코딩해야 한다. 앞서 다루었던 int자료형의 데이터 개수에 따른 메모리 사용량을 확인해 보자. 파이썬에서는 정수 데이터를 사용할 때 int와 같은 별도의 자료형을 명시해줄 필요가 없지만, 시스템 내부적으로는 다음 표에서 보여주는 것과 유사한 크기만큼 메모리를 차지한다.

int 자료형 데이터의 개수에 따른 메모리 사용량

파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자. 리스트를 여러 개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억하자. 

하지만, 이런 문제 또한 드물다. 메모리 제한 때문이 아니라 수천만 개 이상의 데이터를 입력해야 하면 입출력에 너무 많은 시간이 소요되며 채점 환경에서도 다양한 문제가 발생할 수 있기 때문이다. 게다가 입출력 속도는 프로그래밍 언어마다 조금씩 다르며, 빠른 입출력을 위한 테크닉들이 필요에 따라 사용되기도 한다. 모든 프로그래밍 언어에 대한 입출력 속도까지 고려하여 시간 제한을 설정하는 것은 출제자 입장에서도 매우 번거로운 작업이다.

따라서 일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하면 된다. 애초에 대회 문제가 아니라면 복잡한 최적화를 요구하지 않는 것이 일반적이므로 코딩 테스트에서는 이 정도만 기억해도 문제를 푸는 데에 어려움은 없다. 자세한 설명을 위해서는 컴퓨터 메모리 구조에 대해 언급해야 하는데, 이는 이 책의 범위를 넘어서기 때문에 간략히만 언급하였다. 

 

채점 환경

그렇다면 실제 온라인 저지 서비스에서 사용되는 채점 환경의 시스템 제한은 어떨까? 문제에서 요구하는 메모리 제한과 실행 시간 제한은 코딩 테스트를 출제하는 기관마다, 문제마다 조금씩 다르다. 출제자가 매우 빠르게 동작하는 프로그램을 원한다면 시간 제한은 더욱 짧을 것이다. 보통 여러분이 접하는 코딩 테스트 환경에서는 다음과 같은 채점 시스템의 시간 제한 및 메모리 제한 정보가 적혀 있다.

• 시간 제한 : 1초
• 메모리 제한 : 128MB

파이썬은 C/C++ 에 비해 동작 속도가 느리다. 그래서 파이썬을 선택했을 때는 C/C++에 비해 2배의 수행 시간 제한을 적용하기도 한다. 2020년을 기준으로 파이썬 3.7로 코드를 작성할 때, 자신의 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다. 사실 수행 시간을 정확히 측정하기 위해서는 채점 시스템의 컴퓨터 사양과 사용하는 알고리즘을 면밀히 분석해야 하는데, 일반적인 기업 코딩테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점만 기억하자.

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

따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

 

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 문제의 길이를 보고 지레 겁먹는데, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

구현 유형의 문제는 C/C++나 자바로 문제를 풀 때 더 어렵게 다가온다. 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데, C/C++나 자바에서는 문자열 처리가 파이썬에 비하여 까다롭고, 큰 정수를 처리하는 라이브러리를 별도로 사용해야 하기 때문이다. 반면 파이썬은 기본 문법만 알아도 상대적으로 구현 유형의 문제를 쉽게 해결할 수 있다.

구현 측면에서 C/C++와 파이썬은 다음과 같이 비교할 수 있다 .어느정도 이견이 있을 수 있지만 프로그래머 대부분이 공감할 것이다. 

파이썬과 C/C++ 비교

자바로 코딩 테스트를 치르는 응시생이 적은 편이라 이 책에서는 파이썬과 C/C++ 위주로 설명한다.

실무에서 파이썬으로 프로그램을 개발할 때는 GPU를 연동하며, 반복적인 행렬 계산을 요구하는 복잡한 수학 문제를 풀 때는 C언어로 작성된 파이썬 코어 소포트웨어가 동작한다. 그렇기 때문에 파이썬을 쓴다고 해서 항상 프로그램의 동작 속도가 느린 것은 아니다. 하지만 알고리즘 코딩테스트 환경에서는 GPU 연산을 쓰는 경우가 없기 때문에 그러한 사항을 고려하지 않고 있다. 

또한 자동 채점 방식을 이용하는 코딩 테스트 환경에서는 점점 Pypy3를 지원하는 곳이 늘고 있다.
Pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠르다. 이 말은 코딩 테스트에서 Pypy3를 선택하면 파이썬3와 동일한 코드를 제출해서 실행 시간을 줄일 수 있다는 의미이다. 삼성전자 공채에서는 코딩 테스트 채점에 Pypy3를 이용하는데, 지원자가 파이썬3로 제출하면 기본으로 Pypy3를 이용해 채점한다. 특히 반복문이 많을 수록 Pypy3와 파이썬3의 속도가 차이 나는데, Pypy3도 지원하는지 확인하고 만약 Pypy3도 지원한다면 이를 이용하도록 하자. 

반면에 C/C++를 이용한다고 해서 구현이 무조건 어려운 것은 아니다. C/C++를 주 언어로 사용하는 숙련도 높은 랭커들은 자신만의 코드 노트가 있어서 이를 잘 활용한다. ACM-ICPC와 같은 국제 대회에서는 구현이 복잡한 코드의 경우 A4용지나 PDF파일 형태로 참고용 팀 노트를 준비해 이를 볼 수 있도록 하는 경우도 있다. 이럴 때에 자신만의 라이브러리가 이미 구축되어 있다면 C/C++로도 충분히 난이도가 낮은 문제일 수 있다. 하지만 일반적으로 C/C++는 고려해야 할 사항이 많아 초보자에게는 쉽지 않다. 

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다. 예를 들어 카카오 공채 때 API 개발 문제가 출제된 적이 있는데, 이때 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 했다. 이는 알고리즘 문제와 별개로 웹 서버나 데이터 분석에 대한 기초 지식도 필요하다. 이런 기능을 구현해야 할 때, C++나 자바에 비해 파이썬은 매우 간결하고 직관적인 코드의 라이브러리를 사용할 수 있어 더 유리하다. 파이썬을 사용한다면 코딩 테스트에서 API 개발 문제를 보더라도 상대적으로 무난하게 대처할 수 있을 것이다.

이제 구현 알고리즘의 대표적인 예시인 '상하좌우' 문제와 '시각' 문제를 풀어보려 한다. 2문제를 가볍게 읽은 다음 2절의 실전 문제를 풀어보자.

 

[예제 4-1] 상하좌우

여행가 A는 N * N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 * 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다. 

상하좌우

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 
각 문자의 의미는 다음과 같다.

• L : 왼쪽으로 한 칸 이동
• R : 오른쪽으로 한 칸 이동
• U : 위로 한 칸 이동
• D : 아래로 한 칸 이동

이때 여행가 A가 N * N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다. 다음은 N = 5인 지도와 계획서이다. 

상하좌우 계획서와 지도

이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로, 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 다시 말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

[입력 조건]

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다 (1 <= N <= 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 <= 이동 횟수 <= 100)

[출력 조건]

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

[입력 예시]

5
R R R U D D

[출력 예시]

3 4

문제 해설

이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 예를 들어 이동 횟수가 N번인 경우 시간 복잡도는 O(N)이다. 따라서 이 문제의 시간 복잡도는 매우 넉넉한 편이다. 
이러한 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(simulation) 유형으로 분류되며 구현이 중요한 대표적인 문제 유형이다. 다만, 알고리즘 교재나 문제 풀이 사이트에 따라서 다르게 일컬을 수 있으니 코딩 테스트에서의 시뮬레이션 유형, 구현, 유형, 완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억하자.

코딩테스트나 알고리즘 대회에서 가장 난이도가 낮은 1~2번 문제는 대부분 그리디 알고리즘이나 구현 문제이다. 이 두 유형이 논리적 사고력을 확인할 수 있는 가장 기본 난이도의 문제로 적합하기 때문이다. 난이도가 낮은 만큼 합격을 좌우하는 중요한 문제이기도 하다.

[4-1.py 답안 예시]

# N을 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

 

[예제 4-2] 시각

정수 N이 입력되면 00시 00초 부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 파함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 떄 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다. 

• 00시 00분 03초
• 00시 13분 30초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

[입력 조건]

• 첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)

[출력 조건]

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

[입력 예시]

5

[출력 예시]

11475

문제 해설

이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제다. 왜냐하면 하루는 86,400초로, 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지밖에 존재하지 않기 때문이다. 다시 말해 경우의 수가 100,000개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문제를 해결할 수 있다.

따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인하면 될 것이다. 전체 시, 분, 초에 대한 경우의 수는 24 * 60 * 60 이며 3중 반복문을 이용해 계산할 수 있다.

이러한 유형은 완전 탐색(Brute Forcing)유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색) 해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.

다음 소스코드에서는 매 시각을 문자열로 바꾼 다음 문자열에 '3'이 포함됐는지 검사한다. 다시 말해 00시 00분 00초부터 23시 59분 59초까지 1초씩 늘리며 시, 분, 초를 문자열 자료형으로 변환하여 합친다. 예를 들어 03시 20분 35초일 때를 확인한다면, 이를 '032035'로 만들어서 '3이 '032035'에 포함되어 있는지를 체크하는 방식을 이용한다.

[4-2.py 답안 예시]

# N을 입력받기
n = int(input())

count = 0
for i in range(n + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count = count + 1

print(count)

이제 실전 문제를 풀어보자. 구현 문제 유형은 앞장에서 공부했던 그리디 알고리즘 문제 유형과 비교했을 때 큰 차이가 느껴지지 않을 수 있다. 애초에 구현 유형과 그리디 유형은 별개가 아니라 하나의 문제에 구현 유형과 그리디 유형이 함께 포함된 형태로 출제되는 경우가 많기 때문이다. 3장에서 언급했듯이 하나의 문제에는 여러 개의 문제 유형이 포함되는 경우가 많다.