개발하는 멍정이야기

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. 하위 노드 방문(왼쪽 -> 오른쪽) //..

Time for Moving Valid Pages 그렇다면. erase하기 위해서 옮기고 지우고 해야하는데 얼마나 시간이 걸릴까? The Intrinsic Latencies of Flash Memory 대략적으로 읽기는 25ns ~ 65us 쓰기는 300us ~ 1.5ms 지우기는 2ms ~ 5ms Time for Reclaiming a Victim Block 피해 블록 회수 시간. 읽기 : 40나노초 * 200pages = 8밀리초 쓰기 : 800나노초 * 200pages = 160밀리초 지우기 : 3밀리초 * 1block = 3밀리초 Time for Reclaiming Multiple Victim Blocks 여러개의 블럭을 한 번에 쓰고 지울 수 있지만 쓰고 지우는걸 동시에는 못한다는걸까? ?? I..

Consequence of Out-of-Place Updates 덮어쓰기가 안되기 때문에 clean page에 값을 넣다보면 언젠가 자리가 없어질 것이다. -> 그럼 write가 안되니까 invalid를 지우자! How about Erasing Invalid Page? invalid값을 다 지워버리자! -> but erase는 block단위이기 때문에 불가능! < 읽기쓰기 기본 단위는 page지만 삭제는 block! What of a To-Be-Erased Block Holds Valid Page? - block단위로 삭제할 수 있으니 valid값을 새로운 block에 넣고 전부 invalid해진 block을 지워버리자! Valid Page Movement 새로운 block에 값을 옮겼다면 mapping..

Flash Translation Layer(FTL) Host system과 I/O를 처리할 때 SSD는 flash memory의 특성이 있기 때문에 HDD와 다른 방식으로 처리해야한다. flash memory 특징 - Asymmetric operation units (reads/writes가 blocks단위로 지우고 page 단위로 작성 - Program-after-erase property(덮어쓰기가 안됨) - Limited flash memory lifetime(수명이 제한적임-> 아마 wear leveling관련?) Various Functionalities(Modules) of FTL - Address mapping - Garbage collestion(GC) - wear leveling //fe..

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 : 전부 해보기 이런 방법에 대한 시간..