피지컬로 승부하기
구현(Implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.
흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.
개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도(타자)가 빠른 사람을 보고 '피지컬이 좋다'라고 이야기하는데, 구현 유형의 문제는 그런 의미에서 '피지컬을 요구하는' 문제라고도 할 수 있다.
이 책에서는 모든 경우의 수를 모두 계산하는 해결 방법인 완전 탐색, 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 시뮬레이션 유형을 모두 구현으로 취급하여 다룬다.
구현 시 고려해야 할 메모리 제약 사항
C/C++에서 변수의 표현 범위
기본 int 자료형의 표현 범위는 -2,147,483,648 ~ 2,147,483,648인데 이 말은 2,147,483,648보다 큰 수는 int로 처리할 수 없다는 뜻이다.
더 큰 수는 long long과 같은 자료형을 사용하는데, 이 자료형 또한 9,223,372,036,854,775,807보다 큰 수를 처리할 수 없다. 훨씬 더 큰 변수를 만들려면 BigInteger를 사용해야 한다.
long long보다 큰 수를 처리하는 문제는 잘 출제되지 않으므로 넘어가자. 또한 파이썬에서는 직접 자료형을 지정할 필요가 없기 때문에 매우 큰 수의 연산 또한 기본적으로 지원한다.
파이썬에서 리스트의 크기
파이썬에서 리스트를 이용할 때 고려해야 할 사항이 있는데, 바로 코테의 메모리 제한이다. 대체로 128~512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이쌍의 데이터를 처리해야 하는 문제가 출제되곤 한다. 이럴 때는 메모리 제한을 염두에 두고 코딩해야 한다.
파이썬은 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려해야 한다. 리스트를 여러 개 선언하고, 그중에서 크기가 1,000만(40MB) 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억하자.
구현 문제에 접근하는 방법
보통 구현 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 하지만 그렇게 고차원적인 사고력을 요구하는 문제는 잘 나오지 않기 때문에 문법에 익숙하다면 오히려 쉽게 풀 수 있다.
