Python 57 - 구현 ( 알고리즘 )

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

어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 

우리는 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다.

고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있을까? 그렇지 않다.

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

흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 

예를 들어 알고리즘 문제 풀이 전략 시뮬레이션 게임과 비교하면 우리가 스타크래프트와 같은 게임을 할 때 , 게임에서 이길 전략을 완벽하게 짰다고 해보자. 하지만 마우스를 빠르게 움직이지 못한다면 게임에서 패배할 게 뻔하다.

 

그렇다면 어떤 문제가 구현하기 어려운 문제일까?

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

 

이책에서는 완전탐색, 시뮬레이션 유형을 모두 '구현'유형으로 묶어서 다루고 있다. 

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

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

둘 다 구현이 핵심이 되는 경우가 많기 때문이다.

 

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

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

정수형의 종류	자료형의 크기	자료형의 범위
int	4바이트	-2,147,483,648 ~ 2,147,438,647
long long	8바이트	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
BigInteger(클래스)	가변적	제한 없음

반면에 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다.

따라서 파이썬을 이용하는 독자라면 자료형의 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 된다.

다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자.

 

파이썬에서 리스트 크기

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

데이터의 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

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

 

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

 

채점 환경

문제에서 요구하는 메모리 제한과 실행 시간 제한은 코딩 테스트를 출제하는 기관마다, 문제마다 조금씩 다르다.

출제자가 매우 빠르게  동작하는 프로그램을 원한다면 시간 제한은 더욱 짧을 것이다. 보통 코딩테스트 횐경에서는 다음과 같은 채점 시스템의 시간 제한 및 메모리 제한 정보가 적혀있다.

시간 제한 : 1초

메모리 제한 : 128MB

파이썬은 C/C++에 비해 동작 속도가 느리다. 그래서 파이썬을 선택했을 때는 C/C++에 비해 2배의 수행 시간 제한을 적용하기도 한다. 일반적인 기업의 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점만 기억하자. 아골리즘 문제를 풀 때는 시간제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측 할 수 있어야 한다.

 

구현 문제에 접근하는 방법

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

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

	구현 난이도	프로그램 실행시간
파이썬	쉬운 편	긴 편
PyPy	쉬운 편	다소 짧은 편
C/C++	어려운 편	짧은 편

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

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding