Algorithm/알고리즘 개념

목차 개념 크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용됩니다. 그래프에는 정점과 간선이 있는데, 간선에 가중치가 포함되어 있습니다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용합니다. 즉, 최소 신장 트리를 구하기 위한 알고리즘 입니다. 신장 트리와 최소 신장 트리 신장 트리(Spannging tree) 다음과 같이 정의합니다. 그래프에서 1) 모든 정점을 포함하고 2) 정점 간 서로 연결되어 있으며 싸이클이 존재하지 않는 그래프 (싸이클이 존재하는 않는 것은 tree 기본 조건) 예를 들어 아래와 같은 그래프가 있다고 가정해 보겠습니다. 여기서 나올 수 있는 신장..

목차 개요 순열 및 조합을 생성할 때 재귀적으로 구현하지 않고 각 인덱스 값을 비교하여 모든 경우의 인덱스 값을 뽑아내는 방법입니다. 현 순열에서 사전 순(오름차순)으로 다음 순열을 생성합니다. 즉 배열을 가장 작은 값으로 정렬한 뒤, 한 자리씩 swap 하면 서 출력합니다. 예시) 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 (가장 큰 값) 장점 재귀로 짜여진 순열과 달리 시간 복잡도가 낮습니다. (재귀적 호출이 없고 인덱스의 값만 교체해주므로) 순열과 조합을 함께 사용할 수 있습니다. 단점 원래의 배열을 재배열하여 순열을 만드므로 nPr 과 같이 특정 개수의 순열을 만들 수 없습니다. 구현 소스 배열을 오름차순으로 정렬합니다. (1, 2, 3...) (모든 탐색은 오른쪽에서 왼쪽으..

목차 개요 대표적인 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다. 상호 배타적 집합(Disjoint - set)이라고도 합니다. 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 입니다. 2가지 연산으로 이루어져 있습니다. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 구현 부모노드를 저장할 배열 생성 int[] parent = new int[10]; for(int i = 0; i < 10; i++) { parent[i] = i; } 구현은 간단한 트리를 통해서 이루어집니다. parent[i] 를 i 노드의 부모 노드 라고 정의하고 초기화합니다. pare..

DP 개요 DP, 다이나믹 프로그래밍은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 문제해결에 패러다임으로 볼 수 있습니다. 큰 문제를 작은 문제로 나누어서 그 답을 저장해두고 재활용한다. 사용이유 DP는 일반적인 재귀(Navie Recursion) 방법과 유사합니다. 하지만 일반적인 재귀를 사용할 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있습니다. 피보나치 수열을 예시로 들겠습니다. 피보나치의 재귀 함수는 아래와 같습니다. return f(n) = f(n-1) + f(n-2) f(n)을 구하기 위해서 f(n-1)에서 한 번 구한 값들을 f(n-2)에서 같은 과정을 반..

위상정렬이란? 방향 그래프에서 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 이다. 위상정렬의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상정렬 과정에서 선택되는 정점의 순서를 위상순서라고 한다. 위상정렬 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상정렬 알고리즘은 중단된다. 위상정렬의 흐름 1. 진입차수가 0인 정점을 선택 2. 선택된 정점과 연결된 간선들을 제거 3. 위의 과정을 반복해 모든 정점이 선택, 삭제되면 알고리즘 종료 위상정렬과 관련된 문제 백준 작업 : https://www.acmicpc.net/problem/2056 게임 개발 : https://www.acmicpc.net/problem/1516 줄 세우기 :..