blog...

Dijkstra 다익스트라 출발점으로부터 각 정점까지의 최단거리 및 경로 계산 Prim-MST 알고리즘과 유사. 차이점은 Dijkstra-최단경로는 출발점이 주어진다는 것, D의 원소에 출발점부터의 경로의 길이가 저장된다는 것! Prim→어느 정점에서 시작해도 같은 그래프를 도출 / D의 원소에 자신과 연결된 간선의 가중치를 저장 Dijkstra→특정 정점으로부터의 최단 경로를 구하기 때문에 시작 정점이 바뀔 때마다 최단 경로 그래프가 다르게 도출 / D의 원소에 출발점부터의 경로의 길이를 저장 for k in range(N): m=-1 # m:min_vertex min_value=sys.maxsize # 가장 가까운 정점찾기 for j in range(N): if not visited[j] and D[j]

최소신장트리 MST 하나의 연결성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치 합이 최소인 신장트리 ※ 신장트리란(Spanning Tree)? → 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분그래프 MST 알고리즘에는 Kruskal, Prim, Sollin이 있음→Greedy Kruskal 알고리즘 가장 작은 가중치 순서대로 선택 (가중치1→2→3 이런식으로) 사이클 만들면 버리기 n-1개 간선 선택되면 종료 주요코드(일부) weights=[(0,1,9),(0,2,10)...(5,6,6)] # u,v,wt 순 #kruskal은 가중치를 기준으로 정렬해야함! weights.sort(key=lambda t:t[2]) # find함수 : u가..

그래프 연결되어 있는 객체 간의 관계를 표현하는 자료구조 그래프 용어 정점(vertex)과 간선(edge) 방향그래프: a→b 무방향그래프: a↔b (a, b) 차수(Degree): 정점에 인접한 정점의 수 (진입차수, 진출차수) 경로: 시작정점부터 도착점까지의 정점들을 나열 단순경로: 경로상의 정점들이 모두다름 일반적인경로: 중복하여 방문하는 경우도 포함 싸이클: 시작점과 도착점이 같은 단순경로 (트리는 사이클 안됨) 연결성분: 그래프에서 정점들이 서로 연결되어 있는 부분 가중치 그래프: 가중치 부여된 그래프, 음수가중치도 있음 부분그래프 트리: 싸이클이 없는 그래프 신장트리(spanning tree): 하나의 연결성분, 모든 정점들을 싸이클 없이 연결하는 부분그래프 네트워크: 간선에 비용or가중치가 ..

heapq 라이브러리 heapq.heappush(heap, item) : item을 heap에 추가 heapq.heappop(heap) : heap에서 가장 작은 원소를 pop heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 https://www.codetree.ai/missions/8/problems/%08merge-numbers/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai import heapq n=int(input()) arr=list(map(int,input().split())) heapq...

서비스 운영상의 사유로, 제공되는 라이브러리가 사전 공지 없이 변경될 수 있는점 참고 부탁드립니다. string , textwrap, datetime, calendar, collections, collections.abc, heapq, bisect, array, weakref, types, copy, pprint, reprlib, enum, numbers, math, cmath, decimal, fractions, random, statistics, itertools, functools, operator, queue, time, typing 출처: SWEA Q&A https://swexpertacademy.com/main/help/qna/qnaBoardView.do?commuId=AYD03qNaVcsDF..

헷갈리는 것 위주로 정리하였다. format 형태 x, y = 3, "hi" print("x is {0} and y is {1}" .format(x, y)) print("x is {} and y is {}" .format(x, y)) print("x is {new_x} and y is {new_y}" .format(new_x=x, new_y=y)) f string 형태 first_name = "John" print(f"Hello, {first_name}!") 소수점 "{ : .2f }.".format(실수 혹은 변수) : 소수점 3번째 자리에서 반올림을 해서 2자리 까지 출력 f'{변수:.2f}': 소수점 3번째 자리에서 반올림을 해서 2자리 까지 출력 ※소수점 처리 round(실수 혹은 변수, 2): ..

프레임워크 개발자가 개발을 쉽게 할 수 있도록 뼈대를 제공 라이브러리 라이브러리는 개발에 필요한 것들을 미리 구현해놓은 도구 재사용이 가능한 기능을 미리 구현해놓고 필요한 곳에서 호출하여 사용 가능하도록 만들어진 집합 차이 프레임워크와 라이브러리는 제어권한/주도성이 어디에있는지에 따라 차이가 있다. 라이브러리는 단순하게 활용할 수 있는 도구들의 집합이므로, 프로그램에게 실행흐름의 주도권이 있다. 프레임워크는 본인의 제어 흐름 상에서 코드를 호출해 앱을 실행하는 것이다. Library Framework 보조적인 모듈, 클래스, 함수, 코드 집합 API, 컴파일러, 라이브러리 등 주도권이 우리들의 프로그램에 있음 (프레임워크가 코드 호출) 주도권이 프레임워크에 있음 다른 라이브러리로 대체하는게 수월함 다른 ..

Binary search algorithm #O(logn) def binarySearch(A,x): n = len(A) beg = 0 end = n - 1 result = -1 while (beg

13. Fibonacci 피보나치 기본코드(재귀) def fibonacci(n): if n= 0 and matches[e - j] != 0): min_cnt = min(min_cnt, matches[e - j] + 1) if min_cnt != len(A): matches[e] = min_cnt #match[현재위치]에 최소 카운트 삽입 if matches[-1] != 0: return matches[-1] else: return -1 def fibonacciDynamic(n): fib = [0] * (n+2) fib[1] = 1 for i in range(2, n + 2): fib[i] = fib[i - 1] + fib[i - 2] if fib[i] > n: return fib[:i+1] return ..

12. Euclidean algorithm 최대공약수, 최소공배수 알고리즘 https://hyunjini.tistory.com/54 최대공약수 최소공배수 알고리즘 (유클리드 호제법) 최대공약수 ➡️유클리드 호제: 2 개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다 두 수를 입력으로 받고 작은 수가 0이 될때 까지 hyunjini.tistory.com 12.1 ChocolatesByNumbers Two positive integers N and M are given. Integer N represents the number of chocolates arranged in a circle, numbered from 0 to N ..