Debug.Log

최소 신장 트리 (Minimum Spanning Tree) 최소신장트리?신장트리란, 사이클을 형성하지 않고 그래프의 모든 정점(V)이 간선(E)으로 연결되어 있는 것최소신장트리란 최소한의 비용으로 신장트리를 형성하는 것 Kruskal's Algorithm모든 정점을 독립적인 집합으로 만든다.모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.시간 복잡도는 ​ Python Codeparent = {} rank = {} ​ # 정점을 독립적인 집합으로 만든다. def make_set(v): parent[v] = v rank[v] = 0 ​ # 해당 정점의 최상위 정점을 찾는다. def find(v):..

최장 공통 부분 수열(Longest Common Subsequence)두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.diff 명령은 LCS 문제를 해결하는 데 기반을 둔다. diff utility다음과 같이 두 항목이 있다고 하자.a b c d f g h j q za b c d e f g i j k r x y z 여기서 공통이 되는 가장 긴 부분은 다음과 같다.a b c d f g j z 두개 항목을 비교하여 추가(+)되거나 삭제(-)된 부분을 다음과 같이 나타낸다.e h i q k r x y + - + - + + + + LCS 함수의 정의두 수열은 다음과 같이 정의.​, ​. Python CodeA =..

연쇄행렬 최소곱셈 알고리즘 (Matrix Chan Multiplication)연쇄행렬 최소곱셈은 동적 프로그래밍(Dynamic Programming)을 활용하여 연산을 최적화 시키는 것행렬은 결합법칙이 성립한다.(AB)C = A(BC) 그러나 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.예를들어,A : 10x30 행렬B : 30x5 행렬C : 5x60 행렬일 경우(AB)C는 (10x30x5) + (10x5x60) = 1,500 + 3,000 = 4,500번의 연산으로 구할 수 있지만A(BC)는 (30x5x60) + (10x30x60) = 9,000 + 18,000 = 27,000번의 연산을 해야 구할 수 있다. 즉, 연쇄행렬 최소곱셈은 곱하는 순서에 따라 연산의 순서가 달라지는데, 이를 최적화 하는..

제곱 계산제곱 계산은 ​의 형식을 형태이다.본 포스팅에서는 b가 자연수인 경우 제곱 계산을 다루므로 ​으로 표기하겠다.파이썬에서 제곱 계산은 pow(a, n) 함수를 사용하거나, a**n 연산을 사용하면 된다.이제 power함수를 구현해보자. 1. n번 곱하기def power(a, n): ret = 1 for i in range(n): ret *= a return ret print(power(5, 5)) print(power(5, 21))1에다가 a를 n번 곱한다.시간복잡도는 O(N) 2. ​의 power 함수def power(a, n): ret = 1 while n > 0: if n % 2 != 0: ret *= a a *= a n //= 2 return ret print(power(5, 5)) pri..

최대공약수, 최소공배수 알고리즘 유클리드 호제법으로 최대공약수 구하기최대공약수를 구하는 함수를 ​라고 하자.​ 이라면, ​ 임이 성립.​ 이 이라면, ​ 임이 성립한다.def gcd(a, b): mod = a%b while mod > 0: a = b b = mod mod = a%b return b 최소공배수최소공배수는 a과 b의 곱에 최대공약수를 나누어 준 것과 같다.def lcm(a, b): return a*b//gcd(a,b) 최대공약수 (GCD : Greatest Common Divisor)최소공배수 (LCM : Least Common Multiple)

Infix를 Postfix로 바꾸기 중위 표기법(Infix) 우리가 흔히 아는 산술식이다.2 + 3 * 4 혹은 2 + 5 * ( 3 + 4 ) 등과 같이 괄호나 우선순위에 의해 풀어가는 방식.인간이 계산하기에 친숙한 표기법이다. 후위 표기법(Postfix)반면 컴퓨터는 중위표기법으로 계산을 하는 건 매우 어려운 문제이기 때문에 이를 보완하기 위해 후위 표기법으로 바꿔준다.2 3 4 * + 혹은 2 5 3 4 + * + 등으로 표기한다.연산자가 나오면 그 이전의 숫자 2개와 연산을 하는 방식이다.2 3 4 * +는 2 12 +으로, 그리고 14 순으로 계산한다. Infix를 Postfix로중위 표기법을 후위 표기법으로 바꾸기 위해서는 스택을 이용한다.infix를 순서대로 읽는다.읽은 값이 여는 괄호 '(..

소수판별1. 에라토스테네스의 체고대 그리스 수학자 에라토스테네스가 발견한 소수 찾는 방법.N보다 작은 소수들을 찾으려면, 2보다 크거나 같고 ​보다 작은 소수의 배수들만 지우면 된다.예를 들어, 120보다 작은 소수들을 모두 찾고 싶다면, ​ 이므로 2, 3, 5, 7의 배수만 지우면 남은 수는 모두 소수가 된다.작은 수의 소수를 판별하는 데 유용하다. def is_prime(num): if num

퀵 셀렉션 (Quick Selection) 파이썬으로 구현퀵 셀렉션은 리스트를 정렬하지 않고 K번째로 큰 수를 알고 싶을 때 쓰는 방법이다.전체적인 솔루션은 퀵 정렬과 매우 유사하다, 피벗을 하나 골라서 값을 비교하면서, 피벗보다 작은 리스트, 피벗 보다 큰 리스트로 나눈다.k번째 숫자가 속해있는 리스트만 가지고 다시 재귀적으로 반복한다.median 값을 찾을 때도 활용 가능.평균 시간복잡도는 O(n) def quick_selection(arr, kth): pivot = arr[(len(arr)+1)//2 - 1] left, mid, right = [], [], [] for i in range(len(arr)): if arr[i] pivot: right.append(arr[i]) else: mid.app..

이진 검색 (Binary Search) 파이썬으로 구현Binary Search 는 오름차순으로 정렬된 리스트에서 특정값의 위치를 찾는 알고리즘처음 중간의 임의 값을 선택하여, 그 값의 크고 작음을 비교시간복잡도는 O (log N) 이다. def binary_search(arr, value): low = 0 high = len(arr)-1 while (low value: high = mid - 1 elif arr[mid]

계수 정렬 (Counting Sort) 파이썬으로 구현계수 정렬은 비교 정렬이 아니다.K가 정수일 때 (즉, K가 어떤 최대값을 가질때), 입력 요소들이 1부터 K까지의 정수라고 가정.히스토그램과 같이 각 요소들이 전체 리스트에서 몇 개씩 존재하는 지를 세아려 테이블을 만든다.입력된 X 아래에 몇개의 정수들이 존재하는 지에 따라 X의 위치가 결정되는 알고리즘.(예를 들어, 5보다 작은 정수 (1,2,3,4) 가 10개 존재한다면, 5가 들어갈 위치는 11번째이다.)시간복잡도가 O(n)이다. def counting_sorted(arr, K): c = [0] * K sorted_arr = [0] * len(arr) for i in arr: c[i] += 1 for i in range(1,K): c[i] +=..