[알고리즘/JAVA] 위상 정렬(Topological Sorting)

위상 정렬이란?순서가 있는 작업을 차례로 진행해야 할 때 순서를 결정해 주기 위해 사용하는 알고리즘사이클이 없는 방향 그래프(DAG)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것DAG (Directed Acyclic Graph) : 유향 비사이클 그래프 동작과정간선에 대한 정보를 저장하면서 정점들의 진입 차수(특정 노드로 들어오는 간선의 개수)를 기록한다.진입 차수가 0 인 모든 노드를 Queue 에 삽입한다.Queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 확인해 연결 된 노드의 진입 차수를 감소 시킨다.새롭게 진입 차수가 0 이 된 노드를 Queue 에 삽입한다.Queue가 공백상태가 될 때까지 3,4 반복 수행한다. 위상 정렬 구현예시문제https://www.acmicpc...

• format_list_bulleted 알고리즘, 자료구조/이론
• · 2023. 5. 13.
• textsms

[알고리즘/JAVA] 최단 경로 - 다익스트라, 플로이드 워셜

최단 경로란?간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로대표적인 방법하나의 시작 정점에서 끝 정점까지의 최단 경로- 다익스트라(Dijkstra) 알고리즘(음의 가중치 불가)- 벨만 포드 (Bellman Ford) 알고리즘(음의 가중치 허용)모든 정점들에 대한 최단 경로- 플로이드 워샬(Floyd Warshall) 알고리즘 다익스트라 알고리즘  특징시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.탐욕 기법을 사용한 알고리즘으로 MST 의 프림 알고리즘과 유사하다.음의 가중치를 가진 경우는 사용 불가하다. 동작과정시작 정점을 입력 받는다.거리를 저장할 D 배열을 무한대로 초기화 한 후 시작점의 값은 0으로 바꿔 놓는다.아직 방..

• format_list_bulleted 알고리즘, 자료구조/이론
• · 2023. 5. 7.
• textsms

[알고리즘/JAVA] 최소 비용 신장 트리(MST) - 크루스칼, 프림

최소 비용 신장 트리란?신장 트리(스패닝 트리) : 그래프 내의 모든 정점을 포함하는 트리 최소 비용 신장트리 : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리특징 무방향 가중치 그래프그래프의 가중치의 합이 최소N개의 정점을 가지는 그래프에 대해 반드시 (N-1) 개의 간선을 사용해야 한다.사이클을 포함x대표적인 방법Kruskal(크루스칼)Prim(프림) 크루스칼 알고리즘가장 작은 가중치를 가진 간선을 차례대로 하나씩 선택해서 MST를 찾는 알고리즘모든 간선을 가중치에 따라 오름차순으로 정렬가중치가 가장 낮은 간선부터 선택하면서 트리를 연결  - 사이클이 존재한다면 선택xV-1개의 간선이 선택될 때 까지 (2)반복사이클이 존재하는지는 어떻게 찾을까? 유니온 파인드 이용 https://dong..

• format_list_bulleted 알고리즘, 자료구조/이론
• · 2023. 5. 1.
• textsms

[알고리즘/JAVA] 그래프

그래프란?정점(Vertex)들의 집합과 이들을 연결하는 간선 (Edge)들의 집합으로 구성된 자료구조 그래프의 종류무향 그래프(Undirected Graph)유향 그래프(Directed Graph)순환 그래프(Cycle graph)가중치 그래프(Weighted Graph)사이클 없는 방향 그래프(DAG, Directed Acyclic Graph) 그래프 저장 방법간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정1. 인접 행렬2. 인접 리스트인접 행렬(Adjacent matrix)|V| x |V| 크기의 2차원 배열을 이용해서 간선 정보를 저장(V: 정점의 수) 배열의 배열인접 리스트(Adjacent List)각 정점마다 해당 정점으로 나가는 간선의 정보를 저장 인접 행렬인접 리스트A와 B를 잇..

• format_list_bulleted 알고리즘, 자료구조/이론
• · 2023. 4. 17.
• textsms

[알고리즘/JAVA] 트리

트리란?비선형 구조 원소들 간에 1 : N 관계를 가지는 자료구조원소들 간에 계층관계를 가지는 계층형 자료구조(사이클 x)상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조 트리의 조건1. 부모 : 자식 = 1 : N2. 하나의 자식은 둘 이상의 부모X3. 노드의 개수가 N개 → 간선의 개수 N-1개4. 원소가 하나이거나 비어있어도 트리 O5. 싸이클 X 트리 용어 정리노드(node) - 트리의 원소 간선(edge) - 노드를 연결하는 선 , 부모 노드와 자식 노드를 연결 루트 노드 (root node) - 트리의 시작 노드리프 노드 (leaf node) - 자식이 없는 노드경로(path) - 간선들로 연결된 노드를 순서대로 나열한 것 거리 : 간선의 수 형제 노드(sibling nod..

• format_list_bulleted 알고리즘, 자료구조/이론
• · 2023. 4. 12.
• textsms

[알고리즘/JAVA] 완전탐색 - 백트래킹

완전 탐색이란?모든 경우의 수를 시도해 보는 방법반드시 답을 찾을 수 있지만 전부 탐색하기에 시간 복잡도가 일반적으로 높다.완전탐색 기법 종류Brute ForceBFS/DFS백트래킹(Backtracking)비트마스크(Bitmask)  백트래킹여러 가지 선택지(옵션)들이 존재하는 상황에서 한가지를 선택한다. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다. 이런 선택을 반복하면서 최종 상태에 도달한다. - 올바른 선택을 계속하면 목표 상태(goal state)에 도달한다.백트래킹 기법 ▪ 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 감. ▪ 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 ..

• format_list_bulleted 알고리즘, 자료구조/이론
• · 2023. 4. 8.
• textsms