전체 글657 KMP 알고리즘 만든 사람이 Knuth, Morris, Pratt 여서 Knuth–Morris–Pratt(KMP) 알고리즘이라 합니다. 문자열 알고리즘 중 하나로 문자열 에서 다른 문자열을 검색하는 알고리즘입니다. 단순하게 문자열(S) "ABCABDABCABC" 에서 문자열(P) "ABCABC"를 검색해봅시다. S, P 모두 가장 앞에서부터 같은지 비교합니다. (1) ~ (5) 는 문자가 같기 때문에 다음 문자를 비교합니다. (6) D, C는 다르기 때문에 문자열 P를 찾을 수 없습니다. 이제 S 문자열의 인덱스 1부터 다시 비교합니다. (1) B, A는 다르기 때문에 문자열 P를 찾을 수 없습니다. 문자열 P를 찾을 때까지 이를 반복합니다. 문자열 S 인덱스 6부터 시작하는 부분문자열에서 문자열 P를 찾을 수 있었습니.. 2020. 2. 9. [2020 TODO] 중간점검 (1) 2020 TODO 리스트 중간점검 겸 나름의 점수를 매겨보았다. 마라톤 3번 참여 (3/10) 헬스장에서 런닝머신 3km 정도 꾸준히 달리고는 있다. 그런데 너무 천천히 뛴다는 생각이 듬. 길게 뛰어봤자 15분 정도..? 내가 더 할 수 있는데 이정도 밖에 안하는 거면 연습량을 늘려야 하는데, 기본 체력이 부족해서면 다른걸 해야 되는 걸까나. 주 3일 3km 30분 미만으로 달리기를 하고는 있는데, 주 5일로 변경해야겠다. 주 3일은 좀 적은거 같음. 주 5일 3km 해보고 더해도 괜찮겠다 싶으면 목표 시간을 줄이거나 목표 거리를 늘려야겠다. 4월까지 연습만이 살 길이다. 5kg 감량 (4/10) 먹는 양이 애초에 그렇게 많지 않아서 먹는건 괜찮다고 생각했는데 아니었다. 영양소 부족이다. 흐헝헝 식이섬유.. 2020. 2. 8. FILA x 탬탬버린 콜라보 옷 도차악 예판한거 드디어 왔다. 이쁘자나. 반팔도 살걸 그랬다. 2020. 2. 7. 크루스칼 알고리즘(Kruskal’s algorithm) 신장 트리(Spanning Tree)란, 연결 그래프의 부분 그래프이며 모든 정점과 간선의 부분 집합으로 구성되는 트리입니다. 이 때, 모든 정점에는 하나 이상의 간선에 연결되어 있어야 합니다. 최소 신장 트리(Minimum Spanning Tree. MST)는 만들 수 있는 신장 트리 중에서 간선 비용의 합이 최소인 신장 트리를 말합니다. MST의 간선 개수는 정점의 수 - 1개입니다. 간선들의 비용 합이 최소인 경우는 여러 개 나올 수 있으므로 하나 이상 존재합니다. 이러한 MST를 만드는 대표적인 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 선택하여 확장하는 방법이고, 크루스칼 알고리즘은 간선을 선택하여 확장하는 방법입니다. 이번 포스팅에서는 크루스칼(Kruska.. 2020. 2. 6. 프림 알고리즘(Prim's algorithm) 신장 트리(Spanning Tree)란, 연결 그래프의 부분 그래프이며 모든 정점과 간선의 부분 집합으로 구성되는 트리입니다. 이 때, 모든 정점에는 하나 이상의 간선에 연결되어 있어야 합니다. 최소 신장 트리(Minimum Spanning Tree. MST)는 만들 수 있는 신장 트리 중에서 간선 비용의 합이 최소인 신장 트리를 말합니다. MST의 간선 개수는 정점의 수 - 1개입니다. 간선들의 비용 합이 최소인 경우는 여러 개 나올 수 있으므로 하나 이상 존재합니다. 이런 MST를 만드는 대표적인 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 성택하여 확장하는 방법이고, 크루스칼 알고리즘은 간선을 선택하여 확장하는 방법입니다. 이번 포스팅에서는 프림(Prim) 알고리.. 2020. 2. 6. 세그먼트 트리(Segment Tree) 세그먼트 트리는 구간의 값을 저장하는 트리입니다. 1~N인 수열이 있을 때, "인덱스가 a~b인 수들의 합을 구하고 싶다." 혹은, "a~b번째 수들 중 최소 값이나 최대값을 구하고 싶다." 같은 경우 사용합니다. 세그먼트 트리는 이진 트리 모습을 가지며 자식 노드는 부모 노드의 범위를 반 씩 가지고 있습니다. 즉, 부모 노드가 1~5까지의 구간합을 가지고 있다면 자식 노드의 왼쪽 자식은 1~3의 구간 합을 가지고 오른쪽 자식은 4~5까지의 구간 합으로 나눠가집니다. 수열의 크기(N)가 5인 수열 A = {1, 2, 3, 4, 5}의 구간 합을 구하고자 할 때 사용하는 세그먼트 트리를 생성해 봅시다. 인덱스(i)는 접근이 쉽게 0이 아닌 1부터 시작하였습니다. 처음 상태의 세그먼트 트리는 다음과 같습니다.. 2020. 2. 2. 이전 1 ··· 65 66 67 68 69 70 71 ··· 110 다음
