알고리즘 (54) 썸네일형 리스트형 알고리즘6 Djikstra Algorithm Djikstra Algorithm 유명한 Shortest Path의 정답. 프림 알고리즘과 유사하다. 시작은 한군데지만 모든 목적지로 가는 shortest path를 다 구한다. shortest path의 모든 부분은 shortest path이다. 대부분 path를 구하는 것이 아니라 path의 길이만을 구한다. => 길까지 구하는 것으로 금방 바꿀 수 있다. 심지어 path가 여러 개일때 모든 path를 다 찾을 수 있다. 3단계로 나눠서 얘기하면 이를 설명할 수 있음 일단 1단계부터 설명 => 2단계로 바꾸고 => 3단계로 바꿀 것임 (1단계에서 왜 이게 답을 찾느냐가 어려움) G: 입력 그래프 n: 노드 갯수 R: 빨간 노드 집합 V0: source node dmin: 노드에 써진 숫자 빨간노드와 .. 알고리즘5 - Kruskal Algorithm 내 프로그램이 정확하다는 말은 언제든지 할 수 있어야 한다. Prim알고리즘은 한 노드에서 시작해서 퍼져 나간다. 엣지를 추가한다는 점에서 유사하다. Kruskal Algorithm는 전체 그래프에서 가장 작은 엣지를 추가한다. 1,2,3을 추가한 상태이고 이제 4를 추가해야 하지만 두 개의 4 모두 추가하면 사이클이 된다. PASS 프림 알고리즘에서는 이미 들어간 노드와 안들어간 노드를 연결하면 사이클이 생기지 않았다. Kruskal 에서는 어떻게 사이클을 판단할 것인가? 같은 덩어리를 연결하면 사이클이 생긴다. 연결이 안된 노드는 하나의 덩어리라고 생각 이러면 답을 찾느냐? 성능은 어떻게 되는가? 정확성 프림 알고리즘과 마찬가지로 정답은 여러개일 수 있다. 정답 중 하나를 찾는다는 것을 증명한다. 하.. 알고리즘4 Greedy Algorithms - Prim Algorithm 알고리즘을 작전별로 보자! Greedy AlgorMinimum - Spanning Treeithms 답을 찾기 위해 선택을 반복하는 알고리즘 중 비교적(?) 간단한 방법으로 선택하고 선택한 후 바꾸지 않는 알고리즘 그리디 작전을 쓴다면 가장 짧은 쪽으로 계속 간다. B>A>C>D...?? 지금은 안된다. 물론 풀리는 예도 있다. selection sort도 그리디였다. 가장 작은 걸 앞으로 보낸다. 뒤돌아보지 않는다! undirect graph에서 Minimum Spanning을 정의할 수 있다. node가 5개, edge 4개 고르면 tree가 된다. (node n개인 tree는 edge가 n-1개) Tree: Connected Acyclic Graph 모든 노드가 연결되어 있고 사이클이 없는 그래프 .. 알고리즘3-2 자료구조 리뷰2 AVL Tree BST가 보통의 경우에 성능이 좋지만, 특수한 경우에 안 좋다. = > Balanced Tree 최악의 경우에도 O(logN) 왼쪽, 오른쪽 subtree의 높이 차이가 1이하 L-R = 0, 1, -1 중에 하나 따라서 위의 오른쪽 그림은 안됨 루트에서 갈 수 있는 제일 짧은 길과 제일 긴 길 차이가 2배 이하다. 중간까지는 tree높이에 비해서 노드 수가 많기 떄문에 => 노드 갯수에 비해서 tree 높이가 작다. => O(log n) 2-3 Tree key가 1개 있고 child가 2개 있는 노드 key가 2개 있고 child가 3개 있는 노드를 섞어서 만든다. AVL tree와 결국 비슷한 얘기지만 이게 더 직관적이다. 삽입할땐 key와 key사이 가운데로 삽입되어서 위로 올라갈 .. 알고리즘3 자료구조 리뷰 이런 알고리즘이 이런 자료구조를 쓴다~를 알기 위해서! Array 연속된 주소, 동일한 type 갯수를 미리 잡아둬야 한다. 용량을 늘리려면 다른 메모리에 옮겨야 한다. int A[10] 은 int가 4byte이므로 총 40byte A:400 404 408 412 ... A[7] = 400 + 7*4 = 428 이런식으로 바로 찾아갈 수 있음 Search, Delete, Insert 입장에서 좋은 효율은 아니다. sorting이 되어있다면 Binary Search O(log N)가능하다. Stack insert / Delete만 제공한다. Search x =Push O(1) / Pop O(1) Last in, First out 나중에 들어간 게 먼저 나온다. 수식 계산에 사용 ex (3+7)*2 + (6.. 알고리즘2-2 재귀적 선택 정렬 , 합병정렬 , 퀵소트 재귀적 선택 정렬 loop보다 살짝 더 느리다. 이해하기는 더 쉽다. 전체를 살펴보고 제일 작은 숫자를 찾는다. 첫번째 값과 제일 작은 숫자를 바꾼다. 제일 작은 숫자를 빼고 나머지를 sorting하면 전체가 sorting되는 것 그래서 그 뒤의 배열을 재귀적으로 보내준다. 재귀이므로 sorting이 잘된다고 믿으면 된다. proof by induction n-1일때는 재귀 호출이기 때문에 그냥 믿는다. n일때 a[0] 0 a[1]은 무엇인가? 원래 a[1]~a[n-1] 중 한 값이 a[1]일 것이다. (집합조건은 안 깨지기 때문에) 우리가 알 수 있는 사실은 a[1]이 뭐였든 간.. 알고리즘2 선택 정렬 증명 O(logN) 가장 대표적인 예 Recursive Binary Search 이 식은 사실이다. *정확하게 고치자면 이렇게 표현해야 하지만 annotation으로 쓸 것이기 때문에 괜찮음 T(n) 알고리즘1-2 수학적 귀납법과 재귀 수학적 귀납법의 기본형: p(1)이 참이고 P(n-1) -> P(n)이 참이면, P(n)은 모든 자연수 n에 대해서 참이다. n은 짝수다. n은 2보다 크다. BASE가 참이고 STEP이 참인 것이 증명됐다. P(1) -> P(2) P(2) -> P(3) ... P(N-1) -> P(N) 으로 짐작할 수 있다. (전체가 "참"이라는 사실만 이용) 수학적 귀납법의 강한 형태: p(1)이 참이고 P(1)^P(2)^...^P(N-1)->P(N)이 참이면, P(n)은 모든 자연수 n에 대해서 참이다. P -> Q 의 의미? 1. 참 참 참 2. 참 거짓 거짓 3. 거짓 참 참 4. 거짓 거짓 참 ex) 100점 받으면 -> 치킨 사줄게 1. 100점 받아서 치킨 사줌 (참 = 약속 지킴) 2. 100점 받았는데.. 이전 1 ··· 3 4 5 6 7 다음
