목록3학년 1학기/알고리즘 (Algorithm) (27)
오래 못 할 짓 하지 않기
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/Aa3PI/btsHVrfXtzc/FDTZhSEdAgovBCuM4y5l0k/img.png)
지금껏 비효율적인 String matching이 많았다. 이렇게 ababac의 패턴과 ababaa를 비교하는 중에 Mismatching이 발생하면다시 한 칸만 가서 비교하는 것이 아니라 ab단위로 움직여도 되지 않겠나 생각할 수 있다. 한 칸만 움직여서 다시 비교하는 게 아니라 몇 칸 더 가서 다시 비교를 시작해도 된다는 것이다. 여기에서 abaa와 abab를 비교할 때 마지막에서 또 Mismatch가 발생한다.그럼 p를 한 칸만 옮겨서 비교하면 바로 MisMatch인 게 눈에 훤하다.다시 a랑 비교를 시작해줘야 하기 때문에 아래와 같이 이동해야한다. ※ 참고할 점Shift를 할 수 있는 숫자의 후보 중에서가장 조금만 Shift를 한다. s' + k = s + q 이다.둘 다 빨간 동그라미 a를 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bWnnK6/btsHUbRM8Wg/GilRW93z0vP511Ey22Klw1/img.png)
1 . Basic Algorithm2. Rabin - Karp Algorithm3. String matching with finite automata Basic AlgorithmString Matching 주어진 Text T에 Pattern P가 들어가는지 판단하는 것 T 의 길이는 nP 의 길이는 m ( 아마 n보단 작거나 같아야 할 것 같다. ) P가 T에 있다면 Valid Shift라고 한다. or Invalid 4번줄 do if 도 반복문으로 돌아야 한다. - 그에 대한 반복은 최소 1번 (첫 글자만 같은 경우) - 최대 m번 돈다 ( 다 같은 경우 ) 만약 m이 constant하다면? m = n/2라고 하면 O(n^2)이 나온다. 만약 aaab라는 패턴이 있을 때T에서 aaac이렇게 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/boC5XO/btsHLWWJUkQ/qkpz2w2kAgQ3dQHjzXo8uk/img.png)
Median = 중간값 ith Order static = i 번째로 작은 값 ex) Minimum = 1st order statistic Maximum = nth order statistic Median = 홀수면 (n+1) /2 , 짝수면 n/2 가볍게 생각해보기 좋은 것: n개의 숫자에 min과 max찾기> 'min과 max를 찾으려면 각각 n-1번 비교'총 2n-2'n-1번만 해서 두 개를' 구할 순 없을까? n이 짝수일 때, 한 쌍을 잡아두고, 거기에서 큰 걸 Max으로, 작은 걸 Min으로 해서두 쌍 중에 Min set와 Max set을 만든다. ex) 가위바위보 진 팀 , 이긴 팀 이렇게 나눈다면 각각의 set은 (n-2) / 2 가 되고, 그 안에서 각각 min과 max를 찾..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/d1lCug/btsHKOjfPvG/ihtfHFt1Ibz11rH4zTSgR0/img.png)
Counting sortCounting sort의 원리는 간단하다. 하나의 배열(A)을 Input으로 받고하나의 배열(B)에 Result를 담고하나의 배열(C)에 A에 원소별 갯수를 담는다. 원리는 각 숫자별로 갯수를 count하여원소별로 자리를 지정해주는 것 ex) 나보다 먼저 온 사람이 5명이면 내 자리는 6번째 psuedo code를 보자 1~2 : k = 해당 array에서 가장 큰 값 0~k까지의 index가 있는 array C를 만든다. 3~4 : A array를 돌면서, A array에 있는 각 숫자를 볼 때마다 C의 Index(=A에서 읽은 값) 에 +1해준다. 결과A 에서 a라는 item의 갯수= C[a] 의 값 5~6 : 2번째 인덱스부..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/b6PkDl/btsHKR0w30E/fSFAeHlTlozekEpto6kEwk/img.png)
지금껏 우리가 배운 Sort는 Comparison sort이다. Comparison sort = @번째 Index와 비교해서 자리를 바꾸는 sort 이런 Comparison sort의 Time complexity는 오메가(n lg n) = 최소 n log n 이상은 시간이 걸린다. 이렇게 n개의 item이 있을 때 sort를 한다고 했을 때 1 : 2 번째 인덱스를 비교 = 1번이 크면 오른쪽, 2번이 크면 오른쪽으로 가는 플로우다. - leaf의 수 = item의 permutation- algorithm의 running time = Path의 length와 관련있다.- Worst - case running time = height of tree 따라서, 비교를 통해서 sort를 하는 경우에는 T..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/774jT/btsHEZYyGU6/ua8swSo9rDc57IXKTabK31/img.png)
: Sort에서 Divide and Conquer 를 사용하는 알고리즘 구간을 정하고 그 안에서 sort한다. sort의 기준은 Pivot임. 이번에는 Pivot을 배열의 가장 마지막 원소로 지정한다. x 가 pivot이라고 했을 때,왼쪽은 x이하 오른쪽은 x이상 으로 분류한다. 옛날에 배웠던 건 Pivot element가 pivot이거나 , 처음 중간 끝 값 중에 가운데를 pivot으로 했다. A = arrayp = 첫번째 인덱스r = 마지막 인덱스 이번에는 가장 오른쪽에 있는 element를 pivot으로 정한다.검사는 → 이렇게 한 방향으로만 한다. 3번째 줄 : 그럼 처음부터 r-1까지만 검사하면 된다. 4,5,6번째 줄 : 만약 현재 Index의 값이 Pivot보다 작으면, ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/8e6RH/btsHvsAXRZl/h2XqKLgk80acUk0y015Pi1/img.png)
Floyd Algorithm: All Pairs Shortest Path 를 구하기 위한 알고리즘이다. From all to all Dense graph는, Edge의 개수 = O(V^2)인 경우의 graph이다.E에 V^2를 대입하면 과 같다 ● Floyd Algorithm 사용 조건 - Negative Edge 는 가능 - 하지만 Negative Weight cycle은 안 된다. - DP로 구현한다. = Optimal Substructure 적용 가능 알아야 하는 개념- Intermediate Vertex : i에서 k까지 가는 path에 포함되는 Vertex 단, 한 번만 나올 수 있다. DP로 생각해보면 1 ~ ... k-1까지 가는 최단 경로를 찾았다면 k까지 갈 땐 k-1까지..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bijIOv/btsHuJ9ql1N/TfhGGgoqsrNkxqiNmhk2f1/img.png)
Dijkstra Algorithm ( From all to all )● 조건: Negative weight인 edge가 없다면, Bellman-Ford보다 성능이 좋다. ● 구현법- Queue에 담긴 Vertex 를 하나씩 꺼내면서 Tree를 키운다.- Queue는 , d[v] 가 낮은 순서대로 Prioirity queue를 만든다. Minimum shortest path인 것을 select한다.u라는 vertex를 S에 넣은 뒤 , u와 인접한 모든 node를 Relaxation 시킨다. 1 : 초기화2,3 : set을 비우고, Q에 vertex들을 넣는다. 4 ~ 8: Q에 vertex가 비어있지 않았다면, vertex하나를 꺼내고, 그걸 S에 넣는다. 7~8 : ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/xK8Xg/btsHodRiPV7/GKSGtUrRLzFfc6KGmP2lRK/img.png)
u에서 v까지 가는 Shortest path의 Weight은 [ Path가 존재한다면 ]u → v까지의 path의 weight의 최솟값을 구한다. [ Path가 존재하지 않는다면 ]무한대 길 찾기의 유형 1. Single source shortest path : 하나의 Vertex에서 다른 모든 Vertex로 가는데 가능한 최단 경로 (이거 먼저 배울거임) ● 알고리즘 Bellman-Ford AlgorithmIn DAGDijkstra's Algorithm 2. All- Pair shortest path : 모든 Vertex에서 모든 vertex까지 가는데 가능한 최단 경로 ● 알고리즘 Floyd - Warshall Algorithm (다음 장에서 배움) Shortest path ● 특징..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bmd9RO/btsHniLfoRa/bKz1Sz0NVCe3SVD3VuSNl0/img.png)
참고https://min-h-study-review.tistory.com/54Minimum Spanning Tree 조건: Connected + Undirected + Non-Cycled + Weighted graph 이 중에서도 우리는 모든 Vertex를 지나고 , Total Weight가 최소인 Tree를 구할 것이다. ● 특징 )1. n개의 vertex / n-1개의 Edge2. MST 가 Unique하지 않을 수도 있음.(a)에 대한 MST는 b,c 두 개가 있다. ● MST를 찾는 알고리즘 :1. Kruskal Algorithm ( 가장 Weight이 낮은 Edge부터 하나하나 가져옴 ) 2. Prim Algorithm ( root Vertex 에서부터 인접한 Edge중에서 Weight..