전체 글 검색 결과

27 개의 검색 결과가 있습니다.

전공/C++

알고리즘 : 스트링 탐색 #2 (KMP 알고리즘)

지난 시간에는 한 글자씩 대조하여 스트링을 탐색하는 직선적 알고리즘을 알아보았습니다. 이번에 소개할 KMP 알고리즘은 이와 달리 패턴에서 얻은 어떠한 정보를 바탕으로 텍스트를 껑충껑충 넘어가며 패턴과 비교를 진행하는데, 어떻게 진행되는 지 알아보도록 하겠습니다. 위의 그림과 같이 "ABCDABCDABEF" 에서 "ABCDABE" 를 찾으려 합니다. 지난 시간에 알아본 직선적 알고리즘으로 탐색하다 보면 마지막 C, E에서 불일치가 일어나죠. 그렇다면 아래와 같이 딱 한 칸만 이동하여 또 비교를 진행합니다. 이렇게 진행하면 시간낭비가 된다는 걸 그냥 봐도 알 수 있습니다. 이런 시간낭비를 개발자 형님들은 그냥 두고 볼 수가 없었죠. 결국 더 간결하고 시간이 훨씬 적게 드는 탐색 알고리즘을 발견했으며, 발견자..

2022. 6. 4. 02:49

전공/C++

알고리즘 : 스트링 탐색 #1 (Naive, 직선적 알고리즘)

이 페이지에서 "KMP" 라는 글자를 찾고 싶다면 어떻게 해야할까요? Ctrl + F 를 눌러서 "KMP"를 검색하면 됩니다. 이렇게 글에서 특정 단어를 탐색하는 과정을 지금부터 소개할 텐데요, 바로 스트링 탐색 알고리즘입니다. 직선적 알고리즘 "Choi Yena is cute." 라는 문장에서 cute를 찾으려고 할 때, 어떻게 해야 할까요? 우선 여기서 "Choi Yena is cute."는 Text, "cute"는 Pattern이 라고 부릅니다. 각 스트링의 글자 갯수를 N, M이라 할 때, t[N] 배열과 p[M] 배열을 대조하면서 텍스트 내의 패턴을 찾는 것이 스트링 탐색 알고리즘이죠. 여기에는 대표적으로 네 가지 알고리즘이 있습니다. 1. 직선적 알고리즘 (Naive Search) 2. KMP..

2022. 5. 17. 02:41

전공/C++

알고리즘 : 정렬 #3 (Shell Sort, Heap Sort)

지금까지 대표적인 정렬 다섯개에 대해 알아보았습니다. 이번엔 좀 더 응용된 정렬인 Shell Sort(쉘 정렬), Heap Sort(힙 정렬)에 대해 알아보겠습니다. Shell Sort (쉘 정렬) Shell Sort(쉘 정렬)는 Insertion Sort(삽입 정렬)를 변형한 정렬입니다. 먼저 Shell sort에는 "gap" 이 존재합니다. 이 gap을 미리 정해 두고, gap만큼 벌어진 것들 끼리 삽입 정렬을 해주는 겁니다. 그림으로 보겠습니다. 다음 배열 a[]를 정렬하려 하는데, gap을 1 ← 4 ← 13 으로 정했다고 합니다. 무슨 뜻일까요? 일단 첫 시작은 gap=13 이라니까 한번 보도록 합시다. 그러고선 앞서 정한 gap만큼 건너 뛴 원소들끼리 삽입 정렬을 해줍니다. 이 때 3번째 원소..

2022. 4. 20. 00:24

전공/C++

알고리즘 : 정렬 #2 (Mergesort, Quicksort, Stable)

이번에 알아볼 것은 Mergesort(합병 정렬), In-place Quicksort(제자리 퀵 정렬)이며, 정렬의 Stable함을 소개하며 마치겠습니다. Merge Sort (합병 정렬) Mergesort에 들어가기 전, 저번에 복잡도의 점화식에 대해 소개할 때 이상한 코드 하나를 가져왔었죠? BinarySearch(a[], key, left, right) // a[mid] = key인 인덱스 mid를 반환 if (left a[mid] : return (BinarySearch(a, key, mid+1, right)); } } else return -1; // key 값이 존재하지 않음 end BinarySearch() 바로 이 코드입니다. 그 때 말했듯 이 함수를 실행하면 절반짜리 입력으로 재귀호출을 ..

2022. 4. 19. 09:04

전공/C++

알고리즘 : 정렬 #1 (Bubble Sort, Insertion Sort, Selection Sort)

정렬 알고리즘(Sorting Algorithm)은 알고리즘 설계의 처음이자 마지막입니다. 정렬 알고리즘은 n개의 숫자가 주어졌을 때 이를 기준에 맞게 정렬하는 알고리즘으로, 개발자들은 지난 100년간 이 정렬 알고리즘의 실행 시간을 줄이기 위해 노력해왔습니다. 오늘 소개할 정렬은 제일 기본적인 정렬 세 가지입니다. - Bubble Sort (버블 정렬) - Insertion Sort (삽입 정렬) - Selection Sort (선택 정렬) 위 세 가지 정렬은 모두 구조가 간단하며 O(n²)의 시간 복잡도를 가집니다. 따라서 잘 쓰이지는 않지만 다른 정렬의 기초가 되죠. Bubble Sort (버블 정렬) 먼저 Bubble Sort(버블 정렬) 입니다. 이러한 크기 7 짜리의 배열 S가 있고, 우리는 이..

2022. 4. 19. 05:00

전공/C++

알고리즘 : 마스터 정리(Master Theorem)

어찌저찌 점화식을 구했는데, 이를 전개해서 복잡도를 알아내는 것도 쉽지만은 않다는 것을 저번 시간에 보았습니다. 하지만 우리는 언제나 방법을 찾아냅니다. 바로 "마스터 정리(Master Theorem)"입니다. T(n) = aT(n/b) + f(n) 꼴의 점화식이 있다고 합시다. 물론 여기엔 조건이 붙습니다. 1. f(n)은 asymptotically positive function 이어야 함. 2. a≥1 and b>1 의 상수여야 함. 3. the regularity condition that af(n/b) ≤ cf(n) for some constant c < 1. 음... 2번 빼고는 무슨 말인지 도통 모르겠네요. 대충 설명을 드리자면, f(n)은 positive function이어야 함, 즉 음수..

2022. 4. 18. 08:14