구현 (implementation)

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

보통 ps에서 구현문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다.

 

유형

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

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

 

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

 - C/C++/JAVA에서 변수의 표현 범위 (파이썬은 제한x)

  int (4byte): -2,147,483,678 ~ 2,147,483,677

  long long (8byte): -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

  BigInteger(가변적): 제한 x (String 형식으로 다루는 클래스)

 

 - 파이썬에서 리스트 크기 (다른 언어도 마찬가지)

 int 자료형 데이터의 개수에 따른 메모리 사용량

데이터의 개수	메모리 사용량
1000	약 4KB
1000000	약 4MB
10000000	약 40MB

✔ 채점 환경

 - 파이썬은 C/C++보다 동작 속도가 느리다 (아마 자바는 더 느릴걸?)

 - (파이썬 기준) 보통 1초에 2000만번의 연산을 수행할 수 있다

 

✔ 구현 문제에 접근하는 방법

 파이썬: 구현은 쉽지만 시간이 더 오래 걸림

 C/C++: 구현은 어렵지만 시간이 빠름

  (자바: 둘 다 아닐걸?)

 

 

출처| 이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈 저)