[이코테] chap4. 구현

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

 

구현(implementation) 이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.

어려운 구현문제는 어떤 유형인가?

• 알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제
• 특정 소수점 자리까지 출력하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 파싱하는 문제 등 -> 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다.

그러므로 구현 문제일수록 파이썬이 빛을 발하는 언어이다.

• 예를 들면, N개의 원소가 들어있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야하는 문제를 만난다면 무작정 기능을 짜는 것 보다
  파이썬의 itertools 와 같은 표준 라이브러리로 쉽게 해결 가능하다

1.  완전 탐색, 시뮬레이션

[이 책에선 완전 탐색, 시뮬레이션을 구현 유형에 묶어서 다룬다.]

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

• 시뮬레이션
문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법.

2.  고려해야할 메모리 제약 사항

C/C++ 에선 기본 int, long long 등 정수 범위를 가진 변수형이 존재하여, 문제에 주어지는 입력값에 대해서 범위를 확인해야하는 경우가 존재한다.

하지만 파이썬의 경우 직접 자료형을 지정할 필요가 없으며, 매우 큰 수의 연산 또한 기본으로 지원한다.

따라서 파이썬을 이용한다면 자료형의 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 된다.
다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라 연산 결과가 원하는 값이 나오지 않을 수 있다.

• 파이썬에서 리스트 크기

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

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

그러므로 크기가 1000만 이상인 리스트가 있다면 용량 제한으로 문제가 안풀릴 수 있다는 점을 기억해야한다.

하지만, 대체로 이런 문제가 나오는 경우는 드물다. 따라서 더 적은 크기의 메모리를 사용해야 한다는 점만 기억하자.

3.  채점 환경

대체로 1초에 2000만번의 연산을 수행하면 통과한다.

but, 시간 제한 1초 & 데이터의 수가 100만개(메모리 제한 128MB) => 일반적으로 시간 복잡도는 O(NlogN) 이내의 알고리즘을 이용해 문제를 풀어야 한다.

4.  정리

• 시간 복잡도에선 N이 1000개인 경우 되도록 $$O(N^2)$$ (100만)을 넘지 말자.
• 1초 & 데이터의 수가 100만개 라면 일반적으로 시간 복잡도는 O(NlogN) 이내의 알고리즘을 이용해 문제를 풀어야 한다.
• 공간 복잡도에선 list의 크기를 1000만개(40MB) 이상으로 잡으면 통과하지 못한다. -> 100만개 미만으로 잡을 것.
• 1초에 2천만번 연산까지도 가능하다.