개발하는 멍정이야기

Merge Sort Revisited : 잘게 쪼개서 합치면서 비교하며 정렬 worst case time complexity = n lg n + n + 1 -> 합치는 과정에서 2개 이상을 한 번에 처리할 수 있기 때문에 아까보다 좋아짐! - 더욱 개선 할 수 있는 방법? 1. Dynamic programming 2. LInked list 3. More complex merge algorithm merge sort의 자세한 알고리즘은 요기... [알고리즘] Binary Search, Mergesort(DIvide and Conquer) DIvide and Conquer Approach - Divide : 인스턴스가 너무 커서 계산이 힘들다면 작게 쪼개서 계산한다. - Conquer : 작아진 인스턴스를 ..

Two Types of Complexity Analysis Algorithm Analysis : 효율적인 알고리즘을 찾기 위한 접근법 -> time complexity & space complexity problem Analysis : 좀 더 본질적인 문제의 복잡성에 대한 분석 -> matrix multiplication의 경우 n^3이 되는 경우, n^2.81(스트라센) 아무튼 이런저런 방식이 있음 -> 계산 복잡도에 대한 분석을 해보자? (computatuinal complexity analysis) Computational Complexity Objective Ω(f(n))에 대해 Θ(f(n))을 개발하는 방법? -> 하지만 문제의 하한보다 낮은 알고리즘을 개발하는 것은 불가능!! ex. sorti..

The Traveling Salesperson Problem -> 비행기타고 여기저기 출장 다녀오기 (ง˙∇˙)ว + 최소값으로 다녀와야함 Input - 값이 있는 방향 그래프 - 음수 x - 행과 열이 1부터 n까지인 2차원 배열 W - W[i][j] : i번째 정점에서 j번째 정점까지의 간선 위의 가중치 Output - 최적 투어의 길이를 값으로 하는 변수 minlength, 그를 구성하는 행렬 P Dynamic Programming for TSP - Brute force algorithm(전부 찾기) : (n - 1)! - The length of the optimal path(최적 경로 방법?) 아무튼 최단 거리를 찾는게 목표 일반적으로 i가 1이 아니고 vi가 A가 아니라면 a가 0이 아니면(내..

Branch and Bound Algorithm - backtracking을 개선한 알고리즘 - state space tree은 backtracking처럼 그대로 사용됨 - 최적화 문제에 사용 What is a bound? : 바운드는 노드를 넘어 확장하여 얻을 수 있는 해의 값? - 노드의 경계를 계산하여 노드가 유망한지 여부를 확인 - 경계값이 지금까지 발견된 최상의 솔루션의 값보다 크지 않으면 non-promising => k - 1까지의 가장 큰 값이 bound라서 다음 노드의 bound가 Maxprofit보다 작으면 확인 할 필요 없음! -> 내가 찾은 값이 더 크니까! The 0/1 Knapsack Problem Revisited : 가방에 최대한 많은 물건을 훔치자!-> 얼마짜리를 몇키로까지..

Monte Carlo Algorithm - 확률적 알고리즘으로 확률적 분포에 따라 무작위로 결정된다. In backtracking Algorithm - backtracking 알고리즘의 효율성을 추정할 때 사용할 수 있다. - state space tree의 동일한 level에서는 동일한 promising function을 사용 - 동일한 level의 node에는 동일한 수의 자식 노드가 있어야 함. Monte Carlo Algorithm in 4 - queens problem 4-queens problem에서 monte carlo algorithm으로 backtracking algorithm의 효율성 측정하기 -> 실제 방문해야할 노드를 추정 1. i 번째 노드에서 n개 중에 3개정도를 조사하였을 때 ..

Backtracking Technique - dead end를 만나면 뒤로 돌아가서 다른 선택지를 선택함 - Depth First Search(DFS | 깊이 우선 탐색)으로 진행 a modified depth-first-search of a tree (수정된 깊이 우선 탐색) : dead end라는걸 알고 있다면 그 노드는 탐색하지 않음 //유망함수로 판별 promising function(유망 함수) 특정 상태에서 이어진 경로가 해결책이 될 가능성이 있는지 결정 -> 문제의 해결 가능성을 평가하기 위함. -> 트리를 탐색하며 유망함수를 통해 유망한 트리만 탐색함. The Depth First Search(깊이 우선 탐색) //일반적인 방법 1. 루트 방문 2. 하위 노드 방문(왼쪽 -> 오른쪽) //..

Chained Matrix Multiplication (연쇄 행렬 곱셈) : 행렬 i x j와 행렬 j x k 처럼 열의 갯수와 행의 갯수가 같은 연속적인 행렬의 곱셈 - 행렬의 곱은 결합법칙이 적용하기 때문에 곱하는 순서는 상관없지만 곱하는 횟수가 달라지기 때문에 최적의 순서를 구해야한다. e.g. A1 x A2 x A3. A1은 10 x 100, A2는 100 x 5, A3은 5 x 50. (A1 x A2) x A3 10 x 100 x 5 + 10 x 5 x 50 = 7,500 A1 x (A2 x A3) 100 x 5 x 50 + 10 x 100 x 50 = 75,000 //100을 2번 계산하기 때문에 연산 횟수가 증가함 Brute force algorithm : 전부 해보기 이런 방법에 대한 시간..

Graph Theory - 그래프는 G = (V, E)의 두 요소로 구성된다. - vertex : 정점 - E : 간선들의 집합 | 간선들은 2개의 endpoint를 가진다. - directed graph(digraph) : 방향성이 있는 그래프 - weighted graph(weights) : 값이 있는 그래프 - path : digraph에서 정점에서 목적지로 가는 방법(정점들을 담고 있는?) - cycle : path가 돌아서 시작점으로 돌아옴 ㄴcycle인 그래프를 cyclic, 그렇지 않으면 acyclic - simple : 같은 정점을 다시 돌아오지 않는 경우 - length : weighted graph에서 weights들의 합 Example : A weighted, directed grap..

Dynamic Programming (동적 계획법) Bottom up 방식으로 작은 값 부터 구하기 시작하여 결과를 도출한다. 작은 값부터 시작하는건 DIvide and Conquer랑 비슷하시지만 밑에서부터 시작한다는 점에서 차이점이 있다. Bottom up 방식이기 때문에 한 번 계산한 결과를 다시 계산할 필요 없이 저장된 결과를 불러서 사용한다. The Binamial Conefficient(이항계수) 조합 n​Cr n개에서 r개를 순서 상관없이 골라내는 경우의 수 전체 경우의 수 n! 에서 필요없는 나머지 경우의 수 (n-1)!을 나누고 순서가 상관 없기 때문에 뽑은 갯수 k!만큼 또 나눠주기~ Pascal's Triangle 대각선 위에 있는? 값들의 합은 아래에 있는 값이 된다! 조합을 사용해..

Matrix Multiplication : 행렬의 곱은 어떻게 계산 할까 //Matrix Multiplication //Standard Algorithm void matrixmult(int n, const number A[][], const number B[][], number C[][]) { index i, j, k; for (i = 1; i 결과적으로 DIvide and Conquer이 되는 것!! strassen(행렬 A, 행렬 B, 새로운 행렬 C) { if(일반적인 계산이 더 이득일 것 같은 경우) 일반적으로 C = A * B를 계산해줌 else { //계산이 복잡한 경우 행렬 A를 4개의 행렬로 나눠줌 행렬 B를 4개의 행렬로 나눠줌 step1. M1부터 M7까지의 경우를 호출함 ex1. st..