최단 경로 알고리즘 그래프 G = (V, E)가 주어지고 여기서 E는 가중치를 가진 유향 간선들의 집합이다. 임의의 경로는 연속된 간선들로 구성된다. 경로를 구성하는 간선들의 가중치의 합이 해당 경로의 길이가 된다. 다익스트라 알고리즘은 음의 가중치가 없는 경우에 사용이 가능하다. 다익스트라 알고리즘이란? 시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 그리디를 이용한 알고리즘으로 Prim이랑 유사한 방법이라고 보면된다. 구현하기 Dijkstar(s, A, d) s : 시작 정점 A : 인접 행렬 D : 시작 정점에서의 거리 정점의 집합

그래프 G=(V, E)의 신장트리는 정점 집합 V를 그대로 두고 간선을 |V| - 1개만 남겨 트리가 되도록 만든 것이다. 이 중 최소 신장 트리(Minimum Spanning Tree)는 간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 말한다. 최소 신장 트리를 찾는 알고리즘은 두 정점 사이의 최소 비용 경로를 찾는 문제 등에서 활용될 수 있다. Kruskal 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 1.최초, 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 2.가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 시킨다. 사이클이 존재하면 남아 있는 가선 중 그 다음으로 가중치가 낮은 간선을 선택 3.n-1개의 간선이 선택될 때까지 2를 반복한다. Kruskal(..

BFS와 DFS는 그래프에서 모든 정점을 방문해야 할 때 정점을 방문하는 방법이다. BFS(Breadth First Search) 너비우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식이다. 인접한 정점들에 대해 탐색한 후 다시 너비 우선 탐색을 진행하기 때문에 선입선출 형태의 자료구조 큐를 활용 BFS알고리즘을 표현하자면 BFS(v) //탐색 시작 정점 큐 생성 시작 정점 v를 큐에 삽입 정점 v를 방문한 것으로 표시 while(큐가 비어있지 않은 동안) u = R || nc = C || map[nr][nc] < 1) continue; dfs(nr, nc); } } } 위상정렬(Topolo..

부분집합이란? 집합에 포함된 원소들을 순서 없이 선택하는 것. 집합의 원소가 N개일 때, 공집합을 포함한 부분집합의 수는 2^N개 각 원소를 부분집합에 포함시키거나 포함시키지 않는 두가지 경우를 모든 원소에 적용한 경우의 수와 같다. 일단 일반적인 재귀방법으로 부분집합을 작성하는 코드이다. static void generateSubSet(int cnt) { if(cnt == N){ for(int i = 0; i < N; i++) { if(isSelected[i]) {System.out.print(input[i] + "\t");} } return; } isSelected[cnt] = true; generateSubset(cnt + 1); isSelected[cnt] = false; generateSubse..

순열과 조합에서 사용되는 재귀의 개념에 대해 간단히 정리하고 시작하겠다. 재귀란? 어떤 개념이나 문제에 대한 정의를 그 개념이나 문제를 포함하는 작은 개념이나 부분문제로 나타내고 더 이상 작은 개념, 부분문제가 없을 때 재귀의 끝으로 설정하는 것 재귀 함수 작성시 주의 할점 함수에 대한 정의를 명확하게! 함수 수행에 필요한 결정적 요인, 값 설계 재귀 종료조건 따지기 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다. 순열과 조합 순열(Permutation) nPr n개의 숫자 중에서 r개를 뽑는데 순서를 고려하여 나열하는 경우의 수를 뜻한다. 즉 순서와 각 자리의 의미가 있다면 순열, 해당 조건이 의미가 없다면 조합으로 분류한다. 조합에서는 1, 2, 3과 3, 2, 1이 다른 경우의 수로 처리되지..

이진 탐색은 중앙 값을 찾고 찾고자 하는 항목이 왼쪽에 있는지 오른쪽에 있는지 알아내어 탐색 범위를 반씩 줄여나간다. 비교가 이루어 질 때마다 탐색 범위가 급격하게 졸어들기 때문에 정렬된 배열을 탐색할 때는 이진탐색이 빠르다. 데이터의 삽입이나 삭제가 빈번할 경우에는 적합하지 않다. 의사코드 binary_search(list, low, high): middle list[middle]) return list[middle+1]부터 list[high]에서의 탐색; 구현 방법에는 순환 호출과 반복 두가지가 있다. 순환 호출 int binary_search(int key, int low, int high) { int mid; if(low