코딩고치

최소 신장 트리 신장 트리 그래프의 모든 노드가 서로 연결됨과 동시에 트리의 속성을 가지는 그래프. 조건 모든 노드가 연결 트리의 속성 (사이클을 가지지 않음) 최소 신장 트리 Minimum Spanning Tree (MST) 참고 : https://en.wikipedia.org/wiki/Minimum_spanning_tree 신장 트리 중에서 간선의 가중치의 합이 가장 작은 신장 트리 크루스칼 알고리즘 모든 노드를 독립적인 집합으로 만듦 간선을 최소 가중치를 가진 순서대로 정렬 이 노드 순서대로 노드를 연결 사이클이 생기지 않도록 주의 사이클이 생기면 제외를 한 후 다음 가중치를 가지는 간선을 이용하여 노드 연결 Union-Find 알고리즘 이용 참고 : https://ko.wikipedia.org/w..

자료형 숫자형 # 덧셈 print(4 + 7) # 뺄셈 print(2 - 4) # 곱셈 print(5 * 3) # 나머지 print(7 % 2) # 거듭제곱 print(2 ** 4) 11 -2 15 1 16 정수형끼리의 계산은 정수형이 출력 정수형과 실수형의 계산은 소수형 소수형끼리의 계산은 실수형 나누기 계산은 자료형 상관없이 소수형이 출력 print(4.0 + 7.0) print(4.0 + 7) print(7 / 2) # 정수형으로 출력 print(int(4.0 + 7)) 11.0 11.0 3.5 11 # floor division (버림 나눗셈) print( 7 / 3) print( 7 // 3) print(7.0 // 3) 2.3333333333333335 2 2.0 # round (반올림) pr..

최단 경로 알고리즘 최단 경로 문제 두 노드를 잇는 최단 경로 찾는 문제 가중치 그래프에서 가중치 합이 최소가 되는 것을 찾는 문제 문제 종류 단일 출발 및 단일 도착 문제 특정 노드 2개를 선택 후 가장 짧은 경로를 찾는 문제 단일 출발 문제 특정 노드 1개에서 다른 노드들 간 가장 짧은 경로를 찾는 문제 전체 쌍 문제 그래프 내 노드 쌍에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 단일 출발에 대한 답을 찾는 문제 첫 노드를 기준으로 인접한 노드를 추가해 가면서 최단 거리를 구해나가는 방법 너비 우선 탐색과 유사 우선순위 큐를 이용 1) 첫 노드를 기준으로 각 노드들 간의 거리를 저장하는 배열 생성 첫 노드의 거리는 0, 나머지는 무한대로 설정 (inf) 첫 정점 거리 (0)을 먼저 배열에 입력..

탐욕 알고리즘 최적의 해에 가까운 값을 구하기 위한 방법이다. 여러 경우가 있을 때 매 순간 조건에 맞는 최적의 경우를 찾아나가는 방식이다. 예시 동전 문제 지불해야 할 값이 6870원 일 때 10, 50, 100, 500원 동전으로 가장 적은 수의 동전으로 계산 가장 큰 동전부터 지불 coins = [500, 100, 50, 1] def coin_count(price, coins): coin_count = 0 ledger = list() coins.sort(reverse=True) # 내림 차순으로 정리 for coin in coins: coin_num = price // coin coin_count += coin_num price -= coin_num * coin ledger.append([coin,..