재원블로그 재원블로그

유니온 파인드는 집합간의 합집합을 나타낼 때 사용하는 자료구조이다. A[] = { 0, 1, 2 }, B[] = { 1, 2, 3 } 이라고 하고, B 배열이 A 배열로 합쳐진다고 가정하면 union 연산을 수행한 후에는 A[] = { 0, 1, 2, 3 } 이 되는 것이다. 유니온 파인드에서는 두 가지의 연산을 수행할 수 있는데, 한 집합의 대표를 리턴하는 find 와 두 집합을 합치는 union 연산이 있다. 초기 상태에는 한 원소가 하나의 집합이 되고, 그 원소가 그 집합의 대표가 된다. C++로 구현한 기본적인 유니온 파인드는 다음과 같다. vector parent; void init(vector p) { for (int i = 0; i < parent.size(); i++) { parent[i]..

위상 정렬은 순서가 정해진 일들에 대해서 그 순서를 위배하지 않고 일들의 처리 순서를 만드는 방법을 만드는 알고리즘이다. 대표적으로 선수 과목을 예로 들 수 있다. C 과목을 들으려면 B를 들어야 하고, B 과목을 들으려면 A 과목을 들어야 한다고 하자. 그러면 수강 순서는 A -> B -> C 가 될 것이다. 이 순서를 만드는 것이 위상 정렬이다. 위상 정렬은 DAG (Directed Acyclic Graph) 에서만 성립한다. 즉, 유향 그래프여야 하며, 사이클이 없어야 한다. 무향 그래프의 경우 A -> B 와 B -> A 가 모두 가능하여 선수 과목이라는 조건에 모순이다. 또한 C를 듣기 위해서 B를 듣고, B를 듣기 위해서는 A를 듣는데, 이 때 A를 듣기 위해서 C를 들어야 한다면 이 또한 모..

이진 탐색은 정렬되어 있는 요소들에게만 사용할 수 있다. 일반적인 순차 탐색으로는 O(N)의 시간이 소요되지만, 이진 탐색을 사용하면 O(log N) 시간이 소요된다. C++로 구현한 기본적인 구현은 다음과 같다. int binarySearch(int key) { int low = 0; int high = MAX - 1; while (low arr[mid]) { low = mid + 1; } else if (key < arr[mid]) { high = mid - 1; } else { return mid; } } return -1; } 이 코드는 key가 정해진 배열에 존재하는지 여부를 판단할 수 있고, 만약 있다면 그 인덱스를 리턴하고, 없다면 -1을 리턴한다. 배열에서 key의 존재 유무를 판단하는 것..

대표적인 최단 경로 알고리즘 중에서 3번째 플로이드 워셜 알고리즘이다. 플로이드 워셜 알고리즘은 다익스트라나 벨만-포드와 다르게 1:N이 아닌 N:N 의 최단 시간을 찾을 수 있다. 최악 시간 복잡도는 O(|V|^3) 이다. 플로이드 워셜 알고리즘은 처음에 간선들의 정보와 자기 자신으로의 경로는 0이라는 정보만 주고, 모든 정점들의 경유를 하나씩 열면서 직접 가는 것보다 경유하는게 더 짧은지를 확인한다. 플로이드 워셜은 음수 사이클이 없는 그래프에서 음수 가중치가 있어도 사용할 수 있다. C++로 구현한 코드는 다음과 같다. #define INF 1000000000 int n; vector edges; vector floyd_warshall() { vector dist(n + 1, vector(n + 1..

최단 경로를 구하는 두번째 알고리즘 벨만 포드 알고리즘이다. 이 알고리즘은 다익스트라와 마찬가지로 하나의 시작점에서 다른 정점들간의 최소 시간을 구하는 알고리즘이다. 최악 시간 복잡도는 O(|V||E|)이다. 여기서 |V|는 정점의 개수, |E|는 간선의 개수이다. 다익스트라는 최악 시간 복잡도가 O(|E| + |V| log|V|) 인데 이 알고리즘을 사용하는 이유는 음수 가중치에 대해서도 적용할 수 있기 때문이다. 또한 음수 사이클의 존재 유무까지 판단할 수 있다. 이 알고리즘은 다익스트라와 같이 BFS 기반의 연산을 하는 것이 아닌 플로이드 워셜 알고리즘같이 다중 반복을 통해 문제를 해결한다. 그래서 우선순위 큐를 사용하지 않는다. 이 알고리즘은 초기에 start의 dist가 0이라는 것 빼고 모든 ..

가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘에는 대표적으로 다익스트라, 벨만-포드, 플로이드-워셜이 있다. 그 중 다익스트라에 대해서 정리하는 글이다. 다익스트라 알고리즘은 우선순위 큐를 이용할 경우 O(E + VlogV)로 알려져 있다. 여기서 E는 간선의 개수이고, V는 정점의 개수이다. 이 알고리즘은 무향, 유향 상관없이 적용 가능하지만, 음의 가중치가 있으면 사용할 수 없다. 다익스트라 알고리즘은 하나의 시작 정점에서 다른 정점들과의 최단 시간을 알아낼 때, 즉 1 : N일 때 사용할 수 있다. 다익스트라 알고리즘을 C++로 구현한 코드는 다음과 같다. #define INF 1000000000 int v; vector edges; vector dijkstra(int start) { vect..

1월 - 17 ~ 18일 부산 여행 2월 - 3 ~ 4일 천안 카라반 여행 3월 - 3학년 1학기 시작 4월 - 7 ~ 8일 대부도 카라반 여행 6월 - 3학년 1학기 종강 : 성적 3.83 / 4 (전체 / 전공) - 30 ~ 7.1 연남동 에어비앤비 8월 - 1 ~ 2일 가평 카라반 여행 9월 - 3학년 2학기 시작 - 네터스 가입 - 일일백준 시작 - 16 ~ 23일 코로나 11월 - 일일백준 종료 : 최다풀이상 12월 - 3학년 2학기 종료 : 4 / 4.25 (전체 / 전공) - 22 ~ 23일 명동 여행 - 26 ~ 28일 친할머니 장례식 2022년에는 여행과 추억을 많이 쌓지 못했고 성적도 아쉽고 활동도 많이 하지 못했다. 하지만 네터스에서 주관하는 활동들을 거의 다 참여하면서 내가 하는 만..

디자인 패턴(Design Pattern)이란 소프트웨어 공학의 소프트웨어 디자인에서 특정 문맥에서 공통적으로 발생하는 문제에 대해 재사용 가능한 해결책이다. 디자인 패턴을 사용해야 하는 이유 유연성 - 코드를 유연하게 만들어준다. 재사용성 - 코드를 재사용할 수 있게 한다. 공유 용어 - 공유 용어를 사용하면서 다른 사람의 코드를 더 쉽게 이해할 수 있다. 베스트 프랙티스 - 비숙련자도 소프트웨어 디자인을 배울 수 있다. 객체지향 프로그래밍에서의 디자인 패턴에 대해 알아볼 것이다. 카테고리 Creational patterns : 객체 인스턴스화 과정에서 사용하는 패턴이다. Abstract Factory Builder Factory Method Prototype Singleton Structural pat..