5. 구현 : 문제 풀이 전략

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

 

1. 피지컬

 

구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려움.

그렇기 때문에 다른 문제를 먼저 풀고 푸는 것이 좋음.

언어의 문법이 능숙하고 코드 작성 속도가 빠른 사람을 '피지컬'이 좋다. 라고 표현.

 

2. 구현이 어려운 문제

 

알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제.

특정 소수점 자리까지 출력해야 하는 문제.

문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는 (파싱)하는 문제.

대체로 사소한 조건 설정이 많은 문제.

 

표준 라이브러리 사용 경험이 필요.

 

3. 유형

 

완전 탐색, 시뮬레이션 유형

완전 탐색 : 모든 경우의 수를 주저 없이 다 계산

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

----------------------------------------------------------------------------------------------------------

 

파이썬에서 자료형 크기

 

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

1,000 - 4KB

1,000,000 - 4MB

1,000,000,000 - 40MB

코딩 테스트에서는 128 ~ 512MB가 주어짐.

때로 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제 되곤 함.

 

파이썬

 

파이썬은 동작 속도가 느리다.

자신의 코드가 1초에 2000만 번의 연산을 수행한다고 가정하고 문제를 풀면 안정적. (2020년 기준)

일반적으로

시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제.

1초에 연산 횟수가 20,000,000이기 때문에, O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.

 

pypy3

 

pypy3는 C와 C++와 견줄만큼 빠름.

python의 코드로 동작하기 때문에 코딩 테스트 환경이 위 언어를 지원한다면 활용하는 것이 좋음.

 

API 개발 문제

 

api 개발 문제가 출제 된 적이 있었음. (카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성)

웹 서버나 데이터 분석에 대한 기초 지식이 필요.