코딩 테스트 문제 풀이 전략

1. 문제를 한 번에 분석하지 말고 동작 단위로 쪼개서 분석하여 한 번에 생각해야 하는 양을 줄여라.

2. 제약 사항을 정리해두고 테스트 케이스를 추가하라.

3. 입력값을 분석하라.

4. 핵심 키워드를 파악하라.

	키워드	상황
스택	- 쌍이 맞는지 - 최근	- 무언가를 저장하고 반대로 처리해야 할 때 - 데이터의 조합이 균형을 이뤄야할 때 - 알고리즘이 재귀 특성을 가질 때 - 최근 상태 추적
큐	- 순서대로 - ~대로 동작하는 경우 - 스케줄링 - 최소 시간	- 특정 조건에 따라 시뮬레이션할 때 - 시작 지점부터 목표 지점까지 최단 거리
깊이 우선 탐색	- 모든 경로	- 메모리 사용량이 제한적일 때의 탐색 - 백트래킹 문제를 풀 때
너비 우선 탐색	- 최적 - 레벨 순회 - 최소 단계 - 네트워크 전파	- 시작 지점부터 최단 경로나 최소 횟수를 찾아야할 때
백트래킹	- 조합 - 순열 - 부분 집합	- 조합 및 순열 문제 - 특정 조건을 만족하는 부분 집합
최단 경로	- 최단 경로 - 최소 시간 - 최소 비용 - 트래픽 - 음의 순환 - 단일 출발점 경로	- 다익스트라: 특정 지점에서 나머지 지점까지 가는 최단 경로 - 벨만-포드: 음의 순환 탐지, 음의 가중치를 가진 그래프에서 최단 경로

 

5. 데이터의 흐름이나 구성을 파악하라.

6. 컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다. 따라서 초당 연산 횟수가 3,000만이 넘는 알고리즘을 사용하지 말 것! (다음은 제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 최대 연산 횟수이다)

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2^N)	20~25
O(N^3)	200~300
O(N^2)	3,000~5,000
O(NlogN)	100만
O(N)	1,000~2,000만
O(logN)	10억

 

7. 부동소수형(float) 데이터를 활용하는 문제에는 오차 허용 범위를 언급하는 경우가 많다. 엡실론을 신경 쓰자.

(sys.float_info.epsilon보다 작으면 두 값을 같다고 판단)

8. 조기 반환으로 예외 처리/보호 구문을 작성하자.

9. 합성 함수를 활용하자. func = lambda x: funcA(funcB(x))