- 자료구조는 문제 해결을 위한 도구로, 알고리즘 구현 시 간접적으로 사용됨.
- 스택: DFS(깊이 우선 탐색) 구현, scc 등에 사용.
- 큐: BFS(너비 우선 탐색) 구현 시 사용.
- 우선순위 큐: 다익스트라 알고리즘이나 프림 알고리즘, 그리디 문제에서도 자주 활용.
- 그래프: 인접 리스트나 인접 행렬로 표현.
-
그리디 알고리즘:
- 매 순간 최적의 선택을 통해 전체 문제를 해결.
- 정렬과 우선순위 큐를 자주 활용.
- 예) 특정 기간 내 최대 이익 구하기: 정렬 순서 변경이나 우선순위 조정을 통해 해결.
-
구현 문제:
- 문제에서 제시된 조건을 가지고 자신이 생각한 논리를 코드로 구현.
- 알고리즘의 논리를 정확히 구현할 수 있도록 연습 필요.
-
BFS:
- 최단 거리 또는 최단 경로를 구할 때 적합.
- 같은 레벨의 노드부터 탐색하므로 최적 경로를 빠르게 찾음.
- 최단 거리 배열 초기 값을
-1로 설정하면 visited 배열 없이도 구현 가능.
-
DFS:
- 모든 경로를 탐색하거나 특정 조건을 만족하는 경로를 찾을 때 유용.
- 스택이나 재귀를 사용하여 구현. (개인적으로 재귀를 사용하는 것이 편리)
- 재귀는 함수 리턴 값을 활용해 정보를 이전 노드에 전달 가능.
-
백트래킹:
- DFS에서 조건이 맞지 않으면 해당 경로를 즉시 종료하고 다음 경로로 이동.
-
비트마스크 활용:
- 완전 탐색 문제에서 효율적으로 상태를 관리.
-
구현 방법:
while (left < right)또는while (left <= right)패턴으로 사용.- 일반적으로 전자를 사용해 코드의 일관성을 유지(개인적으로 전자가 더 편리).
- 타겟이 범위 안에 있을 수 있도록 처음과 끝을 잘 설정.
-
매개변수 탐색:
- 찾고자 하는 타겟이 범위 안에 있을 수 있음.
lower_bound: 찾고자 하는 값의 첫 등장 위치 반환.upper_bound: 찾고자 하는 값보다 큰 값이 처음 등장하는 위치 반환.
- 순열: 방문 여부를 체크하며 구현.
- 조합: 현재 방문한 노드를 다음 호출에 전달하여 구현.
- 부분 집합을 활용해 요소 수가
r개인 조합을 구할 수도 있음.
- 포화 이진 트리를 활용해 쉽게 이해 가능.
- 비트마스크를 활용하면 간결한 코드 작성 가능.
- 문제를 재귀적으로 작은 부분 문제로 나누어 해결 후 이를 합침.
- DP접근법(TopDown)의 차이점: 부분 문제 간 중복이 없음.
- 예) 사분면 문제에서
size = 2^d를 활용해 사분면 판별 가능.
-
DP알고리즘의 핵심은 중복되는 부분 문제를 저장하여 효율적으로 해결.
-
점화식 기반 문제: 이전 상태에서 현재 상태를 유도.
- 예) 배낭 문제.(최소/최대 비용만 구하려면 완전 탐색으로 풀어도 됨.)
-
탐색 기반 문제: 중복되는 부분 상태를 저장.
- 예) 외판원 순회 문제, 내리막길 문제.
-
접근 방식:
- Top-Down: 재귀와 메모이제이션.
- Bottom-Up: 반복문으로 점진적 해결.
- 스택 활용: 특정 문자열을 찾아 삭제하는 문제에 유용.
- KMP 알고리즘:
- 문자열 매칭 시 불일치가 발생하면, 어느 패턴 문자열의 인덱스에서부터 다시 비교를 시작해야 하는지를 결정하는 것.
- Trie 자료구조: 문자열 검색과 관련된 문제에서 자주 사용.
- Aho-Corasick: KMP와 Trie를 결합해 다중 문자열 검색에 활용.
- Suffix Array:
- 문자열의 모든 접미사를 정렬하여 배열로 관리.
- 코사이 알고리즘으로 LCP(최장 공통 접두사) 계산.
- Prefix 더블링,접두사를 기반으로 문자열 정렬에 활용되며, Suffix Array 구현 시 자주 사용됨
-
위상 정렬:
- kahn알고리즘: 진입 차수(In-Degree)를 기준으로 순서를 결정.(시작점을 찾는다)
- dfs: 후위 순회(Post-Order Traversal)의 역순을 활용하는 방식.
-
SCC(강한 연결 요소):
- 타잔 알고리즘을 활용해 강한 연결 요소를 구성.
- 타잔 알고리즘에서는, 현재 방문한 정점이 그 그래프(서브 그래프 또는 전체 그래프) 내에서 도달할 수 있는 가장 작은 부모 정점일 때, SCC를 구성.
- sccId(scc를 구성하는 순서)는 값이 클수록 위상이 빠르다. (scc 내에서는 id값이 작을수록/방문한 순서대로 위상이 빠르다.)
- 2-SAT 문제 해결에도 활용.
-
LCA(최소 공통 조상):
- DP를 통해 각 노드의 조상 관계(희소 배열)를 미리 저장.
- 공통 조상을 효율적으로 탐색.
-
단절점/단절선:
- (DFS)단절점을 구하는 것과 단절선을 구하는 것의 차이는 현재 방문한 정점의 순위가 해당 정점과 연결된 부분 그래프의 최소 순위보다 작거나 같으면 단절점이고, 작다면 단절선이다. 단, 단절점의 경우 시작 정점(root)는 예외로 차수로 판단 가능.
-
최단 거리:
- 다익스트라: 가중치 비음수.
- 벨만-포드: 음수 가중치 가능.
- 플로이드-워셜: 모든 정점 쌍 간의 최단 거리 계산.
[참고-https://jaeun-choi98.github.io/2023/10/05/data_structure(4)]
-
MST (최소 신장 트리):
- 프림 알고리즘: 우선순위 큐(Heap) 활용.
- 크루스칼 알고리즘: Union-Find로 구현.
-
이분 매칭:
- DFS를 통해 매칭 확장.
- 현재 정점(u)에서 연결된 정점(v)을 탐색하고, 만약 이미 v와 매칭된 정점(u')이 있다면 u'가 다시 다른 정점과 매칭될 수 있는지 탐색 후 가능하다면 현재 정점(u)를 포함시키고 더 큰 매칭을 만듬. 그리고 만약 u'가 존재하지 않는다면 그냥 추가.
-
Max Flow/Min Cut:
- 최대 유량 = 최소 컷.
- 유량의 대칭성 flow(u->v) = -flow(v->u) 관계를 이용함. 여유 유량 cap(u->v) - flow(u->v) > 0 이라면, 해당 간선을 따라 흐를 수 있는 경로로 모든 노드를 방문하여 증가 경로를 구함. 찾을 수 있는 최대 증가 경로 수를 구하고 그 값을 합하면 최대 유량.
- CCW (Counter Clock Wise):
- 세 점의 방향(반시계, 시계, 일직선) 판별.
- 컨벡스 홀 (Convex Hull):
- 점들의 집합에서 모든 점을 포함하는 최소 볼록 다각형 생성
- 기준점을 기준으로 점들을 반시계 방향으로 정렬 후, 정렬된 점들을 탐색하면서 볼록(시계 방향)인지 검사
- 세그먼트 트리:
- 구간 연산을 효율적으로 처리.
- 리프 노드에 데이터를 저장하고, 조상 노드에 연산 결과를 저장.
- 누적합:
- 구간 합 계산을 최적화.
- 데이터 수정 자주 생기는 경우 세그먼트 트리를 활용.
- 희소배열:
- 유니온-파인드:
- 서로소 집합 관리 알고리즘.
- MST(최소 신장 트리) 구현 시 사용 (예: 크루스칼 알고리즘).