Coding Diary

1. 개념 그래프 상에 있는 모든 경로의 최단 경로를 구할 수 있는 알고리즘이다. 즉, 노드 1 2 3 4 5 가 있을 때, 노드 1과 노드 2사이의 최단 경로, 노드 1과 노드 3 사이의 최단 경로....노드 4와 노드 5 사이의 최다 경로를 모두 구할 수 있다. 출발 노드로부터 각 노드까지의 최단 경로를 구하는 다익스트라나 벨만포드 알고리즘과는 살짝 다르다. 2. 특징 모든 노드 간의 최단 경로를 탐색할 수 있다. 음수 가중치 에지가 있어도 수행할 수 있다. 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간 복잡도가 O(V3)이다. V는 노드의 수. 인접 행렬을 이용하면 구현이 간단하다. 3. 원리 동적 계획법의 원리 시작 노드부터 도착 노드까지의 최단 경로는 시작 노드부터 중간 노드까지의 최단..

1. 개념 그래프에서 출발 노드와 다른 노드들 간의 최단 거리를 구하는 알고리즘이다. 즉 노드 1, 2, 3, 4, 5가 있고 출발 노드가 1이라고 했을 때, 1부터 2까지 가는 최단 거리, 1부터 3까지가는 최단거리, 1부터 4까지가는 최단 거리, 1부터 5까지 가는 최단 거리를 구할 수 있는 알고리즘이다. 2. 특징 간선의 가중치가 양수다. 시간 복잡도가 O(에지수log노드수) 이다. 우선순위 큐를 사용하여 시간복잡도를 시간 복잡도를 줄인다 우선순위 큐를 사용하면 현재 위치로부터 최소 비용으로 갈 수 있는 다음 노드를 먼저 탐색하여서 불필요한 경로를 탐색하지 않아도 된다. 즉, 모든 노드를 탐색해보지 않아도 된다. 인접 리스트를 사용하는 것이 간단하다. 3. 원리 인접 리스트를 만든다 최단 거리 배열..

1. 개념 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 이렇게 구한 노드 순서는 해당 순서의 노드가 처리되기 위해서는 그 노드보다 앞에 있는 노드가 처리되어야 함을 의미한다. 즉, 반약 위상 정렬의 결과가 1 2 3 4 5 일 때, 2가 처리되기 위해서는 무조건 1이 처리되어야 하는 것이고, 5가 처리되기 위해서는 무조건 1234가 처리 되어 있어야 하는 것이다. 2. 특징 항상 유일한 값으로 정렬되지 않는다. 시간 복잡도는 O(노드 수 + 에지 수) 이다. 3. 원리 진입 차수를 이용한다 진입 차수는 자기 자신을 가리키는 에지의 개수를 의미한다. 진입 차수가 0이라는 것은 해당 노드는 아무 것에도 의지하지 않는다는 것을 의미한다. 그래서 진입 차수가 0인 것을 먼저 정렬한다. -- 1..

1. 개념 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과, 특정 원소가 속한 집합의 대표 원소를 반환하는 find 연산. 2. 연산 1) union 원소 a가 집합 A에 속해있고, 원소 b가 집합 B에 속해 있을 때 a와 b를 union한다는 것은 A와 B의 합집합을 구하는 것과 같다. 2) find 집합 A에는 다양한 원소들이 있고, 그 중에 a도 있다. find(a)는 a가 속한 집합에 있는 다양한 원소 중 대표 원소를 구하는 연산이다. 3. 원리 1차원 배열을 선언한다. 그 배열의 인덱스는 원소를 의미하고, 인덱스에 있는 값은 해당 원소가 속한 집합을 의미한다. 1) find 1 2 3 4 5 6 1 2 3 4 5 6 find(1)은 1이 속한 집합의 대표 ..

1. 개념 정점(노드)과 간선(에지)으로 이루어진 자료구조. 정점은 고유한 식별자를 가지고 있고, 간선은 정점들끼리의 관계를 나타낸다. 2. 종류 1) 방향 그래프 간선에 방향성이 있는 그래프를 의미한다. A에서 출발해서 B로 가는 간선이 존재한다면 이는 A에서 B로 가는 방향을 가진 간선이고, 이러한 정점과 간선을 모아 놓으면 방향 그래프이다. A에서 B로는 갈 수 있지만, B에서 A로 가는 길은 없다. 2) 무방향 그래프 간선에 방향이 없다. A에서 B가 연결되어 있으면 출발과 도착이 없고 그냥 둘이 연결 된 거다. A에서 B로 갈 수 있고, B에서 A로도 갈 수 있다. 3) 가중치 그래프 A와 B가 연결이 되어 있는데 그 연결된 간선에 가중치가 부여된 것이다. 이러한 가중치는 두 정점 사이의 거리,..

