개발-로그 개발-로그

print("크루스칼 구현") kruskal(mygraph) 지난번에는 다익스트라 알고리즘(Dijkstra algorithm)에 대해 알아보았습니다. 이번에는 크루스칼 알고리즘(Kruskal's algorithm)에 대해 알아보겠습니다. *해당 자료는 패스트캠퍼스 올인원 패키지 강의자료를 참고하였습니다.* 최소신장트리(Minimum Spanning Tree)의 조건 MST라고 불리는 최소신장트리의 조건 1.싸이클이 존재하지 않아야한다.(트리의 속성) 2.모든 노드가 서로 연결되어있어야한다. 3.간선의 가중치 합이 최소값이어야 한다. 조건 1,2번 조건 3번 대표적인 최소신장트리 알고리즘 🖍크루스칼 알고리즘(Kruskal's algorithm) 🖍프림 알고리즘(Prim's algorithm) 먼저 최소상신..

지난번에는 탐욕 알고리즘(Greedy algorithm)에 대해 알아보았습니다. 이번에는 다익스트라 알고리즘(Dijkstra algorithm)에 대해 알아보겠습니다. 다익스트라 알고리즘(Dijkstra algorithm) 다익스트라 알고리즘이란 최단 경로 문제의 일부이며, 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 알고리즘이다. 다익스트라 알고리즘(Dijkstra algorithm)의 접근법 heaq 라이브러를 이용해 우선순위 큐를 생성하고, 우선순위 큐에 저장되어있는 정점(첫 정점)을 추출하여, 추출 된 정점과 해당 정점에서 각 인접노드로 향하는 정점까지의 거리를 비교한다. 이때 각 인접노드는 배열에 저장되어있고, 각 인접노드로 가는 거리가 배열에 저장 (첫정점 =0, 이외정..

지난번에는 깊이 우선 탐색(Depth-First Search)에 대해 알아보았습니다. 이번에는 탐욕 알고리즘(Greedy algorithm)에 대해 알아보겠습니다. 탐욕 알고리즘(Greedy algorithm) 탐욕 알고리즘이란 최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘이다. 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라 생각되는 경우를 선택하는 방식으로 최종값을 구한다. 탐욕 알고리즘(Greedy algorithm)의 예 문제 : 동전 문제 ●지불해야 하는 값이 5872원 일 때 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불해라. 접근법: 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 접근 coin_list = [1, 100, 50, 50..

지난번에는 너비 우선 탐색(Depth-First Search)에 대해 알아보았습니다. 이번에는 깊이 우선 탐색(Depth-First Search)에 대해 알아보겠습니다. 깊이 우선 탐색(Depth-First Search) DPS(깊이우선탐색)이란 정점들의 자식들(자식노드들)을 먼저 탐색해 나가는 그래프 탐색 알고리즘이다. 깊이 우선 탐색(Depth-First Search)의 접근법 파이썬에서 제공하는 key와 value를 묶어놓은 dictionary 이용해서 그래프를 표현하고, Queue(visited_queue), Stack(need_visit_queue) pop(), extend()메서드를 이용해서 나타낸다. 패턴 분석 ●dictionary에 저장 할 키값(key)은 키값에 대한 인접노드(values..

지난번에는 순차 탐색(Sequential Search)에 대해 알아보았습니다. 이번에는 너비 우선 탐색(Breadth-First Search)에 대해 알아보겠습니다. 너비 우선 탐색(Breadth-First Search) BFS(너비우선탐색)이란 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색해 나가는 그래프 탐색 알고리즘이다. 너비 우선 탐색(Breadth-First Search)의 접근법 파이썬에서 제공하는 key와 value를 묶어놓은 dictionary 이용해서 그래프를 표현하고, Queue(visited_queue, need_visit_queue) 2개와 pop(0), extend()메서드를 이용해서 나타낸다. 패턴 분석 ●dictionary에 저장 할 키값(key)은 키값에 대한 ..

지난번에는 이진 탐색Binary Search)에 대해 알아보았습니다. 이번에는 순차 탐색(Sequential Search)에 대해 알아보겠습니다. 순차 탐색(Sequential Search) 순차 탐색은 데이터리스트를 앞에서부터 순서대로 하나씩 비교해가며 원하는 데이터를 탐색하는 비교적 간단한 탐색 알고리즘이다. 순차 탐색(Sequential Search)의 접근법 탐색 할 데이터리스트의 맨 앞 인덱스부터 차례대로 비교해서 탐색 할 데이터를 찾아낸다. 패턴 분석 데이터 리스트는 86, 53, 9, 17, 28, 33, 24, 91이다. 탐색 할 데이터 : 33 // search_data=33 ●맨앞 데이터부터 차례대로 탐색 할 데이터인지 확인한다. ↓ 86 53 9 17 28 33 24 91 ↓ 86 5..

지난번에는 병합 정렬(Merge Sort)에 대해 알아보았습니다. 이번에는 이진 탐색Binary Search)에 대해 알아보겠습니다. 이진 탐색(Binaray Search) 이진 탐색은 데이터리스트가 기본적으로 정렬이 되어 있을 때 탐색 할 데이터리스트를 재귀용법을 이용해 둘로 나누어 데이터가 있을만한 곳을 탐색해나가는 탐색 알고리즘이다. 이진 탐색(Binaray Search)의 접근법 탐색 할 데이터리스트의 medium(중간 값)을 설정 후 medium보다 작으면 medium 이전값까지 재 탐색 medium보다 크면 medium 이후값 재 탐색 패턴 분석 정렬 된 데이터 리스트는 10, 11, 18, 36, 42, 68, 71, 95이다. (Medium = int(len(data) //2) ) 탐색 할..

지난번에는 퀵 정렬(Quick sort)에 대해 알아보았습니다. 이번에는 병합 정렬(Merge sort)에 대해 알아보겠습니다. 병합 정렬(Merge sort) 병합정렬은 데이터리스트를 절반으로 잘라 왼쪽(left)리스트, 오른쪽(right)리스트 로 나누고, 각 왼쪽(left) 오른쪽(right)리스트를 재귀용법 이용해 최종적으로 데이터 를 쪼갠 후 이를 합병 정렬을 이용해 다시 하나의 리스트로 정렬하는 알고리즘이다. 병합 정렬(Merge sort)의 접근법 하나의 데이터리스트를 각 왼쪽(left)리스트, 오른쪽(right)리스트는 재귀용법을 이용해 동일 함수를 호출하여 쪼갠 후 이를 하나의 데이터리스트로 다시 합병한다. 패턴 분석 데이터 리스트는 19, 49, 27, 11, 18, 40, 34, 22..