구현 (implementation)

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

 

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정을 구현이라고 한다.

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

실제로 코딩 테스트에서 구현 문제를 보면 당황할 수 있다. 어떻게 풀면 될지 대략 감은 오는데, 막상 소스코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있기 때문이다.

예를 들어 파이썬으로 코딩 테스트에 응시했는데, N 개의 원소가 들어 있는 리스트에서 R 개의 원소를 뽑아 한 줄로 세우는 모든 경우를 구해야 하는 문제를 만나면 어떻게 할까?

무작정 기능을 전부 작성할 수도 있다.
하지만 파이썬은 itertools 와 같은 표준 라이브러리로 쉽게 짜는 방법도 있다.
이는 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법이다.

완전 탐색, 시뮬레이션 유형은 모두 구현 유형으로 묶어서 다룬다.

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

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

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

 

C/C++/Java에서의 정수형을 표현할 때 주로 int 자료형을 주로 사용하며 이 자료형의 크기는 4바이트이다.

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

더 큰 수는 크기가 8바이트인 long long과 같은 자료형을 사용하면 되지만 이마저도 9,223,372,036,854,775,807보다 큰 수를 처리할 수 없다.
따라서 훨씬 큰 수를 담을 변수를 만들려면 흔히 BigInteger 클래스를 구현하거나 이용해야 한다.

반면 파이썬에서는 자료형 크기 제약을 받지 않기 때문에 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 좋다.

 

- 파이썬에서 리스트 크기

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

파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자.

 

출처 :

이것이 코딩테스트다 with 파이썬 - 나동빈