1. 개념 방정식의 해를 구하기 위해 사용하는 알고리즘이다. 2. 원리 ax+by=c(a,b,c,x,y는 정수) 와 같은 방정식이 있을 때, c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다. ax+by=c가 정수해를 갖게 하는 c의 최솟값이 gcd(a,b)이다. 3. 방법 5x + 9y = 2 일때, 이 식을 만족하는 정수 x와 y를 찾아보자. 식이 정수해를 갖게 하는 c의 최솟값이 gcd(5,9)라는 것을 적용하여 식을 다시 놓는다. 5x + 9y = 1 5와 9로 유클리드 호제법을 반복 실행하며 몫과 나머지를 저장한다. 나머지가 0이 되면 반복을 중단한다. 유클리드 호제법 실행 나머지 몫 5%9 5 0 9%5 4 1 5%4 1 1 4%1 0 4 위에서 구한 나머지와 몫을 이용하여 x와 ..

1. 개념 두 수의 최대 공약수를 구하는 알고리즘이다. + 두 수의 곱을 최대 공약수로 나누면 최소공배수도 구할 수 있다. 2. 방법 큰 수를 작은 수로 나누는 MOD 연산을 수행한다. 위의 작은 수와 MOD 연산의 결과로 MOD 연산을 수행한다. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다. MOD연산은 큰 수를 작은 수로 나눈 나머지를 구하는 연산이다. 3. 코드 // 반복문으로 구현 public static int gcd(int num1, int num2){ int small = num1 num2 ? num1 : num2; int temp = 0; while(small != 0){ temp = big % small..

1. 개념 현재 상태에서 문제를 해결할 수 있는 가장 좋은 해를 선택해나가면 최적의 답을 구할 수 있게 되는 알고리즘 2. 과정 1) 해 선택 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다 2) 적절성 검사 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다 3) 해 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다. 3. 특징 시간 복잡도는 O(n)이다. n개를 쭉 살펴보면서 하나를 해라고 선택한 후, 적절성 검사를 하고, 적절하면 해라고 인식, 적절하지 않으면 해라고 인식하지 않는 과정을 n개 동안 진행한다. 앞의 선택(해를 선택하는)이 뒤의 선택에 영향을 미치지 않을 때 사용 가능하다. 문..

1. 개념 정렬되어 있는 데이터에서 원하는 값을 찾을 수 있는 알고리즘. 정렬되어 있는 데이터 중 중앙값을 찾고, 그 중앙값과 내가 찾고자 하는 값을 비교해서 찾고자 하는 값이 더 작으면 중앙에서 왼쪽만 보고, 찾고자 하는 값이 더 크면 중앙에서 오른쪽만 본다. 이렇게 하면 살펴야 하는 데이터의 크기를 절반씩 줄여나갈 수 있다. 2. 예시 데이터: 3 7 13 15 23 35 38 40 찾고자 하는 데이터: 13 맨 처음 중앙값은 15, 찾고자 하는 값이 더 작으니 15보다 왼쪽만 본다. 15보다 왼쪽 중 중앙값은 7, 찾고자 하는 값이 더 크니 7보다 오른쪽만 본다. 7보다 오른쪽 중 중앙값은 13. 찾고자 하는 값을 찾았다. 3. 특징 N개의 데이터에서 logN번의 연산으로 원하는 데이터를 찾을 수 ..

1. 개념 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것을 그래프 순회라고 한다. DFS는 그래프를 순회하는 방법 중 하나이다. DFS는 시작 노드부터 출발해서, 시작 노드와 인접한 것 중 하나를 방문한다. 그리고 그 방문한 것과 인접한 것을 또 방문한다. 이렇듯 시작 노드부터 인접한 것을 따라 계속 그걸 방문해나가는 방법이다. 마치 아래 방향으로 쭉 깊이있게 탐색하는 것 같다. 만약, 더 이상 방문할 것이 없다면 이전 노드로 돌아와서 이전 노드와 인접해 있지만 아직 방문하지 않은 노드를 방문해 나간다. 2. 예시 위와 같은 그래프를 DFS로 방문하면 다음과 같다. 같은 단계일 경우 오름차순으로 노드를 방문한다. 1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> ..