신장트리 원래의 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프 Spanning Tree로 불리기도 한다. 신장 트리의 조건 본래의 그래프의 모든 노드를 포함 모든 노드가 서로 연결 트리의 속성을 만족 (사이클이 존재X) 최소 신장 트리 가능한 신장 트리중에 간선의 가중치 합이 최소인 신장 트리 Minimum Spanning Tree : MST 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾는 알고리즘 크루스칼 알고리즘, 프림 알고리즘이 존재 크루스칼 알고리즘 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용을 기준으로 정렬, 작은 간선 부터 양 끝의 두 정점을 비교 두 정점의 최상위 정점을 확인, 다를 경우 연결 (사이클이 생기지 않도록) Union- find 크..

최단 경로 알고리즘 두 노드를 잇는 가장 짧은 경로 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 경로를 찾는다. 최단 경로 문제 종류 단일 출발 및 단일 도착 - 특정노드에서, 또다른 특정노드의 경로 단일 출발 - 특정 노드에서 해당 노드간 경로를 찾는 문제 전체 쌍 최단 경로 - 그래프 내의 모든 노드 쌍(u,v)에 대한 최단 경로 다익스트라 알고리즘 최단 경로 문제 중 2번에 해당 하나의 정점에서 다른 모든 정점 간의 각 짧은 거리를 구하는 알고리즘 BFS와 유사 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든다. 인접 노드 간의 거리부터 먼저 계산하며, 가장 짧은 거리를 배열에 업데이트 여러 로직이 있지만, 가장 개선된 로직은 우선순위 큐 (heapq 라이브러리 사용) 다익스트라 - 우..

탐욕 알고리즘 매순간 최적의 해를 선택하는 방식 근사치 추정에 활용 (반드시 최적의 해를 구할 수 있는 것은 아니다.) 동전 문제 coin_list = [10, 50, 100, 500] def min_coin_count(money, coin_list): quotient_list = [] coin_list.sort(reverse=True) answer = 0 for coin in coin_list: count = 0 quotient = money // coin money = money % coin count += quotient answer += count quotient_list.append([coin, count]) return answer,quotient_list 몫은 quotient, list 내림..

그래프 실제 세계의 현상이나 사물을 노드(정점)와 간선(링크)로 표현 노드 : 위치, 정점(Vertex)로 부르기도 한다. 간선(Edge) : 노드를 연결한 선 (링크, 브랜치로 부르기도 한다.) 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 노드 그래프와 트리 차이 BFS & DFS 대표적인 그래프 탐색 알고리즘 BFS(Breadth First Search) : 정점들과 같은 레벨에 있는 노드를 먼저 탐색 DFS(Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식 BFS는 두 개의 큐 , DFS는 스택과 큐 활용 graph = dict() graph['A'] = ['B', 'C'] graph['B'] =..

이진 탐색 탐색할 자료를 둘로 나누어 탐색 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide & Conquer) Divide : 문제를 하나 또는 둘 이상으로 나눈다. Conquer : 나눠진 문제가 충분히 작고, 해결 가능하다면 해결, 아니면 다시 나눈다. 이진 탐색 정렬된 상태에서 진행 Divide : 리스트를 두 개의 서브 리스트로 나눈다. Conquer search > 중간값 이면, 뒤에서 찾는다. 반대면 앞에서 찾는다. def binary_search(data, search): if len(data) == 1 and search == data[0]: return True if len(data) == 1 and search != data[0]: return False if len(..

동적 계획법과 분할 정복 동적 계획법 (DP) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 부문 문제를 해결 상향식 접근법으로, 상위 문제를 풀어가는 방식 Memoization : 프로그램 실행 시 이전에 계산한 값을 저장하여, 실행 속도를 빠르게 하는 기술 문제를 쪼갤 때, 부분 문제는 중복되어, 재활용 된다. (피보나치) 분할 정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식 일반적으로 재귀함수 구현 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음 병합 정렬, 퀵 정렬 공통점과 차이점 공통점 문제를 잘게 쪼개서,..

재귀 용법 (Recursive call, 재귀 호출) 고급 정렬 알고리즘에서 재귀 용법을 사용 한다. 함수 안에서 동일한 함수를 사용 예제 def factorial(num): if num > 1 : return num * factorial(num-1) else: return num 시간 / 공간 복잡도 모두 O(n-1)이므로, 둘다 O(n)이 된다. def function(입력): if 입력 > 일정값: return function(입력-1) else: return 일정값 재귀 호출은 내부적으로 스택처럼 관리 된다. 파이썬에서 재귀 호출의 최대 깊이는 1000회이다. (즉, 스택 공간이 1000개) def palindrome(data): pal_data = data[::-1] if data == pal_..

버블정렬 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 즉, 한 회전 당 제일 큰값을 뒤로 보낸다. 데이터 길이 -1 만큼 턴한다. def bubblesort(data): for index in range(len(data) -1): swap = False for index2 in range(len(data) - index -1): if data[index2] > data[index2 +1]: data[index2], data[index2+1] = data[index2+1], data[index2] swap=True if swap == False: break return data 알고리즘 분석 반복문이 두 개 O(n^2) 최악의 경우 : n(n-1..