자료구조 및 알고리즘23 [알고리즘] 자바에서의 백 트래킹(N-Queen 문제) 백 트래킹(BackTracking) - 백트래킹, 또는 퇴각 검색으로 부른다. - 제약조건 만족 문제(Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 : 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack(다시는 이 후보군을 체크하지 않을 것을 표기) 하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법이다. - 실제 구현 시 고려할 수 있는 모든 경우의 수(후보군) 을 상태 공간트리(State Space Tree) 를 통해 표현한다. * 상태 공간 트리 : 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리 * 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 .. 2021. 12. 16. [알고리즘] 자바에서의 최소 신장 트리(프림 알고리즘) 프림 알고리즘(Prim's Algorithm) - 대표적인 최소 신장 트리 알고리즘(크루스칼 알고리즘 보다 다소 복잡하다.) * 프림 알고리즘 - 시작 정점을 선택 한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식이다. * 크루스칼 알고리즘과 프림 알고리즘의 비교 - 둘 다 탐욕 알고리즘을 기초로 하고 있다.(당장 눈 앞의 비용을 선택해서, 결과적으로 최적의 솔루션을 찾는다.) - 크루스칼 알고리즘은 가장 가중치가 작은 간선부터 선택하면서 MST 를 구한다. - 프림 알고리즘은 특정 정점에서 시작하여, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택한다. - 간선으로 연결된 정점들.. 2021. 12. 16. [알고리즘] 자바에서의 최소 신장 트리(크루스칼 알고리즘) 신장 트리란? Spanning Tree, 또는 신장 트리라고 불린다. - 원래 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프이다. * 신장 트리의 조건 - 본래 그래프의 모든 노드를 포함해야 한다. - 모든 노드가 서로 연결되어 있다. - 트리의 속성을 만족시킨다.(사이클이 존재하지 않음) 최소 신장트리 - MST(Minimum Spanning Tree) 라고 불린다. - 가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree 를 지칭한다. * 최소 신장 트리 알고리즘 - 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재한다. - 대표적인 최소 신장 트리 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘 1. 모.. 2021. 12. 15. [알고리즘] 자바에서의 다익스트라 알고리즘(최단 경로 알고리즘) 최단 경로 문제란? 그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 문제이다. - 가중치 그래프 에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다. * 최단 경로 문제의 종류 - 단일 출발 및 단일 도착 최단 경로 문제(single-source and single-destination shortest path problem) : 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제이다. - 단일 출발 최단 경로 문제(single-source shortest path problem) : 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제이다. 예를 들어 A,B,C,D 라는 노드를 가진 그래프에서 .. 2021. 12. 12. 이전 1 2 3 4 ··· 6 다음
