Debug.Log

연쇄행렬 최소곱셈 알고리즘 (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번의 연산을 해야 구할 수 있다. 즉, 연쇄행렬 최소곱셈은 곱하는 순서에 따라 연산의 순서가 달라지는데, 이를 최적화 하는..

C언어 포맷출력 인자전달 (passing parameter to printf)C/C++에서 포맷 출력할 때 인자를 전달해야 할 경우가 있다.예컨대, https://www.acmicpc.net/problem/1022 백준온라인저지의 1022번 문제 (소용돌이 예쁘게 출력하기) 에서도 정수의 최대길이에 따라 출력 포맷이 달라진다. %dprintf("%d\n", 100); printf("%d\n", 20);일반적인 정수포맷의 출력방법. %ndprintf("%3d\n", 100); printf("%3d\n", 20);출력하는 정수의 최대길이를 정해준다.최대길이보다 짧은 경우 앞은 공백으로 채워진다. %*dint max_len = 3; printf("%*d\n", max_len, 100); printf("%*d\..

제곱 계산제곱 계산은 ​의 형식을 형태이다.본 포스팅에서는 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] +=..

퀵 정렬 (Quick Sort) 파이썬으로 구현퀵 정렬은 분할 정복 알고리즘의 좋은 예이다.리스트 중 하나를 pivot으로 정하고, pivot보다 작은 아이템은 왼쪽, pivot보다 큰 아이템은 오른쪽으로 보내면서 pivot의 자리를 확정한다.그리고 왼쪽 리스트와 오른쪽 리스트에 대해서 재귀형식으로 진행.평균 시간복잡도는 O(n*log n), 최악의 시간복잡도는 O(n^2) def quick_sorted(arr): if len(arr) > 1: pivot = arr[len(arr)-1] left, mid, right = [], [], [] for i in range(len(arr)-1): if arr[i] pivot: right.append(arr[i]) else: mid.append(arr[i]) mi..