kkanalog

KMP 알고리즘을 확장 구현하고, 각 패턴에 따라서 탐색하고 패턴이 발생한 모든 위치를 찾을 수 있는지 확인. KMP 알고리즘의 동작에 대한 분석과 직접 구현한 코드에 대한 설명, 패턴에 따른 탐색의 분석이 포함됨. 2022.11.14 - [Algorithm] - [String Matching] KMP Algorithm ( 1 ) [String Matching] KMP Algorithm ( 1 ) KMP 알고리즘을 확장 구현하고, 각 패턴에 따라서 탐색하고 패턴이 발생한 모든 위치를 찾을 수 있는지 확인. KMP 알고리즘의 동작에 대한 분석과 직접 구현한 코드에 대한 설명, 패턴에 따른 탐색 kkastory.tistory.com Implementation readFile Function 주어진 파일을 읽..

KMP 알고리즘을 확장 구현하고, 각 패턴에 따라서 탐색하고 패턴이 발생한 모든 위치를 찾을 수 있는지 확인. KMP 알고리즘의 동작에 대한 분석과 직접 구현한 코드에 대한 설명, 패턴에 따른 탐색의 분석이 포함됨. String Matching Algorithm 스트링 처리 알고리즘 어떤 단어나 문장이 문서의 어느 곳에 있는지 찾고 싶을 때, 이때 대상 문서를 Text라 하고, 찾으려는 단어나 문장을 Pattern이라고 한다. 그리고 주어진 텍스트에서 패턴이 어디에 있는지 알아내는 것을 스트링 매칭( String Matching ) 이라고 한다. 텍스트 스트링이 컴퓨터에 저장될 때는 이진 스트링으로 변환되어 저장된다. 스트링에서는 알파벳에 속하는 문자들만 나타날 수 있다. 스트링 탐색 알고리즘에서 길이 ..

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 알고리즘의 동작에 대한 분석 및 구현 코드의 설명. 2022.11.14 - [Algorithm] - [정렬알고리즘] Selection Sort 선택 정렬 [정렬알고리즘] Selection Sort 선택 정렬 대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 알고리즘의 동작에 대한 분석 및 구현 코드의 설명. Selection Sort _ 선택 정렬 가장 작은 것을 선택해서 kkastory.tistory.com 2022.11.14 - [Algorithm] - [정렬알고리즘] Median of Three Quick Sort 중간 값 분할 빠른 정렬 [정렬알고리즘] Median ..

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 알고리즘의 동작에 대한 분석 및 구현 코드의 설명. Odd Even Merge Sort _ 홀짝 합병 정렬 시퀀스를 계속 반으로 분리하고 다시 merge 하는 정렬. 홀짝 합병 정렬 알고리즘은 병렬 프로세서에서 구현에 적합하게 만들어진 알고리즘이다. Bitonic Sort 와 마찬가지로 Merge Sort를 기본으로 하지만, Bitonic Sort 와 달리 오름차순, 내림차순의 bool 값이 들어가지 않고, 현재 원소 로부터 다음 원소까지 떨어진 거리에 대한 값이 들어간다. 이 값을 이용해 짝수 인덱스들끼리, 홀수 인덱스들 끼리 정렬을 한 후에 Merge 함수로 합한다. 또한 정렬 된 값을 저장하기 위한 새로운 저..

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 알고리즘의 동작에 대한 분석 및 구현 코드의 설명. Bitonic Sort _ 바이토닉 정렬 Conquer와 Combine을 거듭하며 bitonic sequence로 바꾼 후 정렬. Bitonic Sequence 란, 증가했다 감소하거나 혹은 감소했다가 증가하는 시퀀스를 말한다. 0~1 Sequence라고 하며, 일반적으로 local maximum 혹은 local minimum 값으로 생각한다. 예를 들어, 010 101 01 10 0 1 모두 Bitonic Sequece 이다. Bitonic 정렬에서는 Bitonic Sequence를 1 0 혹은 0 1 서브 시퀀스를 2개 이하로 포함하는 시퀀스라한다. Biton..

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 알고리즘의 동작에 대한 분석 및 구현 코드의 설명. Shell Sort _ 쉘 정렬 원래의 데이터를 여러 개로 분리하고, 분리된 데이터에서 삽입 정렬 하여 정렬 쉘 정렬은 삽입 정렬을 이용하여 여러 개의 서브 시퀀스로 나누어 각각 삽입 정렬을 반복하여 정렬하는 알고리즘이다. 이때 k 값을 줄여가며 여러 서브 시퀀스로 나누는데, 이 서브 시퀀스는 일정한 k 간격만큼 떨어진 원소들만 포함하여 만든다. 이때 k 값은 여러가지로 정할 수 있지만, 홀수 와 짝수가 번갈아 가면서 나오는, 증가 시에는 3*k+1, 감소 시에는 3/ k 로 감소 하는 k 값을 사용하는 것이 일반적이다. 이렇게 서브 시퀀스로 나누는 이유는 서로 ..

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 알고리즘의 동작에 대한 분석 및 구현 코드의 설명. Median of Three Quick Sort _ 중간 값 분할 빠른 정렬 Quick Sort _ 빠른 정렬 : 하나의 큰 데이터를 두개의 작은 데이터로 분할하여 정렬하는 방법이다. 빠른 정렬은 분할과 정복 기법을 사용한 정렬이다. 빠른 정렬은 pivot 값을 선정하여 pivot 값을 중심으로 데이터를 pivot 보다 작은 값이 모여있는 부분과 큰 값이 모여있는 두 부분으로 나누게 된다. pivot을 중심으로 정렬 후에는 pivot은 데이터 셋에서 정확한 자신의 자리를 찾아서 들어가게 된다. 이로 인해 나눠진 두 데이터 셋은 다시 새로운 pivot 값을 선정하고..

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 알고리즘의 동작에 대한 분석 및 구현 코드의 설명. Selection Sort _ 선택 정렬 가장 작은 것을 선택해서 제일 앞으로 보내기 . 선택 정렬은 정렬하기를 원하는 원소를 찾고 그것의 위치를 찾아 바꿔주는 원소 교환을 사용하여 정렬을 수행한다. 이에 따르면 가장 작은 원소는 첫번째 위치로, 그 다음 작은 원소는 두번째 위치로 들어가게 된다. 이러한 동작을 계속 반복하는 것을 선택 정렬이라고 한다. 선택 정렬 알고리즘은 n개의 원소 각각에 대해 n-1번의 비교를 해야한다. 따라서 비교 연산 횟수는 (𝑛(𝑛−1))/2 이고, 대입 연산 횟수는 3(𝑛 − 1) 이므로, 선택 정렬 알고리즘의 worst case 시..