[Algorithm 개념] 구현 Implementation

이것이 코딩테스트다 with 파이썬 개념 정리 

 

구현

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 
• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미 

 

구현하기 어려운 문제 

1. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 
2. 특정 소수점 자리까지 출력해야 하는 문제 
3. 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는 (파싱을 해야하는) 문제 
4. 사소한 조건 설정이 많은 문제

 

완전탐색 

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

 

시뮬레이션 

• 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 

 

구현 문제 접근

- 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편임 

 

 

cf) 메모리 ,시간 제한 고려 사항 

파이썬에서 리스트 크기 

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

 

• 파이썬은 1초에 2000만 번의 연산을 수행한다고 가정하고 문제를 풀면 시간제한에 안정적임
• (ex) 시간제한이 1초, 데이터 개수가 100만개 -> 시간복잡도 O(NlogN) 이내의 알고리즘을 이용하여 풀어야 함  (N=1,000,000일 때 NlogN은 20,000,000 이기 때문) 
• 시간 제한과 데이터 개수를 확인하고 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 함.