[알고리즘] 코딩테스트 전, 알고리즘 문제 유형 정리

※ 생각 나는 대로 적는 중... (잘못된 부분이 있을 수도 있음)

 

브루트 포스 (완전 탐색)

• N의 범위를 잘 파악해서 1초 미만으로 해결이 가능한 경우
• 10! 이하의 시간복잡도인 경우 (재귀 호출 시 깊이가 10 이하인 경우)

 

1. 백트랙킹

• 순열 : 순서 고려 O, 값의 중복 X (시간복잡도 : O(N!) )
• 중복 순열 : 순서 고려 O, 값의 중복 O (시간복잡도 : O(n ^ r), 여기서 r은 재귀의 깊이 )
• 조합 : 순서 고려 X, 값의 중복 X
• 중복 조합 : 순서 고려 X, 값의 중복 O
• 재귀 호출 시 깊이를 보고 시간복잡도 파악 가능하다.

 

 

2. BFS

• 출발값이 존재
• 도착값까지 '최소' 시간 or 거리 or 횟수 만에 도착해야하는 경우
• 간선의 가중치(노드 간 거리)가 전부 같은 경우 (무가중 그래프)

 

3. 비트마스크 (BitMask)

• 정수 하나로 특정값의 방문여부를 체크할 수 있다.
• 메모리 비용을 아낄 수 있는 경우
• int형의 경우 32비트를 사용 가능하므로 0~31까지의 수의 방문 여부를 체크 가능하다.

---

이분 탐색

• 최소 or 최대값을 구하는 문제
• 선형 탐색 시 시간복잡도가 너무 커서 O(log N)만에 값을 찾아야 되는 경우
• 결과값들이 정렬 되어 있는 경우 → 최소값을 구하는 경우라고 치면 현재까지 찾은 수보다 큰 수들은 답이 될 수 없음이 확실한 경우
•  BFS와 같이 쓰이는 경우가 종종 있음

---

그래프 이론 문제

• 가중 그래프 여부 확인
• 무향, 유향 그래프 여부 확인
• 노드, 간선 정의를 할 수 있어야 한다.

 

1. DFS

• 백트랙킹에서 자주 쓰임
• 사이클 찾기 문제
• 그래프 완전 탐색 알고리즘
• 시간복잡도 : O(V + E)
• 무가중 그래프
• 최단 거리는 절대 찾을 수 없음

 

2. DFS + DP

• 문제의 가정에서 갈 수 있는 방향이 목표지점까지로만 갈 수 있도록 제한되어 있어야 한다. (사이클 x)
• 경로 수 구하기
• 유향 그래프에서 사용 가능
• 즉, (1, 1)에서 (N, N)으로 간다고 쳤을 때 무조건 ↓, → 방향으로만 갈 수 있도록 가정이 되어야함

1890번: 점프

 

3. BFS

• 출발지점 → 도착지점까지 최단 거리(경로) 찾기
• 무가중 그래프
• 그래프 완전 탐색 알고리즘
• 시간복잡도 : O(V + E)

 

4. BFS + DP

• 가중 그래프에서도 사용이 가능하다.
• 메모이제이션을 통해 재방문이 가능한 경우를 정의하는 것
• 다익스트라 대신 사용 가능

코딩테스트 연습 - 경주로 건설

1005번: ACM Craft

 

5. 다익스트라

• 가중 그래프
• '특정 노드 → 모든 노드'까지 가는데의 최소 비용 구하기
• 간선마다 가중치가 다른지 파악해야한다. (가중치가 같다면 BFS 사용 가능)
• BFS 기반
• 그리디 알고리즘
• 시간복잡도 (우선순위 큐 사용 o) : O(E log V)
• 시간복잡도 (우선순위 큐 사용 x) : O(V ^ 2 + E)

 

6. 플로이드-와샬

• 가중 그래프
• '모든 노드 → 모든 노드'까지 가는데의 최소 비용 구하기
• 시간복잡도 : O(N ^ 3)

 

7. 최소 신장 트리

• 출발점, 도착점이 따로 안 정해져 있고 모든 노드를 최소 비용으로 방문하는 것이 목적인 경우
• 따라서 모든 노드가 연결되어 있는 경우
• 종류 : 크루스칼 알고리즘, 프림 알고리즘

1922번: 네트워크 연결

 

8. 위상 정렬

• 앞서 있는 노드들을 모두 방문 완료해야 그 다음 노드를 방문 가능한 경우
• 사이클이 없는 유향 그래프인 경우
• DP랑 섞이는 문제가 종종 나온다.
• EX) 그래프에서 특정 노드까지의 경로 수 구하기
• EX) A, B 건물을 모두 건설 완료해야 C 건물을 건설할 수 있다.

1005번: ACM Craft

---

문자열 처리

• 스택, 큐, 우선순위 큐와 같은 자료구조의 활용이 중요
• 특히 스택의 활용성이 두드러짐 EX) 괄호쌍 찾기, O(N)만에 문자열 구성

 

1. KMP

• 패턴찾기 알고리즘
• failureFunction만 따로 쓰여서 응용되는 경우도 있다.
• 패턴이 겹칠 수 있는 경우도 세어야 할 때 사용
• EX) 'eraserase' 문자열에서, 'erase' 패턴 찾기 : 총 2번이 등장한다. 

 

2. Trie

• 문자열들을 저장하고 문자열 검색 시 O(log N)만에 찾을 수 있게 하는 자료구조
• 접두어, 접미어 관련 문제

코딩테스트 연습 - 가사 검색