구현(Implementation)

: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

• 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다.

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

• 피지컬(프로그래밍 언어의 문법에 능숙하고, 코드 작성 속도가 빠른 것)을 요구하는 문제 유형

까다로운 구현 문제란?

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

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

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

대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다. 특히 초보자 입장에서는 프로그래밍 언어의 문법부터가 익숙하지 않기에 더 어렵게 느껴진다.

구현 문제의 유형

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

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

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

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

int 자료형

• 크기 : 4Byte
• 표현 범위 : -2,147,483,648 ~ 2,147,438,647

  즉, int 자료형으로 처리하면 2,147,438,647보다 큰 수를 처리할 수 없다.

• C/C++, Java 등 프로그래밍 언어에서 정수형(integer)을 표현할 때는 int 자료형을 주로 사용한다.

long 자료형

• 크기 : 8Byte
• 표현 범위 : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,808

BigInteger

• 크기 : 가변적
• 표현 범위 : 제한 없음

📌 BigIntegerr 라이브러리

• Java에서는 표준 라이브러리로 지원함
• C++에서는 표준 라이브러리로 지원하지 않음. 코딩 테스트 중에 이를 직접 작성하기에는 어렵기 때문에 보통은 인터넷에서 검색해 외부 라이브러리 형태로 그대로 가져와 사용한다.
• 사실, 보통 long에서 다룰 수 있는 수보다 더 큰 정수를 처리하는 문제는 잘 출제되지 않는다.

💡 Python에서의 자료형 선택?

• Python에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며, 매우 큰 수의 연산 또한 기본적으로 지원한다.
• 실제로 코딩 테스트/프로그래밍 대회 등에서도 파이썬을 선택했다면 정수형 변수의 연산 때문에 머리 아플 일은 없을 것이다.
• 다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자.

Python에서의 리스트 크기

코딩테스트에서 파이썬 리스트를 이용할 때에는 메모리 제한을 고려해야 한다.

대체로 코딩테스트에서는 128 ~ 512MB로 메모리를 제한하는데, 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되고는 한다.

앞서 다루었던 int 자료형의 데이터 개수에 따른 메모리 사용량을 확인해보자. 파이썬에서 시스템 내부적으로는 다음 표에서 보여주는 것과 유사한 크기 만큼 메모리를 차지한다.

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

데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자.

리스트를 여러 개 선언하고, 그 중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다.

참고 자료

• 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 저, 한빛미디어