코딩 테스트 문제를 정복해보자
💡 새롭게 알게된 점
입력에 따른 사용 알고리즘
입력이 100 이하인 경우
완전 탐색
백트래킹
입력이 10,000 이하인 경우
최대 O(n^2) 이내로 끝내야하는 문제
문제에 따라 O(n^2 log n)까지는 허용
n*n 2차원 리스트를 모두 순회해야하는 문제가 많음
입력이 1,000,000 이하인 경우
최대 O(n log n)으로 끝내야하는 문제
힙, 우선순위 큐
정렬
동적 계획법
위상 정렬
다익스트라 알고리즘
입력이 100,000,000 이하인 경우
최대 O(n)으로 끝내야하는 문제
동적 계획법
그리디
그 이상인 경우
최대 O(log n)으로 끝내야하는 문제가 많음
거의 안나오는 문제 유형
이진탐색
문제 유형에 따른 사용 알고리즘
입력값이 작은 문제
완전 탐색 혹은 백트래킹 문제
지도가 주어지고 채워진 영역을 찾아야하는 경우
높은 확률로 BFS, DFS 문제
FloodFill과 같이 정직한 방식으로 나오거나 전염병 문제나 치즈 문제처럼 변형되어 나오는 경우가 있음
그래프 그림이 있는 경우
높은 확률로 최단 거리 찾기, 최소 신장 거리, 위상 정렬 중 하나의 문제
최단 거리 찾기
‘가장 빠른 길’, ‘최단 거리’ 같은 키워드나 ‘~ 비용 내로 갈 수 있는 길 찾기’ 같은 키워드가 나와도 최단 거리 찾기 유형
다익스트라, DFS, BFS 사용 가능
최소 신장 거리
‘가장 저렴한 방법으로 모든 경로 연결’ 등의 키워드로 출제
양방향 그래프, 단방향 그래프 모두 가능
크루스칼, 프림 사용 가능
위상 정렬
순서를 정해야할 때 사용
보통 ‘순서’, ‘차례’ 등의 키워드가 나오면 위상 정렬 문제
X라는 조건을 만족하는 가장 최대/최소값을 찾아라
높은 확률로 결정 문제
파라메트릭 서치를 통해 해결 가능
실시간으로 정렬이 이루어져야 하는 경우
높은 확률로 우선순위 큐 혹은 힙 사용하는 문제
DP 문제
보통 완전 탐색처럼 시간이 오래 걸리면 안되는데 특별한 알고리즘을 사용하는 문제가 아닐거 같을 때 높은 확률로 DP 문제
문자열이 주어지는 경우
높은 확률로 구현력 문제
문자열을 자르거나 붙이는 경우가 대부분
현재 상황에서 가장 최적인 선택을 해야하는 경우
문제에서 항상 최적의 선택을 해야하는 경우 혹은 ‘가장 많은 선택을 할 수 있는’, ‘가장 작은/큰’ 등의 키워드가 들어가면 높은 확률로 그리디 문제
엣지 케이스 찾기
입력 값에 따른 엣지 케이스
입력 값의 크기가 굉장히 작은 케이스 (대부분의 입력 값이 최대값 언저리인 경우)
입력 값의 크기가 굉장히 큰 케이스 (대부분의 입력 값이 최소값 언저리인 경우)
입력 값의 범위가 넒은 케이스 (A는 최소값이고 B가 최대값인 경우)
음수 입력이 허용된 경우 음수만 입력받는 케이스
리스트를 입력 받을 때 값이 없거나 하나만 있는 케이스
상황에 따른 엣지 케이스
그래프에서 사이클(cycle)이 발생하는 경우
길찾기 문제에서 지그재그로 움직일 경우
부동소수점 오차
❗️ 느낀점
여태까지 코딩 테스트를 풀 때 아직 익숙하지 않아 어떤 알고리즘을 사용해야 할지 모르기 때문에 우선 적고 봤다.
그래서 코드를 다 짜고 난 후 효율성에서 통과하지 못하는 경우가 많았는데, 오늘 배운 내용을 토대로 앞으로 코딩 테스트 문제를 풀기 전에 어떤 알고리즘을 적용하면 최고의 효율이 나올지 먼저 생각하는 습관을 길러야겠다.