백트래킹(Backtracking) 비선형으로 구성된 자료구조의 모든 경우의 수를 전부 고려하여 해를 찾는 도중 막히면 되돌아가서 해를 찾는 기법 최적화 문제와 결정 문제를 푸는 방법 가지치기(Prunning)를 통해 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 이동하며 가지치기를 얼마나 잘하는지에 따라 효율성이 결정됨 DFS https://pasongsong.tistory.com/240 [알고리즘] 너비 우선 탐색 BFS Breadth First Search BFS 너비 우선 탐색 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 DFS는 깊이 우선 탐색으로 정점의 자식들을 먼저 탐색하는 방식 BFS 방식 : A -> B -> C -> D -> G -> H -> I -> E -> F -> J 한 단..
신장 트리(Spanning Tree) 신장 트리란 아래의 조건을 만족하면서 모든 노드가 연결되어 있는 Tree 구조를 말함 모든 노트가 서로 연결되어 있어야 한다. 사이클이 존재하지 않아야 한다.(Tree의 속성) 왼쪽이 Original graph이고 오른쪽이 Original graph에서 나올 수 있는 신장 트리이다. 최소 신장 트리(MST) Minimum Spanning Tree(MST)라고도 불리며 Spanning Tree의 간선 가중치 값이 최소인 Tree를 말함 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal's algorithm (크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) 크루스칼 알..
최단 경로 최단 경로 문제는 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 및 단일 도착 (single-source and single-destimation shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 V에 도착하는 가장 짧은 결로를 찾는 문제 단일 출발 (single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 전체 쌍 (all-pair) 최단 경로 그래프 내의 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는..
탐욕법 Greedy 최적의 해에 가까운 값을 구하기 위해 사용함 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행하여 최종적인 값을 구하는 방식 최적의 값이라고 단언할 수는 없음 예시 문제 동전 문제 지불해야하는 값이 4750원 일 때 10원 50원 100원 500원 동전으로 동전의 수가 가장 적게하여 지불하시오. 풀이 금액이 큰 동전을 최대한으로 지불해야함 탐욕법을 통해 매순간 최적의 동전 수를 구함 coin = [500, 100, 50, 10] def min_coin_cnt(value, coin): total_coin_cnt = 0 details = list() coin.sort(reverse = True) for co in coin: co_num = ..
DFS 깊이 우선 탐색 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 Node들의 자식을 타고 내려가며 순회함 DFS 방식 : A -> B -> D -> E -> F ->C -> G -> H -> I -> J 구현 코드 # 그래프 생성하기 graph = dict() graph['A'] = ["B", "C"] graph['B'] = ["A", "D"] graph['C'] = ["A", "G", "H", "I"] graph['D'] = ["B", "E", "F"] graph["E"] = ["D"] graph["F"] = ["D"] graph["G"] = ["C"] graph["H"] = ["C"] graph["I"] = ["C", "J"] graph["J"] = ["I"] def bfs(gr..
BFS 너비 우선 탐색 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 DFS는 깊이 우선 탐색으로 정점의 자식들을 먼저 탐색하는 방식 BFS 방식 : A -> B -> C -> D -> G -> H -> I -> E -> F -> J 한 단계식 내려하면서 같은 level의 노드를 순회함 구현 코드 graph = dict() graph['A'] = ["B", "C"] graph['B'] = ["A", "D"] graph['C'] = ["A", "G", "H", "I"] graph['D'] = ["B", "E", "F"] graph["E"] = ["D"] graph["F"] = ["D"] graph["G"] = ["C"] graph["H"] = ["C"] graph["I"] = ["C", "J"] ..
그래프 Graph 그래프는 실제 세계의 현상이나 사물을 정점(Vertex)또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용 집에서 학교가기 용어 노드(Node): 위치를 말함, 정점(Vertex)라고도 함 간선(Eage): 위치 간의 관계를 표시한 선으로 노드를 연결한 선임 (link, branch라고도 불림) 인접 정점(Adgjcent Vertex): 간선으로 직접 연결된 정점(또는 노드) 참고 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이(Path Length): 경로를 구성하기 위해 사용된 간선의 수..
병합 정렬 (합병 정렬) merge sort 동적 프로그래밍과 달리 memorization 방법은 쓰지 않고 재귀용법을 씀 분할정복 알고리즘을 사용한 정렬 알고리즘 중 하나임 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눈다. ( 리스트를 자르는 함수) 각 부분 리스트를 재귀적 합병 정렬을 이용하여 정렬한다. 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다. https://visualgo.net/en/sorting Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science community on earth. If you..
