반응형 Algorithm/알고리즘 이론18 Chapter 21. 백트래킹 백 트래킹 기법의 이해 1. 백 트래킹 (backtracking) 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현 각 후보군을 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 .. 2020. 7. 22. Chapter 20-2. 최소 신장트리의 이해 최소 신장 트리의 이해 1. 프림 알고리즘 (Prim's algorithm) 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm 과 Prim's algorithm 비교 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선.. 2020. 7. 22. Chapter 20-1. 최소 신장트리의 이해 최소 신장 트리의 이해 1. 신장 트리 란? Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) 2. 최소 신장 트리 Minimum Spanning Tree, MST 라고 불리움 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 3. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루.. 2020. 7. 22. Chapter 19. 최단경로 알고리즘 이해 최단 경로 알고리즘의 이해 1. 최단 경로 문제란? 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 (single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 따지고 보.. 2020. 7. 22. Chapter 18. 탐욕 알고리즘의 이해 탐욕 알고리즘의 이해 1. 탐욕 알고리즘 이란? Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 최적의 해에 가까운 값을 구하기 위해 사용됨 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제1: 동전 문제 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 coin_list = [1, 100, 50, 500] print (coin_list) coin_list.sort(reverse=Tr.. 2020. 7. 22. Chapter 17-2. 너비우선탐색(BFS) 너비 우선 탐색 (Breadth-First Search) 1. BFS 와 DFS 란? 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 DFS 방식: A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타.. 2020. 7. 22. Chapter 17-1. 깊이우선탐색(DFS) 깊이 우선 탐색 (Depth-First Search) 1. BFS 와 DFS 란? 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 DFS 방식: A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 .. 2020. 7. 22. Chapter 16. 그래프 이해 그래프 이해 1. 그래프 (Graph) 란? 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용 예제 집에서 회사로 가는 경로를 그래프로 표현한 예 2. 그래프 (Graph) 관련 용어 노드 (Node): 위치를 말함, 정점(Vertex)라고도 함 간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함) 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out.. 2020. 7. 22. Chapter 15-2. 이진 탐색 탐색 알고리즘2: 이진 탐색 (Binary Search) 1. 이진 탐색 (Binary Search) 이란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 다음 문제를 먼저 생각해보자 이진 탐색의 이해 (순차 탐색과 비교하며 이해하기) [저작자] by penjee.com 이미지 출처 2. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 하나 또는 둘 이상으로 나눈다. Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진 탐색 Divide: 리스트를 두 개의 서브 리스트로 나눈다. Comquer 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 .. 2020. 7. 22. Chapter 15-1. 순차 탐색 (Sequential Search) 탐색 알고리즘1: 순차 탐색 (Sequential Search) 1. 순차 탐색 (Sequential Search) 이란? 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 프로그래밍 연습 임의 리스트가 다음과 같이 rand_data_list로 있을 때, 원하는 데이터의 위치를 리턴하는 순차탐색 알고리즘 작성해보기 가장 기본적인 방법이므로, 직접 작성해보겠습니다. - 원하는 데이터가 리스트에 없을 경우 -1을 리턴 데이터 준비: data_list 10개 만들기 from random import * rand_data_list = list() for num in range(10): rand_data_list.appe.. 2020. 7. 20. 이전 1 2 다음 728x90 반응형
