알고리즘/python 기초 썸네일형 리스트형 최소 스패닝 트리(MST) 1. 스패닝 트리 / 신장 트리 - 그래프 내의 모든 정점을 포함하고 그래프의 일부 간선을 선택해서 만든 트리 - 스패닝 트리는 노드가 N개, 간선이 N-1개가 됨 - Spanning Tree는 모든 정점들이 연결 되어 어야 하고 사이클을 포함해서는 안된다. Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다. 2. 최소 스패닝 트리(MST) - 간선의 가중치의 합이 최소인 스패닝 트리 - 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우에 사용됨 - 알고리즘 : 크루스칼, 프림 (둘 다 그리디 기반 알고리즘) 3. 알고리즘1 : 프림 - https://www.fun-coding.org/Chapter20-prim-live... 더보기 최단 경로 1. 다익스트라 알고리즘 - 특정 노드 -> 다른 모든 노드를 가는 최단 경로를 구함 - '음의 간선'이 없을 때 사용 가능 (GPS SW 기본 알고리즘으로 사용) - 그리디 알고리즘 - 출발 노드를 설정한 후, 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택해가는 알고리즘 - 입력 시 sys.std.realine()으로 사용하는 것 추천! - 헷갈리지 말 것 : dist를 갱신하는 거랑 노드를 선택하는 과정을 별개로 생각하기! * 간단하지만 오래 걸리는 구현 방식 #DFS로 구현 #리스트 : 노드 개수 + 1 import sys input = sys.stdin.readline INF = int(le9) #무한대.10억 #입력받기 N,M = map(int,input().split() #노드개수.. 더보기 DP 1. DP로 풀 수 있는 문제 조건 - 큰 문제를 작은 문제로 나눌 수 있다. - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 2. 메모리제이션 - DP 구현 방법 중 하나. 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 저장한 결과를 가져오는 기법 ( caching 기법이라고도 함) - 이전에 계산된 결과를 일시적으로 기록하는 개념 - top-down방식에 사용되는 기법 ( 재귀함수를 사용하여 큰 문제를 해결하기 위해 작은 문제를 호출) 3. top-down / bottom-up - top-down : 재귀 함수 호출 - bottom-up : 반복문을 사용하여 작은 문제부터 값을 구해가는 방식. 이 때 결과를 저장하는 리스트를 dp 테이블이라 함 4. DP임을.. 더보기 탐색 1. 순차탐색 - 리스트 내 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 - O(N) 2. 이진탐색 - 찾으려는 데이터와 중간 위치 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법 - 배열 내 데이터들이 정렬되어있어야 한다. - 확인하는 데이터의 개수가 절반씩 줄어든다는 점에서 O(logN) - 입력 데이터가 2000만을 넘어가면 이진 탐색으로 접근해보기 def binary_search (array,target,start,end): if start > end: return None mid = int((start + end) // 2) if array[mid] == target; return mid elif array[mid] > target: return binary_sear.. 더보기 이전 1 다음