Greedy Approach - Prim's Algorithm
2020. 5. 18. 14:45
🕶 Algorithm/알고리즘
Greedy Approach : 반복 알고리즘으로써 매번 Step에서 무엇인가 선택을 할 때 목적함수 값을 최대화 하거나 최소화하는 방향으로 선택하는 것 결과적으로는 최선의 선택이 되지 않는다. 동전을 거슬러 주는 횟수를 최소화 하기 위해선? 동전을 큰 것부터 주자. 1. Selection procedure : 동전의 단위가 큰거부터 체크한다. 2. Feasibiliy check : 조건의 맞는 것을 체크한다. 3. Solution check : 거스름돈이 완성됐는지 체크한다. Minimum Spanning Tree undirected graph : 무향 그래프 directed graph : 유향 그래프 Tree : Acyclic connected graph : 연결 그래프이면서 싸이클이 없는 그래프 R..
Sequence Alignment Algorithm
2020. 5. 15. 15:35
🕶 Algorithm/알고리즘
여러개의 서열 중에서 서로 닮은 부분과 다른 부분을 찾아내는 알고리즘 2개의 다른 DNA 서열을 대응시켜 유사성을 비교 G A ·· C G G A T T A G G A T C G G A A T A G 두 서열은 서로 다른 길이를 가질 수 있고 또한 각 서열은 공백들을 가질 수 있다. 주어진 두 서열에 공백들을 포함시켜 서로 같은 길이로 만든다. 공백들끼리 대응되는 것은 허용되지 않지만 서열의 시작부분과 끝 부분에도 공백을 삽입할 수 있다. 두 서열을 대응시키기 위해 score를 정한다. 한 열(column)에 같은 문자가 있다면 score는 + 1 (match) 다른 문자가 대응되었을 때는 -1 (mismatch) 문자와 공백이 대응되었을 때는 -2 이 방법으로 위 두 서열의 score를 계산하면 9x1..
Traveling Salesperson Problem
2020. 5. 14. 00:00
🕶 Algorithm/알고리즘
왜 v1부터 시작하는가? cycle 이니까 시작점이 어디든 상관없지만 그냥 v1에서 시작하는걸로 생각하자 G = (V,E) vertex, edge W : 인접행렬의 매트릭스 V : 그래프의 꼭지점 = {v1, v2, v3, v4} A : V의 부분집합 D[vi][A] : vi 에서 모든 A를 하나씩 방문하면서 v1로 가는 가장 짧은 거리 만약 A가 {v3} 였다면? D[v2][A] 는 경로가 없으므로 무한대 : 2->3->1 만약 A가 {v3, v4} 였다면? D[v2][A] 는 2->3->4->1 or 2->4->3->1 i = 1 은 아니다. 그리고 vi는 V의 원소가 아니다. D[vi][￠] = W[i][1], if A = 공집합 : vi에서 바로 vi로 간다는 소리 D[vi][A] = minimu..
Traveling Salesperson Problem (TSP) - 0
2020. 5. 13. 22:37
🕶 Algorithm/알고리즘
외판원문제(TSP)에 대해 살펴보도록 하겠습니다. 외판원문제는 난해한 문제로 잘 알려져있지요. 간단히 말하면 "모든 도시들을 한 번씩 방문하는데 드는 최소 비용을 구하라" 정도가 될 것같습니다. 예를 들어볼까요? 위와 같은 도시들이 있다고 합시다. 1,2,3이 도시의 번호이고 가운데 숫자는 도시간 이동비용이 되겠습니다. 어떻게 가야 비용이 덜 들까요? 1->2->3의 순서로 가면 되겠네요. (총 비용 30) 3->2->1의 순서로 가도 같은 비용이군요. 3->1->2와 같은 최악의 선택만 하지 않으면 됩니다. 외판원 문제가 어려운 이유는 "가능한 모든 경로를 조사해야 한다"는 사실에 있습니다. 위 그림에서 가능한 경로는 1->2->3 1->3->2 2->1->3 2->3->1 3->1->2 3->2->1..
알고리즘 과제 #3
2020. 5. 12. 20:55
🕶 Algorithm/알고리즘
Optimal binary search tree를 구하는 dynamic programming algorithm과 Optimal sequence alignment룰 구하는 dynamic programming algorithm을 구현하는 것이다. Optimal binary search tree [50점] 제 3 장에서 공부한 optimal binary search tree를 구하는 dynamic programming algorithm을 C/C++ 언어로 구현하시오. 입력은 한 줄로 이루어지며, 입력 값들은 space로 구분되어 입력된다. 첫 번째 입력 값은 key의 개수 이며, 두 번째부터 번째 입력 값은 각 key를 search할 확률 이다. Key1, Key2, …, Keyn 은 정렬되어 있다고 가정한다..
Optimal Binary Search Tree
2020. 4. 30. 15:13
🕶 Algorithm/알고리즘
트리들 중 어느 트리로 만들어야 좋을까? key 를 search할 때 걸리는 시간을 적게 하고 싶다. 비교횟수를 최소화 하고 싶다. 각 key를 찾을 때까지 key comparison의 최솟값 각각의 key들을 search할 확률이 1/7 로 하지않고 비교한다. 여러개의 키로 이루어져 있다. 각 키를 search할 확률이 나와 있다. 1 >> key1 을 찾을 때까지 비교를 3번 하게 된다. 0.7 × 3 + 0.2 × 2 + 0,1 × 1 2 >> key2 을 찾을 때까지 비교를 3번 하게 된다. 0.7 × 2 + 0.2 × 3 + 0,1 × 1 3 >> key3 을 찾을 때까지 비교를 3번 하게 된다. 0.7 × 2 + 0.2 × 1 + 0,1 × 2 4 >> key4 을 찾을 때까지 비교를 3번 하..
Binary Search Tree
2020. 4. 28. 21:06
🕶 Algorithm/알고리즘
Binary Search Tree 이번 글에서는 자료구조의 일종인 이진탐색트리(Binary Search Tree)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님, 그리고 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 기본으로 하되 중위순회 등 요소를 제가 추가하였습니다. 그럼 시작하겠습니다. Concepts 이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종입니다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐습니다. 예컨대 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능합니다. 연결..
Dynamic Programming - Chained Matrix Multiplication
2020. 4. 21. 22:00
🕶 Algorithm/알고리즘
3.3 Dynamic Programming and Optimization Problems substance -> subinstance Optimal solution 안에는 그 문제의 모든 subinstance의 solution이 다 포함되어 있다. 문제 자체가 이런 성질을 가지고 있어야 DP를 적용할 수 있다. 모든 문제가 가지고 있는 성질이 아니다. 3.4 Chained Matrix Multiplication 행렬이 교환법칙은 성립하지 않지만 결합법칙은 성립한다. 행렬의 곱셈은 standard algorithm을 사용한다. scalar multiplication 이기도 하고 scalar addition 이기도 하다. 3번째가 가장 적게 걸린다. 곱하는 서로다른 순서가 몇가지냐? : Catalan num..
Dynamic Programming - Floyd's Algorithm
2020. 4. 21. 17:38
🕶 Algorithm/알고리즘
많은 경우 중에서 비용 혹은 길이가 최소인 경우는? i부터 j까지의 최단 경로
Dynamic Programming - The Binomial Coefficient
2020. 4. 21. 17:23
🕶 Algorithm/알고리즘
3.1 The Binomial Coefficient nCk 라고 배웠다. standard notation은 (nk) 라고 쓴다. 위. n개의 물건 중 k개를 선택하는 방법. 시간이 오래걸린다. 계속 중첩돼서 값을 구해야 하기 때문에 오래 걸린다. 했던 일 또하고 또하고 또하고 recursive call 일어나는 횟수를 세면 2 * nCk - 1 이다. 이게 시간복잡도이다. n값이 고정되어 있더라도 k값이 변한다. k값이 n/2일 때 값이 가장 크다. Algorithm 3.1의 시간복잡도가 나쁘다는 것을 알 수 있다. 그러면 어떻게 하냐? B라는 2차원 배열을 만들어서 i값은 0부터 n까지 j값은 0부터 k까지 ㄱ 형태로 더하면서 채운다. 맨아래쪽의 ㄱ 아래 값을 return 하면 된다. 시간 복잡도는 채..
Determining Thresholds
2020. 4. 19. 22:31
🕶 Algorithm/알고리즘
2.7 Determining Thresholds threshold 란? : 단순한 알고리즘보다 Strassen의 알고리즘을 사용하는 편이 더 좋을 것이라고 예상되는 지점 n-1 : merge할 때 걸리는 시간. 실험을 통해 알아내야 한다. merge 알고리즘을 만든 다음에 넣어봐야 아는 것이다. merge 할 때 시간 복잡도가 32 n 이라면 시간복잡도가 32n logn 는 merge sort 알고리즘 시간복잡도 이고 exchange sort 했을 때 n(n-1)/2 이다. exchange sort 실행 시간 < merge sort 실행 시간인 지점을 봐보자. 이 부등식의 의미는 n=1 이 될 때까지 한 것. 등식보다 ≥ 부등식으로 풀어야 한다. 현재 배열의 사이즈 = t 개 t개의 원소를 t/2로 나눠..
Multiplication of Large Integers (아주 큰 정수의 곱셈)
2020. 4. 18. 12:04
🕶 Algorithm/알고리즘
2.6 Arithmetic with Large Integer 2.6.2 Multiplication of Large Integers 굉장히 큰 정수의 곱셈은 어떻게 할까? 배열로 표현 한다. n자리 정수의 곱 시간복잡도는? n자리 정수 2개 곱셈 = O(n^2) 그럼 Divide and conquer로 시간복잡도를 낮춰보자. n자리 정수를 절반으로 나눠서 계산하자 m은 n자리 정수를 2로 나눈 값이다. u와 v 는 n자리 정수이다. >>> integer 타입이 아니라 배열이다. if ( u 나 v 가 0이면 ) : 곱이 0이니까 0이고 else if ( threshold보다 작다면 ) : u와 v를 그냥 곱한다. else : m은 n을 2로 나눈 값이고 divide는 나눈 몫을 나타낸다. 이때 divde는..
Strassen Algorithm
2020. 4. 17. 12:57
🕶 Algorithm/알고리즘
행렬의 곱셈 크기가 n x n인 두 행렬 A와B의 곱을 C로 나타내고자 한다. 의 원소를 라 하고, 는 가로 는 세로를 나타낸다. B와 C도 동일하게 표시한다. 행렬의 곱셈을 다음과 같이 표현할 수 있다. C하나의 원소를 구하는데 드는 비용은, 곱셈 번과 덧셈 번이다. 따라서, C 전체를 구할 경우 C의 크기는 n x n 이므로 곱셈을 번 그리고 덧셈을 번하게 된다. 따라서, 두행렬을 구하는 복잡도는 이 된다. 알고리즘 A와 B를 체 F에 대한 정사각행렬이라고 하자. 두 행렬의 곱 C는 다음과 같다. 만약 A와 B가 2ⁿ × 2ⁿ 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다. 이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라 내야 한다. 이제 A, B, C를 같은 크기의 정..
Divide-and-Conquer (part4)
2020. 4. 2. 17:34
🕶 Algorithm/알고리즘
이걸 Divide-and-Conquer 해보자. 이걸 C행렬에 갖다 놓는다. C행렬의 첫번째 칼럼 ADD = 행렬의 덧셈의 관한 함수 문제 나온다 그니까 Master theroem 공식 외워라 ! Recursive Matrix Multiplication에 적용 (n/2 - n/2) 행렬 M7 까지 n/2 by n/2 행렬이다. scalart multiplicationdml 횟수 scalar addtion = 0 Scalar additon의 횟수
Divide-and-Conquer (part3)
2020. 4. 2. 16:18
🕶 Algorithm/알고리즘
Divide-and-Conquer 시간복잡도 함수의 일종의 공식 P 633 + 110 = ppt 743 자세한 설명 : https://ratsgo.github.io/data%20structure&algorithm/2017/09/11/recurrence/ 재귀함수의 계산복잡도 · ratsgo's blog 이번 글에서는 알고리즘의 계산복잡도 함수가 재귀식(Recurrence relation) 내지 점화식 형태로 표현되는 경우를 살펴보도록 하겠습니다. 재귀식 또는 점화식이란 피보나치 수열(다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열)처럼 수열의 항 사이에서 성립하는 관계식을 말합니다. 이로부터 데이터 수 $n$에 대해 닫힌 형태(closed-form expression)의 정확한 계산복잡도..