코딩 일지

다익스트라다익스트라 알고리즘(Dijkstra Algorithm)이란, 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산하는 알고리즘이다.해당 정점에서 갈 수 있는 최적의 경로로만 가기 때문에 음수 가중치를 가지는 그래프에서는 사용할 수 없다.#include#include#include#define INF 0xFFFFFFFusing namespace std;int dist[5]={0,};vector > graph[5];void dijkstra(int n){ priority_queue > pq; dist[n]=0; pq.push({0,n}); while(!pq.empty()){ int now = pq.top().second; int cost ..

선형 탐색(Linear Search)선형 탐색은 단순히 순서대로 하나씩 찾는 탐색 기법으로평소 우리가 사용하던 탐색 방법과 같다.예를 들어, 우리가 아래 배열에서 8을 찾으려 한다면,1478111516192123어떻게 할까?단순히 for문으로 index 0부터 index 9까지 탐색하면서 8이 나올 때까지 반복할 것이다.이게 선형 탐색이다.선형 탐색은 O(N)의 시간복잡도를 가진다.이진 탐색(Binary Search)이진 탐색은 데이터를 반씩 쪼개가며 찾는 탐색 기법이다.1478111516192123위와 같은 배열에서 8을 찾으려 한다고 하자,(left : index 0, right : index 9)먼저 mid(= (left+right)/2 )만큼 자른다.1478111516192123index가 mid..

깊이 우선 탐색깊이 우선 탐색(DFS, Depth - First - Search)란, 한 분기를 모두 탐색하고 다음 분기를 탐색하는 방법이다.브루트포스백트래킹주로 이 두 문제를 풀 때 사용한다.재귀함수와 비슷하다.단순 속도로 따지면 BFS보다 느리다.dfs로 탐색하면13 -> 6 -> 11 -> 17 -> 31 -> 7 -> 8 -> 21 -> 19순으로 탐색한다.#include#includeusing namespace std;vector tree[100]; // 각 노드의 인접 리스트를 저장할 벡터 배열int visit[100]={0,}; // 노드 방문 여부를 체크할 배열, 초기값은 0(방문하지 않음)// 깊이 우선 탐색(DFS)을 수행하는 함수void dfs(int n){ if(visit[n..

신장 트리신장 트리(Spanning Tree)란, 그래프의 최소 연결 부분 그래프이다.N개의 정점을 가지는 그래프의 최소 간선 수는 (N-1)개이고, (N-1)개의 간선으로 연결되어 있으면 트리의 형태가 된다.신장 트리는 사이클을 포함해서는 안되며, 모든 정점들이 연결되어 있어야 한다.따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결해야 한다.최소 신장 트리최소 신장 트리(MST, Minimum Spanning Tree)란, 최소 비용의 신장 트리를 선택하는 알고리즘이다.MST의 특징은 다음과 같다.간선의 가중치의 합이 최소여야 한다.n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.사이클이 포함되어선느 안된다.MST를 구현하기 위한 방법으..

유니온 파인드유니온 파인드 (Union-Find)란, 합 집합을 만드는 것이다.즉, A, B, C데이터가 존재할 때, A와 B데이터가 하나의 집단이고, C데이터는 또 다른 집단이다를 나타내기 위해 쓰는 알고리즘이다.즉, 개별로 존재하는 데이터들을 하나의 집단으로 나타낼 때 사용한다.이렇게 1, 3, 7이 묶여있고, 2, 4, 6이 묶여있을 때두 집단을 합쳐야될 때 사용한다.parent1234567value12345671, 3, 7이 묶여있고, 2, 4, 6이 묶여있으므로parent1234567value1212521다음과 같이 값을 바꿔준다.이후 두 집단을 합치기 때문에parent1234567value1111511이렇게 바꿔주면 된다.그러면 1, 2, 3, 4, 6, 7의 값이 모두 1로 동일하기 때문에 ..