알고리즘 공부

1. 백트래킹

- 보통 재귀 형태

- 특정 파라미터 값에 따라 종료, 다음 재귀로 넘어가는 과정에서 값을 증가

- 하노이탑(재귀 문제), 모든 경우의 수 출력 등 다양한 곳에서 사용

 

2. DFS : 재귀

- 백트래킹의 형태로 보통 구현, 그래프 이론에서 사용되는 특수한 형태

 

3. BFS : 큐

- 큐를 사용한 탐색

- 모든 경우의 수를 탐색 -> 시간 복잡도가 큰 편

- 간선의 가중치가 모두 동일한 경우 -> 시간 복잡도가 작거나, 최단 거리 탐색에도 사용 가능

 

4. 다익스트라 : 최단 거리 탐색

- 가중치가 음이 아닌 경우만 사용 -> 벨만-포드 알고리즘 사

- 시간 복잡도 O(ElogV)

- V: 노드의 숫자, E: 간선의 숫자이다.

- 간선이 10만개로 주어지는 문제는 보통 다익스트라

 

5. 플로이드 워셜 : 최단 거리 탐색

- 시간 복잡도 O(N^3)

- N이 매우 작은 경우 사용

- 임의의 경로에서 다른 경로로 탐색하는 경우가 매우 많은 경우 사용

 

6. 벨만 포드 : 최단 거리 탐색

- 음수 가중치 사이클이 있어도 사용 가능

- 최단 거리가 무한히 작아지는 경우 -1을 출력해야한다 => 벨만 포드 사용

 

7. 이분 탐색

- 특정 값을 O(logN)내에 찾기 위한 알고리즘

- 값의 범위가 10억 정도로 큰 경우 사용

 

8. 누적 합

- 특정 구간의 합을 여러 번 쿼리하는 문제에서 주로 사용

 

9. 투 포인터

- 주로 정렬과 함께 사용

- 배열을 탐색하는데 O(N^2)인 경우 시간 초과가 난다 -> 투 포인터 문제

 

10. 슬라이딩 윈도우

- 정해진 길이의 구간 합을 구하는 경우 사용

- 연속된 특정 구간의 최대/최소 값을 구하는데, 구간의 길이가 긴 경우 => 슬라이딩 윈도우

 

11. 유니온 파인드 - 분리 집합

- 두 노드가 같은 그래프에 속하는지 판단하기 위한 자료구조

- O(N)의 공간 복잡도

- DFS로 해결하기에 그래프가 큰 경우, 유니온 파인드로 그래프 판단

 

12. 최소 스패닝 트리 - 최소 신장 트리

- 모든 정점을 연결하되, 사이클이 없이 최소 가중치로 연결되는 그래프

- 간선을 오름차순으로 정렬, 가장 가중치가 낮은 간선이 연결하는 두 노드를 유니온 파인드로 판단하여, 이미 그래프에 속해있는지 판단

- 그래프를 잇는 최소 비용 -> 최소 스패닝 트리

 

13. LCS (Longest Common Sequence/Substring) - 최장 공통 부문 수열/문자열

- 다이나믹 프로그래밍을 이용한 알고리즘

- 두 문자열의 가장 긴 공통 부분을 찾는다.

 

14. 트리

1) 세그먼트 트리, 인덱스 트리

- 특정 구간의 합/최대값/최솟값 등을 구하되, 그 구간의 내부가 변경되는 경우 사용하는 자료구조

- 특정 합을 저장해놓는 트리를 구현한 형태

2) LCA (Lowest Common Ancestor) - 최소 공통 조상

- 트리 구조에서 가장 가까운 공통 조상을 찾음

- 단순 탐색이 가능하지만, 시간 복잡도 상 다이나믹 프로그래밍을 이용하여 구현하는 문제가 많다.

 

15. 브루트포스 알고리즘

- 모든 경우의 수를 탐색하는 매우 간단한 로직

- 시간 복잡도가 매우 큰 편 -> 조건이 작다면 브루트 포스 가능성

 

16. 그리디 알고리즘

- 순간 순간의 해를 적립해나가면 최적 해가 되는 알고리즘

- 보통 시간복잡도가 O(N), N이 큰 경우며 특정 알고리즘이 없으면 그리디 알고리즘

 

17. 다이나믹 프로그래밍

- 메모이제이션으로 이전 값을 저장해두어 최적화

- 대표 예시 : 피보나치 함수

 

18. 정렬

- 버블 소트, 퀵 소트, 머지 소트, 카운팅 소트 등 다양한 정렬 방법이 존재. (코딩 테스트에서는 거의 출제 x)

 

19. 자료 구조

- 스택, 큐, 우선순위 큐, 집합, 해시 등의 여러 자료구조 존재

- 우선순위 큐와 그리디 알고리즘이 같이 사용되는 경향이 있다.