- 자료구조의 이해(스택, 큐, 해쉬맵, 트리, 그래프)
- 문제를 해결할 때 간접적으로 사용됨. 예를 들면 BFS 알고리즘을 구현할 때는 큐를 사용하고, 다익스트라 알고리즘이나 프림 알고리즘의 경우에는 우선순위 큐를 활용.
- 그래프를 표현할 때, 주로 인접 리스트를 사용하는 것이 편리.
- 그리디, 구현(시물레이션)
- 주로 정렬과 우선순위 큐를 이용하여 문제 풀이.
- 몇일 이내에 최대로 되는 경우를 구하라는 문제는 정렬 순서를 반대로 고려.
- 구현은 모든 알고리즘 문제에서 활용. 여러 문제를 풀어보는 것이 좋음.
- 완전 탐색(Bruteforce) - DFS, BFS, 백트래킹
-
BFS로 풀어야 할까 DFS로 풀어야 할까는 문제의 상황마다 다름. 단순 모든 정점을 방문한다면 DFS, BFS 어느 것을 사용해도 괜찮음.
최단거리(최단루트)를 구하는 문제 -> BFS 효과적, 왜냐하면 BFS는 같은 레벨의 노드들 부터 탐색하기 때문(DFS의 경우 방문했던 곳이 최단 루트가 아닐 수도 있음)
방문했던 곳까지의 경로 정보를 저장(활용)해야 하는 경우 -> DFS 효과적 -
BFS를 사용하여 최단거리를 구할 때, 최단 거리를 저장하는 배열을 만드는 과정에서 초기 값을 -1로 설정하면 visited 배열을 굳이 만들어주지 않아도 됨. (코드가 간결해짐.)
-
우선순위 큐를 이용하여 가중치가 큰 값부터 방문할 수도 있음.
-
백트래킹과 DFS의 차이는 백트래킹은 탐색 도중 조건이 일치하지 않는다면, 끝까지 탐색하지 않고 다음 노드(같은 레벨의 노드)로 이동한다는 점이다.
-
비트마스크를 활용하면 완전 탐색 문제를 쉽게 해결할 수도 있음.
-
DFS의 경우, 스택이나 재귀를 사용할 수 있음. 그러나 재귀와 스택의 차이점은 재귀가 함수의 리턴을 통해 방문이 완료된 정보를 이전 노드(방문한 곳)에 제공할 수 있는 반면, 스택은 한 번 pop()된 노드는 별도로 저장하지 않으면 완료된 정보를 이전 노드에 제공할 수 없음.(개인적으로 재귀를 사용하는 것이 편리)
- 이분 탐색(Binary search) - 반복문 사용(재귀를 사용해도 됨)
- 처음과 끝을 잘 설정(타겟이 처음과 끝에 범위에 있어야 함).
- 목표값과 중간값을 비교하며 처음 또는 끝을 갱신.
- 매개변수탐색 문제의 경우, upper-bound를 쓸건지 lower-bound를 쓸건지 판단해야한다.(찾고자
하는 타겟이 범위 안에 있을 수도 있음.)
-upper은 찾고자 하는 값(target)을 포함하는 구간의 최댓값을 찾고,
lower은 target을 포함하는 구간의 최솟값을 찾음. - mid 값과 target 값을 비교할 때, <= 및 >= 연산자만을 사용하여(lower, upper) 비교하도록 하는 것이 개인적으로 편리.
- 순열/조합
- 순열과 조합을 구현할 때 재귀를 사용하면 편리하다. 순열의 경우, 방문한 노드를 체크하여 구현할 수 있으며, 조합의 경우 현재 방문한 노드를 다음 재귀 호출에 전달함으로써 구현할 수 있음.
- 조합은 부분 집합을 이용하여 요소 수가 r개인 부분 집합을 구하는 방법을 사용할 수도 있음.
- 부분집합
- 포화이진트리를 생각해보면 쉽게 이해 가능.
- 비트마스크와 함께 활용하면 깔금하게 코드를 짤 수 있음.
- 분할정복
- 반복되는 부분을 찾는 것이 중요.
- 사분면 문제의 경우 size(2^d)를 통해 몇 사분면에 있는지 체크함.
- DP
- 점화식을 찾아서 푸는 문제의 경우 Top down(재귀) 방식과 Bottom up(반복문) 방식 둘 다 활용할 수 있음.
- 점화식 문제의 Top down 방식은 분할정복 문제 코드 구현 로직과 비슷.
- 이전의 경우로 부터 현재의 경우가 파생된다면, 다이나믹 프로그래밍(점화식)으로 풀 수 있음.
- Top down 방식의 경우, 점화식이 아닌 완전탐색 문제에서도 활용됨. 중복되는 부분을 찾아 메모리에 저장함. ex)외판원 순회 문제, 백준-내리막길, 파이프연결하기2
- 문자열 처리 문제
- 같은 문자열을 찾아 삭제하는 경우, 스택을 이용해보려고 하자. cf)중간에 같은 문자열을 삭제하면 처음부터 다시 검사해야함
- kmp 알고리즘
kmp 알고리즘의 핵심은 패턴 문자열과 타겟 문자열이 일치하지 않는 위치가 발생했을 때, 어느 패턴 문자열의 인덱스에서부터 다시 비교를 시작해야 하는지를 결정하는 것. - Trie 자료구조
- Aho-corasick(kmp+trie)
- 그외 기타 알고리즘
- union-find
각 원소에 대해 속한 집합을 표현하는 알고리즘 ex) ST(신장트리) 구현할 때나 크루스칼(MST) 알고리즘에 활용. - 누적합
여러 알고리즘 문제에서 활용됨. ex) DP점화식
- 그외 그래프 알고리즘
- 위상 정렬
InDegree(진입차수)가 핵심. - 세그먼트 트리
포화이진트리로 리프(단말) 노드에 실제 데이터가 적재. 조상 노드에는 구간에 대한 합, 최솟값, 최댓값 등이 적재. - LCA(최소 공통 조상)
- 다익스트라, 벨만포드, MST(프림, 크루스칼) [참고-https://jaeun-choi98.github.io/2023/10/05/data_structure(4)]