chapter4. 구현

코딩 테스트 에서 구현(implementation)이란?  

 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 이라고 책에서 소개하고 있다.

 

주로 머릿속에서 떠올리기는 쉽지만 구현이 복잡하거나 어려운 문제들이 출제되는 경향이 많다고 한다. 그럼 이를 위해서 우리는 피지컬을 키워야 한다고 나온다.

 코딩에서 피지컬이란, 프로그래밍 문법에 능숙하고 코드작석 속도가 빠른 것을 일컫는다. 

 

구현에서 주의 해야 할 점들을 몇가지 소개 하고 있다.

 

<c/c ++ 와 자바에서 정수형 종류에 따른 범위>

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

 

 

<파이썬에서 리스트 크기>

 

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

크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 유의해야 한다.

 

<파이썬 연산 속도>

그럼 연산 속도 제한을 맞추기 위해서는 대략 자신의 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 풀면 안정적으로 통과 가능