반응형

학부 내용 정리/[ 2-2 ] 알고리즘 31

[ 알고리즘 ] Divide and Conquer : Quick Sort

1. Quick Sort Quick Sort의 알고리즘을 한번 보겠다. 1. 배열에서 하나를 pivot으로 설정한다. 2. 배열의 가장 앞을 가르키는 i와 가장 뒤를 가르키는 j로 설정한다. 3. i와 j가 만날때까지 아래의 과정을 반복한다. 3-1. i가 가르키는 값과 pivot이 가르키는 값을 비교해서 i가 더 작다면 pivot보다 더 큰 숫자를 만날때까지 i를 증가시킨다. 3-2. j가 가르키는 값과 pivot이 가르키는 값을 비교해서 j가 더 크다면 pivot보다 더 작은 숫자를 만날때까지 j를 증가시킨다. 3-3. 둘다 적절한 값을 찾는다면 i가 가르키는 값과 j가 가르키는 값을 바꾼다. 4. 반복문을 나왔다면 pivot값과 j가 가르키는 값을 교환한다. 5. 처음부터 j까지, j 다음부터 끝까..

[ 알고리즘 ] Tape Storage

1. Problem Definition N개의 데이터 아이템이 있다. 각 데이터 Di는 (Li ,Fi)로 이루어져 있다. Li은 데이터의 사이즈 , Fi은 사용 빈도수이다. 테이프에는 데이터를 한번만 쓸 수 있고, 읽는것은 무제한이다. 데이터를 읽으러 가는 모든 때의 시작점은 맨 처음이다. (데이터를 읽고나서 매번 맨 앞으로 돌아간다) 직관적으로 보면 크키가 클수록 뒤에 있고 자주 쓰는 것을 앞에 배치하면 좋겠다는 생각이든다. 하지만 자주 쓰는데 크기가 너무 크다면..? 이라는 애매한 상황이 생긴다, 2. Solution F/L 순서대로 저장하면 된다. (greedy) Proof 기대값은 빈도수 * 맨 앞에서 해당 데이터 까지의 L 라고 정의할 수 있다. 귀류법으로 증명을 해보겠다. Assume : Fi..

[ 알고리즘 ] Deadline Scheduling

1. Problem Definition J1, J2,...,JN 이라고 표기되는 N개의 job이 있다. 각 J는 (D,P) 로 쓰이는데, D는 deadline이고 P는Profit 이다. 1시간 단위의 타임슬롯이 있고 모든 일은 1시간이 소요된다 ex) (2,2) , (1,3), (1,1) 또, 이 문제는 아래의 가정을 따른다. 모든 deadlines은 N이하라고 가정한다. (N보다 크면 N으로 생각해도 됨) Job들은 내림차순으로 정렬되어있다. Deadline 이후의 일은 안나온다고 가정한다. 직관적으로 보면, 이익이 큰 것부터 최대한 뒤쪽에 배치하는 것이 효율적인 것을 알 수 있다. 최대한 뒤쪽에 두는것이 다른 Job들에게 방해가 될 가능성이 적어보이기 때문이다. 이것도 Greedy 알고리즘이다. 2...

[ 알고리즘 ] 최단거리 : Dijkstra Algorithm

1. Shortest Path 시작은 한군데지만 모든 목적지로 가는 shortest path를 다 구한다. shortest path의 모든 부분은 shortest path이다. 이는 여러가지 버전이 있다. 길이만 구하기 길이와 Path 구하기 가능한 여러개의 Path 구하기 2. Dijkstra Algorithm 이 알고리즘에 대해 설명해보겠다. 먼저 몇가지 정의를 하고가면 R: 정답이 확정된 노드들의 집합 B: Red Set에 있는 노드들만 거쳐서 갈 수 있는 노드들의 집합 Dmin : 최단거리 1) 먼저 시작 노드부터 각 노드까지의 weight를 dim에 기록한다. 연결이 되어있지 않으면 ∞라고 기록된다. 2) 시작 노드를 R에 넣고 아래의 과정을 반복한다 R 밖에 있는 Dmin(u)들 중 가장 작은..

[ 알고리즘 ] MST(2) : Kruskal Algorithm

