(해당 정리는 바킹독님, 동빈나님의 강의를 참조합니다)
바킹독 : https://www.youtube.com/channel/UCwFszkz9NbnQyQn5YbDfZtg
동빈나 : https://www.youtube.com/watch?v=94RC-DsGMLo
동적프로그래밍(DP)
이 지나치게 많은 일을 하는 것에서 착안된 알고리즘
-->DP를 보완하는 알고리즘
이다.
- 당장 눈 앞에 보이는
최적의 상황만을 쫓는 알고리즘
부분에서의 최적의 해
가전체적인 최적의 해
가 되는 경우!- 무조건 큰 경우대로 / 작은 경우대로 처럼 극단적으로 문제에 접근한다
-->정렬(sort)기법과 함께 사용되는 경우가 많다
ex) 거스름돈 주기 : 무조건 큰 화폐부터 거슬러 주면 된다 ! (최적의 해)
특정 조건
을 만족하는모든 경우의 수
에 대해 수행하는 알고리즘- 해를 찾는 도중 해가 아니어서 막히면,
되돌아가서 다시 해를 찾아가는 기법
브루트포스(완전탐색)
과유사
하지만,특정 조건을 만족하는 경우의 수
를 수행한다는 차이점이 있음- 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아 간다
--> 이것을가지치기
한다고 한다
- 주된 사용
:DFS
등으로 모든 경우의 수를 탐색하는 과정에서,
조건문 등을 걸어서 답이 절대로 될 수 없는 상황을 정의하여
그러한 상황에서 탐색을 중지시킨 뒤 돌아가서 다른 경우를 탐색하게 한다.
예시 문제
#include <iostream> #include <vector> #include <algorithm> using namespace std; int N, M; int arr[10]; bool isused[10]; void func(int depth){ if(depth == M){ for(int i=0;i < M;i++) cout << arr[i] << ' '; cout << '\n'; return; }else{ /* 백트래킹 핵심 부분 */ for(int i=1;i<=N;i++) { if(!isused[i]){ arr[depth] = i; isused[i] = true; func(depth+1); isused[i] = false; } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M; func(0); return 0; }
[ Intro ]
그래프
에서정점
끼리최단 경로
를 구하는 방법
하나의 정점 --> 다른 하나의 정점까지 최단경로
하나의 정점 --> 다른 모든 정점까지의 최단경로
:Dijkstra 알고리즘
하나의 목적지로가는 모든 최단 경로
모든 정점끼리의 최단 경로를 구하는 문제
:플로이드 워셜 알고리즘
다익스트라 최단경로 알고리즘
은하나의 정점 --> 다른 모든 정점까지 최단경로
에 해당
[ 로직 ]
- 모든 노드간 이동거리 배열을
INF(큰 값)
으로 초기화출발 노드(정해짐)
를 통해 갈 수 있는경로 갱신
- 갱신된 테이블을 통해
방문하지 않은 노드
중최단거리가 가장 짧은 노드
를 선택- 노드 간 이동거리가 더짧다면
갱신
하며 수행- 다시
방문하지 않은 노드
중최단거리가 가장 짧은 노드
를 선택 후반복!
[ 설명 ]
다익스트라
가 제시안최단경로 알고리즘
현재
를 기준으로방문하지 않는 점
들 중최단거리가 가장 짧은 노드
를 선택하는 알고리즘
-->한 단계
당하나의 노드
에 대한최단 거리
를 확실히 찾는다- 현재 상황에서 최선을 선택한다는 원리로
'그리디 알고리즘'
으로 분류된다간선
이음의 값
을 가지면성립되지 X
단순 값
이 아닌경로
를 찾기 위해서는 추가적인 코드가 필요
구현 방법
에 따라시간복잡도
가 상이하다
배열
로 구현 ->O(N^2)
우선순위 큐
로 구현 ->O(NlogN)
:Heap 자료구조
를 사용하면 노드를 선택하는 과정을O(N)
이 아닌O(logN)
으로 가능
(최대 힙
-> 값이큰 값
이 먼저 나옴
최소 힙
-> 값이작은 값
이 먼저 나옴)
[ 예시 & 코드 ]
priority_queue를 이용한 Dijkstra
#include <iostream> #include <vector> #include <queue> #include <algorithm> #define INF 1e9 // 10억을 의미 using namespace std; vector<pair<int,int>> graph[30001]; // 0인덱스는 사용하지 X int dis[30001]; // 0인덱스는 사용하지 X void dijkstra(int start){ priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, start}); dis[start] = 0; while(!pq.empty()) { int dist = pq.top().first; // 비용 int now = pq.top().second; // 현재 거쳐가는 지점의 인덱스 pq.pop(); if(dis[now] < dist) continue; /* i는 의미 없고 그냥 순회하기 위한 변수 */ for(int i=0;i<graph[now].size();i++) { /* first-> 목적지 , second -> 목적지 까지 필요한 비용 */ int cost = dist + graph[now][i].second; // 비용 계산 if(cost < dis[graph[now][i].first]){ // first에는 목적지가 들어가있고 현재 기록된 값이랑 비교 검사 dis[graph[now][i].first] = cost; // first까지 가는데 들어가는 비용 cost를 갱신하고 pq에 삽입 pq.push({cost, graph[now][i].first}); } } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M, C; int cnt=0, MAX=0; cin >> N >> M >> C; fill(dis, dis+30001, INF); for(int i=0;i<M;i++) { int a,b,c; cin >> a >> b >> c; graph[a].push_back({b,c}); } dijkstra(C); for(int i=1;i<=N;i++) if(dis[i] != INF){ cnt++; MAX = max(MAX, dis[i]); } cout << cnt-1 << ' '<< MAX << '\n'; return 0; }
[ 설명 ]
모든 노드 -> 다른 모든 노드
까지의최단경로 모두 계산
하는 알고리즘다익스트라 알고리즘
과 마찬가지로거쳐가는 노드
를기준
으로 알고리즘을 수행2차원 배열
을 통해모든 노드
간최단거리
를 기록2차원 테이블 배열
을점화식
에 따라갱신
한다는 점에서DP
에 속함
: 점화식에 맞게 배열을 갱신한다
시간복잡도
가 무조건O(N^3)
이기 때문에플로이드 워셜
을 쓰는 문제의입력
은500
을 넘지 않게 주어진다
[ 코드 ]
#include <iostream> #include <vector> #include <queue> #include <algorithm> #define INF 1e9 // 10억을 의미 using namespace std; int graph[501][501]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N,M; cin >> N >> M; /* 최단거리 테이블을 모두 무한으로 초기화 */ for(int i=0;i<501;i++) fill(graph[i], graph[i]+501, INF); /* 자기 자신으로 가는 비용은 0으로 초기화 */ for(int a=1;a<=N;a++) for(int b=1;b<=N;b++) if(a==b) graph[a][b] = 0; for(int k=1;k<=N;k++) { for(int a=1;a<=N;a++) { for(int b=1;b<=N;b++) /* a-> 출발노드, b-> 도착노드 , k-> 경유 노드 */ graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b]); } } /* 수행된 결과를 출력 */ for(int a=1;a<=N;a++) { for(int b=1;b<=N;b++) { if(graph[a][b] == INF) cout << "INF" << ' '; else cout << graph[a][b] << ' '; } cout << '\n'; } return 0; }
3중 for
문을 통해 각 모든 점에 대해기존 경로
vs경유 경로
를 검사해서 작은 경로로 update!구현 난이도
는Dijkstra
보다낮다
[ 설명 ]
정렬된 상태
에서 원소를O(logN)
의 시간복잡도로 찾는탐색
- 주로
파라메트릭 서치
유형 문제 풀이로 많이 사용됨
입력의 크기
가매우 큰 상황
에서일정 조건
으로탐색
을 해야하면이진탐색
을 가장먼저 떠올려야 한다
특정 수
의개수
를 구하는 과정을O(logN)
으로 수행할 수 있음
C++
에서upper_bound
와lower_bound
를 이용해countByRange
를 정의한 후leftValue
와 ```rightValue
에 같은 값을 넣으면특정 수의 개수
를 구할 수 있음
C++ STL
에binary_search()
가 구현되어 있으나 지정 값을 찾는기능에 제한된다/* stl container */ binary_search(arr.begin(), arr.end(), M); /* array */ binary_search(arr, arr+N, M);
[ 코드 - 반복문을 통한 이진탐색 구현 ]
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #define ll long long using namespace std; ll N,M,high; vector<ll> arr(1000002); /* 이진탐색 - O(logN) */ void bs(vector<ll>& arr, ll st, ll en){ ll ans=0; while(st <= en) { ll tot=0; ll mid = (st + en)/2; for(auto a : arr) if(a > mid) tot += a-mid; if(tot < M) en = mid-1; else{ ans = mid; st = mid + 1; } } cout << ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; for(int i=0;i<N;i++) { cin >> arr[i]; high=max(high,arr[i]); } bs(arr,0,high); return 0; }
[ 설명 ]
- 두 집단 사이에서 Max Matching되는 경우를 구하는 것
- 노트북 집단과 사람 집단에서 최대로 연결될 수 있는 경우를 구하는 것
- 핵심
: 내가 선택하려는 노드가 이미 선택되어 있을 때
그것을 선택한 노드에게 다른 노드를 선택할 수 있도록 권장하는 것
[ 예시 코드 ]
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <set> #define ll long long using namespace std; vector<pair<int,int>> v(1010); int work[1010]; bool finish[1010]; int T, N, M; /* 이분 탐색 */ bool DFS(int x){ for(int t=v[x].first;t<=v[x].second;t++) { if(finish[t]) continue; finish[t] = true; if(work[t] == -1 || DFS(work[t])){ work[t] = x; return true; } } return false; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> T; while(T--) { v.clear(); cin >> N >> M; for(int i=0;i<M;i++) { int a, b; cin >> a >> b; v.push_back({a,b}); } /* 연결된 점의 좌표 초기화 */ fill(work, work+1010, -1); int ans=0; /* 모든 점들에 대해 연결 */ for(int i=0;i<M;i++) { /* 정점 방문 여부 초기화 */ fill(finish, finish+1010, false); if(DFS(i)) ans++; } cout << ans << '\n'; } return 0; }
- BOJ 9576
- 신장 트리(
Spanning Tree
)
그래프
에서모든 노드를 포함
하면서사이클이 존재하지 않는
부분 그래프
(모든노드 포함
+사이클 X
)
- 최소 신장 트리 (
MST
=Minimum Spanning Tree
)
최소한의 비용
으로구성
되는신장 트리
최소 신장 트리
를 구하는알고리즘 중 하나
(MST
를 구하는다른 알고리즘
으로프림(Prim) 알고리즘
이 있음 )
Union-Find 알고리즘
이 사용
Union
:두 집합을 합치는 연산
- 최초
모든 노드
는parent
로자기 자신
을 가지고 있다두개의 노드
중더 큰 번호에 해당하는 노드
의부모노드
를작은 노드
로갱신!
Find
:연결된 루트 노드를 찾는 것
(여기서는부모 노드
를 찾는 것)
- 재귀적으로 구현하여 연결된 가장 부모 노드를 찾는다
-->findParent 구현시
부모 테이블 값
을바로 갱신
하면'경로 압축'
이 가능함!
- 크루스칼(
Kruskal
) 알고리즘로직
1)모든 간선
에 대해오름차순 정렬
2)아직 처리하지 않은 간선
중가장 짧은 간선
을선택
3)사이클이 없으면
(부모 노드가 같지 않으면
)현재 MST
에추가
(사이클이 있으면
제외
)
#include <iostream> #include <vector> #include <algorithm> using namespace std; int N,M,ans,max_cost; int parent[100002]; // 1~100000 사용 /* find 연산 */ int findParent(int x){ if(x == parent[x]) return x; return parent[x] = findParent(parent[x]); } /* union 연산 */ void unionParent(int a, int b){ a = findParent(a); b = findParent(b); if(a<b) parent[b] = a; else parent[a] = b; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; vector<pair<int, pair<int,int>>> edges; for(int i=0;i<M;i++) { int a, b, cost; cin >> a >> b >> cost; edges.push_back({cost,{a,b}}); } // parent 초기화 for(int i=1;i<=N;i++) parent[i] = i; // edges 정렬 sort(edges.begin(), edges.end()); for(int i=0;i<edges.size();i++) { int a = edges[i].second.first; int b = edges[i].second.second; int cost = edges[i].first; if(findParent(a) != findParent(b)){ unionParent(a,b); max_cost = max(max_cost, cost); ans += cost; } } cout << ans - max_cost; return 0; }
findParent
find 연산
return parent[x] = findParent(parent[x]);
를 통해서경로 압축
을바로 구현
-->바로 위 부모가 아니라
루트
를 가리킬 수 있도록바로바로 갱신!
findUnion
:union 연산
parent 초기화
edges 정렬
MST 추가
짧은 cost 순서
대로사이클이 형성하지 않으면
현재 MST
에추가