코딩 테스트 문제 유형 파악하기

 

 

시작에 앞서, 알아야 하는 연산량에 따른 수행 속도

1억(100,000,000 = 10^8) → 1초

 

 

---

 

 

 

1. 입출력 제한 보고 파악하기

 

1) 입력이 100 이하인 경우 (입력값 범위가 매우 작은 경우)

• 완전 탐색
• 백트래킹 (?)

 

2) 입력이 10,000 (10^4, 만) 이하인 경우

• 최대 O( N^2 ) 이내로 끝내야 함 ( 문제따라 O( N^2 log N ) 까지도 허용)
• N x N 차원 리스트를 모두 순회하는 문제 ↑

 

3) 입력이 1,000,000 (10^6, 백만) 이하인 경우

• 최대 O( N log N ) 으로 끝내야 함
• 힙, 우선순위 큐
• 정렬
• DP
• 위상 정렬
• 다익스트라 알고리즘

 

4) 입력이 100,000,000 (10^8, 억) 이하인 경우

• 최대 O( N ) 으로 끝내야 함
• DP
• 그리디

 

5) 그 이상인 경우

• 최대 O( log N ) 으로 끝내야 함
• 이진 탐색
• 출제 빈도 ↓

 

2. 문제의 특징을 보고 파악하기

 

1) 입력값이 작은 문제

• 완전 탐색
• 백트래킹

 

2) 지도가 주어지고 채워진 영역을 찾아야 하는 경우

• BFS / DFS

 

3) 그래프 그림이 있는 경우

• 최단 거리 찾기 → 다익스트라, 플로이드 워셜, 밸만 포드
• 최소 신장 트리 (가장 저렴한 방법으로 모두 연결)  → 크루스칼, 프림
• 위상 정렬

 

4) 실시간 정렬 수행

• 우선순위 큐 / 힙

 

5) DP

 

"여러 번 해보고 점화식을 만들 수 있다" or "문제를 보고 유형 파악이 어렵다"

 

① 문제에서 주어진 초기값 적기

② 초기값을 포함한, 계산 가능한 상태값들 적기

③ 현재 알고 있는 값들을 통해, 다음 값들을 구할 수 있는지 판단

④ 혹은 이전 값들을 통해, 현재값을 구할 수 있는지 판단

 

 

6) 문자열이 주어지는 경우

• 구현
• 빌트인 사용

 

7) 가장 최적의 선택

≫ 가장 많은 선택, 가장 큰, 가장 작은 ···

• 그리디 ( 최소 신장 트리 포함 )

 

위의 내용들은 결정적인 것은 아니고 확률적으로 가능성이 높다일 뿐이니 참고만 하자!

 

 

참고 자료

https://hh-bigdata-career.tistory.com/24