Seung-MinJi

1. 백 트래킹 - 백 트래킹 또는 퇴각 검색으로 부름 - 제약 조건 만족 문제에서 해를 찾기 위한 전략 - 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack하고 바로 다른 후보군으로 넘어가며 결국 최적의 해를 찾는 방법 - 실제 구현시, 고려할 수 있는 모든 경우의 수를 상태공간트리를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색 - Promising: 해당 루트가 조건에 맞는지를 검사하는 기법 - Pruning(가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 방법 즉,..

1. 프림 알고리즘 - 대표적인 최소 신장 트리 알고리즘 - 크루스칼 알고리즘, 프림알고리즘 - 프림 알고리즘 - 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장트리를 확장해 나가는 방식 -크루스칼 알고리즘과 프림 알고리즘 비교 - 둘다, 탐욕 알고리즘을 기초로 하고 있음(당장 눈앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) - 크루스칼 알고리즘은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함 - 프림 알고리즘은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식..

1. 신장 트리란? - spanning Tree, 또는 신장 트리라고 불리움 - 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 - 신장 트리의 조건 - 본래의 그래프의 모든 노드를 포함 - 모든 노드가 서로 연결 - 트리의 속성을 만족시킴(사이클이 존재하지 않음) 2. 최소 신장 트리 - Minimum Spanning Tree, MST라고 불리움 - 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 3. 최소 신장 트리 알고리즘 - 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 - 대표적인 최소 신장 트리 알고리즘 - 크루스칼 알고리즘, 프림 알고리즘 4. 크루스칼 알고리즘 - 모든 정점을 독립적인 집합으로 ..

1. 최단 경로 문제란? - 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임 - 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 및 단일 도착 최단 경로 문제 - 그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로르 찾는 문제 단일 출발 최단 경로 문제 - 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 *A,B,C,D라는 노드를 가진 그래프에서 특정 노드를 A라고 한다면 A외 모든 노드인 B C D 각 노드와 A간에 각각 가장 짧은 경로를 찾는 문제를 의미함 전체 쌍 최단 경로 - 그래프 내의 모든 노드 쌍 (u,v)에 대한 최단 경로를 찾는 문제..

1. 탐욕 알고리즘 이란 - Greedy algorithm 또는 탐욕 알고리즘이라고 불리움 - 최적의 해에 가까운 값을 구하기 위해 사용됨 - 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제1: 동전 문제 - 지불해야 하는 값이 4720원일 떄 1원 50원 100원 500원 동전으로 동전의 수가 가장 적게 지불하시오. - 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 - 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total_coi..

1. BFS와 DFS란? 대표적인 그래프 탐색 알고리즘 - 너비 우선 탐색 : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 - 깊이 우선 탐색 : 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 - BFS 방식: A-B-C-D-G-H-I-E-F-J - 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회함 - DFS 방식: A-B-C-D-E-F-C-G-H-I-J - 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회함 2. 파이썬으로 그래프를 표현하는 방법 - 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음 그래프 예와 파이썬 표현 graph = dict() graph..

1. BFS와 DFS란? 대표적인 그래프 탐색 알고리즘 - 너비 우선 탐색 : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 - 깊이 우선 탐색 : 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 - BFS 방식: A-B-C-D-G-H-I-E-F-J - 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회함 - DFS 방식: A-B-C-D-E-F-C-G-H-I-J - 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회함 2. 파이썬으로 그래프를 표현하는 방법 - 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음 그래프 예와 파이썬 표현 graph = dict() graph..

1. 그래프란? - 그래프는 실제 세계의 현상이나 사물을 정점 또는 노드와 간선로 표현하기 위해 사용 2. 그래프 관련 용어 - 노드 : 위치를 말함 정점이라고도 함 - 간선 : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 - 인접 정점 : 간선으로 직접 연결된 정점 - 참고 용어 - 정점의 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수 - 진출 차수 : 방향 그래프에서 외부로 향하는 간선의 수 - 경로 길이 : 경로를 구성하기 위해 사용된 간선의 수 - 단순 경로 : 처음 정점 끝 정점을 제외하고 중복된 정점이 없는 경로 - 사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우 3. 그래프 종류 무방향 그..