IT개발/알고리즘, 우리 친해지자!26 알고리즘 : 최단 경로 최단 경로는? 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 1. 단일 출발 및 단일 도착(single-source and single-destination shortest path problem)최단 경로 문제 - 그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 2. 단일 출발(single-source shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 3. 전체 쌍(all-pair)최단경로 : 그래프 내의 모든 노드.. 2021. 9. 30. 알고리즘 : 탐욕 알고리즘 탐욕 알고리즘은? Greedy algorithm 또는 탐욕 알고리즘 이라고 함 최적의 해에 가까운 값을 구하기 위해 사용 여러 경우 중 하나를 결정해야 할 때마다 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행, 최종값을 구함 탐욕 알고리즘의 예 예시문제1 : 동전 - 지불해야 하는 값이 4830원 일 때 1원, 50원, 100원, 500원 동전으로 동전의 수를 가장 적게 지불하세요. - 가장 큰 동전을 우선으로 최대한 지불해야 하는 값을 채우는 방식으로 구현 - 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택 coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total_coin_count = 0 details = .. 2021. 9. 27. 알고리즘 : 깊이 우선 탐색(Depth-First Search) https://every-time-i-pass-this-place.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89Breadth-First-Search 알고리즘 : 너비 우선 탐색(Breadth-First Search) 너비 우선 탐색 (BFS)은? 너비 우선 탐색(Breath-First Search) : 정점들과 같은 위치에 있는 노드(형제노드)들을 먼저 탐색하는 방식 BFS방식 A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서 해당.. every-time-i-pass-this-place.tistory.com 지난 .. 2021. 9. 23. 알고리즘 : 너비 우선 탐색(Breadth-First Search) 너비 우선 탐색 (BFS)은? 너비 우선 탐색(Breath-First Search) : 정점들과 같은 위치에 있는 노드(형제노드)들을 먼저 탐색하는 방식 BFS방식 A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서 해당노드와 같은 위치에 있는 노드(형제노드)들을 먼저 순회함 파이썬으로 그래프를 표현하는 방법 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음 Key Values A B C B A D C A G H I D B E F E D F D G C H C I C J J I graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['B', 'E', 'F.. 2021. 9. 21. 이전 1 2 3 4 5 6 7 다음
