algorithm

[알고리즘] 플로이드-워샬 알고리즘

플로이드-워샬 알고리즘 모든 쌍 최단 경로 알고리즘: 모든 정점 쌍 사이의 최단 경로를 구하는 방법 단순 최단 경로 알고리즘 m개의 간선을 사용해서 i에서 j까지 이르는 최단거리 모든 정점 k에 대해 최대 m-1개의 간선을 사용해서 i에서 k까지 이르는 최단거리 $d_{ik}^{m-1}$에다가 $w_{kj}$를 더한 값을 구하고, 이 중 가장 짧은 것을 택함 for (i=1 to n) for (j=1 to n) d(i to j, k=0) = w[i][j]; for (m=2 to n-1) for (i=1 to n) for (j=1 to n) d(i to j, k=m) = min(d(i to k, k=m-1) + w[k][j]) 시간 복잡도: $\theta(n^4)$ 플로이드-워샬 $d_{ij}^{k}$ =..

[알고리즘] 위상 정렬 Topological Sort (자바 Java)

위상 정렬 사이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬 간선 (i, j)가 존재하면 정점 i는 반드시 j보다 앞에 위치 방식 1: 큐 활용 topologicalSort(G, V) { for i

[알고리즘] 유니온-파인드 (Union-Find) (자바 Java)

목차 유니온 파인드 (Union-Find) 서로소 집합(Disjoint-sets) 서로 중복 포함된 원소가 없는 집합들 → 교집합이 없다 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분, 이를 대표자(representative)라고 함 연산 Make-Set(x): 원소 x로만 구성된 집합을 만든다 Find-Set(x): 원소 x를 가진 집합을 알아낸다 Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다 표현 방법 연결 리스트, 트리 1. 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표원소로 삼음 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 2. 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모노드를 ..

[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra), 벨만-포드 (Bellman-Ford) (자바/Java)

목차 최단 경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라 (dijkstra): 음의 가중치 허용x 벨만-포드(Bellman-Ford) : 음의 가중치 허용o 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 1. Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 탐욕 기법을 사용 - 프림 알고리즘과 유사 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재 이때 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지으 ㅣ최단 경로로 구성됨 s→t = s→x + x→t 시간복잡도 : O(ElogV) 과..

[알고리즘] 비트 연산자 & 부분집합 (자바/Java)

비트 연산자 &둘 다 1 이면 1 / 해당 비트가 있는지 검사! System.out.println(3 & 5); // 3 = 011 // 5 = 101 // -------- // 001 -> 1 | 하나라도 1이면 1 System.out.println(3 | 5); // 3 = 011 // 5 = 101 // -------- // 111 -> 7 ^ XOR - 서로 다르면 1 System.out.println(3 ^ 5); // 3 = 011 // 5 = 101 // -------- // 110 -> 6 A >1); // 5 / (2^1) = 2 // 101 -> 010 = 2 부분집합 N개의 원소를 가진 집합에서 전체 부분집합의 개수 = 2^N 1. 재귀 부분집합은 공집합부터 원소가 1개, 2개, … ..

[알고리즘] 정렬 - 버블 정렬(Bubble Sort) (자바/Java)

목차 버블 정렬 개념 인접한 두 개의 원소를 비교하며 정렬하는 알고리즘 정렬 과정 배열이 {30, 15, 2, 8, 21, 7}일 때를 가정한다. 원소는 자신의 오른쪽 값과 비교하기 때문에, 첫 사이클에서 비교할 마지막 index는 n-2이다. n-1(마지막 원소)와 비교를 하면 한 사이클이 끝나기 때문이다. 그렇게 한 사이클이 지나면 가장 큰 값이 배열의 오른쪽에 위치하여 다음 사이클에서는 비교 대상에서 제외된다. 두 번째는 30을 제외하고 다섯개의 원소만 비교하며 같은 과정을 반복한다. 이 사이클이 끝나면 두 번째로 큰 원소인 21이 자신의 위치를 찾아간다. 이렇게 반복하다보면 i가 1일때, 두 번째로 작은 원소인 7이 정렬되고, 자동으로 가장 작은 원소인 2는 비교 대상이 없기 때문에 모든 정렬이 ..