PART02 - CHAPTER 04. 구현

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

피지컬로 승부하기

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

- 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.

- 이 구현 유형의 문제들을 보면 '알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는게 좋다'라고 설명한다.

- 어떤 문제가 구현하기 어려운 문제일까?

    ㆍ알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

    ㆍ특정 소수점 자리까지 출력해야하는 문제

    ㆍ문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제

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

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

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

 

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

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

- 전통적으로 프로그래밍 언어에서 정수(Integer)을 표현할 때는 int 자료형을 주로 사용하며 이 자료형의 크기는 4바이트이다.

- 특히 C/C++, 자바 등을 이용해 코딩할 때는 int 자료형을 필수적으로 이용한다.

- 기본 int 자료형의 표현 범위는 -2,147,483,648 ~ 2,147,438,647 인데 이 말은 int 자료형으로 처리하면 2,147,438,647보다 큰 수를 처리할 수 없다는 의미이다.

- 더 큰 수를 처리해야 할 때는 크기가 8바이트인 long과 같은 자료형을 사용하는데, 이 또한 9,223,372,036,854,775,807 보다 큰 수를 처리할 수 없다.

- 따라서 훨씬 큰 수를 담을 변수를 만들려면 흔히 BigInteger 클래스를 구현하거나 이용해야 한다.

- 자바의 경우 BigInteger를 표준 라이브러리로 지원하지만, C++의 경우 표준 라이브러리에도 포함되어 있지 않다.

- 대체로 long에서 다룰 수 있는 수보다 더 큰 정수를 처리하는 문제는 잘 출제되지 않는다.

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

정수형 종류	자료형의 크기	자료형의 범위
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만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점만 기억하자.

- 시간 제한이 1초이고, 데이터의 개수가 100만 개의 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야한다.

    ㆍ실제로 N = 1,000,000일 때 Nlog(2)N은 약 20,000,000이기 때문이다.

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

 

구현 문제에 접근하는 방법

- 보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴  편이다.

- 문제의 길이를 보고 지레 겁먹는데, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

- 구현 유형의 문제는 C/C++나 자바로 문제를 풀 때 더 어렵게 다가온다.

- 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데, C/C++나 자바에서는 문자열 처리가 파이썬에 비하여 까다롭고, 큰 정수를 처리하는 라이브러리를 별도로 사용해야 하기 떄문이다.

- 반면 파이썬은 기본 문법만 알아도 상대적으로 구현 유형의 문제를 쉽게 해결할 수 있다.

* 초보자 입장에서의 파이썬과 C/C++ 비교 *

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

 

- 실무에서 파이썬으로 프로그램을 개발할 때는 GPU를 연동하며, 반복적인 행렬 계산을 요구하는 복잡한 수학 문제를 풀 때는 C언어로 작성된 파이썬 코어 소프트웨어가 동작한다.

- 그렇기 때문에 파이썬을 쓴다고 해서 항상 프로그램의 동작 속도가 느린 것은 아니다. 하지만 알고리즘 코딩 테스트 환경에서는 GPU연산을 쓰는 경우가 없기 때문에 그러한 사항을 고려하지 않는다.

- 또한 자동 채점 방식을 이용하는 코딩 테스트 환경에서는 점점 Pypy3를 지원하는 곳이 늘고 있다.

- Pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행속도가 더 빠르다.

    ㆍ때로는 Pypy3의 실행속도가 C/C++와 견줄만큼 빠르다.