Python x 알고리즘 : 구현(Implementation)

"구현"이란 

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

 

• 문제 해결 분야에서 구현 유형의 문제는 "풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제"를 의미한다.
• 프로그래밍 언어의 문법에 능숙하고 코드 작성속도(타자)가 빠른 사람처럼 피지컬을 요구하는 문제가 구현문제이다.
• 전략을 잘 짰다고 해도 빠르게 풀지 못하면, 구현 문제를 풀기 어렵다
• 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제, 특정 소수점 자리까지 출력하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱)문제 등이 까다로운 구현 유형의 문제의 예다.

 

완전 탐색, 시뮬레이션을 구현 유형으로 볼 수 있는데

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

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

 

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

• C/C++에서 변수의 표현 범위

int (4바이트): -2,147,483,648 ~ 2,147,483,647
long long (8바이트): -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
BigInteger 클래스 : 더 큰 수를 담은 변수

 

• 파이썬에서 리스트 크기

데이터 개수: 1000 -> 약 4KB
데이터 개수: 1000,000 -> 약 4MB
데이터 개수: 1000,000,000 -> 약 40MB

파이썬에서 수백만 개 이상의 데이터를 처리해야 하는 문제에서는 메모리 제한을 고려해야한다.

 

 

채점환경

• 속도 : 파이썬 < C/C++ 파이썬이 더 느리다
• 따라서 파이썬을 선택했을 때는 C/C++에 비해 2배의 수행 시간 제한을 적용기도 한다.
• 2020 파이썬 3.7 기준 - 1초에 2000만번 연산 수행으로 가정하고 풀이
• 제한시간이 1초이고, 데이터의 개수가 100만개인 문제

-> 시간 복잡도 O(NlogN)이내의 알고리즘을 이용하여 문제 풀이

 

PyPy3: 파이썬3의 문법을 그대로 지원, 대부분 파이썬3보다 실행 속도 빠르다