1. Kruskal Algorithm 크루스칼 알고리즘의 기본 아이디어는 가장 작은 weight의 edge부터 하나씩 추가하는것이다. 단 사이클이 생기면 버리고 다음 weight의 edge를 확인한다. 위으 그림으로 예를 들어보겠다. 가장 작은 비용을 가진 edge는 1노드와 6노드를 잇는 10짜리 노드이다. 이것을 선택한다. 그 뒤로도 작은 순서대로 선택한다. 10, 12, 14, 16 이 다음으로 비용이 적은건 18이지만 18을 선택하면 사이클이 생기기에 그 다음인 22를 선택한다. 위와같이 사이클이 생기지 않게 작은 것들만 골라 spanning tree가 만들어지게 하면 된다. 증명 (proof by induction) 증명하기 전에 몇가지 가정을 이해해야한다. Tmst는 많은 정답 Edge set..

[ 알고리즘 ] MST(1) : Prim Algorithm

1. greedy Algorithm greedy 알고리즘은 선택을 반복하는 알고리즘들 중 비교적 간단하게 선택하고 선택한 것은 바꾸지 않는 알고리즘이다. 2. Minimum Spanning Tree (MST) Spanning Tree는 그래프의 모든 정점과 간선의 부분집합으로 구성된 부분 그래프이다. MST는 주어진 그래프의 연결 그래프들 중 엣지들의 비용이 최소가 되도록 하는 그래프이다. (단, 사이클을 생성X) 사이클이 있으면 안되는 이유는 사이클이 없어도 되기 때문이다. 사이클이 중 하나를 없애도 연결그래프는 유지가 된다. 게다가 비용까지 감소가 된다. 우리는 '최소'를 찾고 있으므로 사이클이 있을필요가 없다. 아니, 있으면 안된다. 3. Prim Algorithm 프림 알고리즘의 아이디어는 먼저 ..

[ 알고리즘 ] 자료구조 내용 복습

앞으로 자주 쓰일 자료구조들을 한번 복습해볼 것이다. 1. Array 동일한 type의 데이터를 연속된 주소에 저장하는 자료구조이다. 갯수를 미리 정해야하고 중간에 용량을 늘리기는 불가하다. 인덱스만 알면 데이터에 접근하기 슂다는 장점을 가지고있다. ex) A[7] = 400 + 7*4 = 428 Search, Delete, Insert 입장에서 효율이 좋지 않다. sorting이 되어있다면 Binary Search O(log N)가능하다. 2. Stack insertO(1) / DeleteO(1)만 제공한다. Search x Last in, First out 수식 계산에 사용 ex (3+7)*2 + (6-3)/5 3. Queue insert O(1) / Delete O(1)만 제공한다. Search x..

[ 알고리즘 ] 정렬(3) : Quick Sort

1. Quick Sort 이는 merge sort와 다르게 추가 배열을 만들지 않아도 된다. quick sort의 알고리즘은 아래와 같다. 1. 배열에서 어느 한 값을 pivot으로 설정한다. 2. pivot을 기준으로 왼쪽은 pivot보다 작게 오른쪽은 pivot보다 큰 숫자가 들어가도록한다. 3. pivot을 기준으로 왼쪽과 오른쪽을 나눠서 재귀를 실행시킨다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]

[ 알고리즘 ] 정렬(2) Merge, Recursive Merge Sort

1. Merge Algorithm sorting된 두개의 배열을 앞에서부터 각각 하나씩 비교하며 한 배열에 순서대로 합치는 알고리즘. 이 알고리즘의 단점은 하나의 배열을 새로 만들어야한다는 것이다 2. Recursive Merge Sort 위 코드를 간단히 설명해보자면 먼저 a[]와 똑같은 b[]를 만든다. h는 배열 전체 길이의 절반이다. b[0]부터 b[h-1] 까지 sort하는 함수를 한번 호출하고 b[h]부터 b[n-h-1]까지 sort하는 함수 하나를 호출한다. 끝까지 한 다음에는 마지막에 a로 sorting되며 합쳐진다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야..

[ 알고리즘 ] 정렬(1) : Selection Sort, Recursive Selection Sort

1. sorting의 조건 정확하게 sorting이 되기 위해서는 아래의 두가지 조건이 성립되어야한다. 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]n−1 일 때 sort 함수가 성공한다고 가정하자. 항상 재귀 실행 전에 a[0]에 최소값이 들어간 후 실행된다. 따라서 재귀로 들어가기 전부터 ∀x((x>0)→(a[0]a[0]

반응형