자료구조와 알고리즘 ft. 수업/자료구조 정리

2. 버블 정렬 (Bubble Sort)

1. 정렬 알고리즘의 개요

Reference : 이것이 자료구조+알고리즘이다 with C언어 정렬 (Sorting) 정해진 기준에 따라 데이터를 순서대로, 그리고 체계적으로 정리하는 알고리즘 정렬의 목적은 '탐색' 궁극적인 목적은 물건이나 데이터를 쉽게 찾고자 하는 데 있다 고전 알고리즘 버블 정렬, 삽입 정렬, 퀵 정렬

1. 문자열 탐색 알고리즘의 개요

Reference: 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어 문자열 탐색 알고리즘 : 특정 문자열에서 특정 문자열을 찾는 알고리즘 => 많은 종류의 문자열 탐색 알고리즘이 개발되었다 ex) Naive, DFA, KMP 문자열 탐색 알고리즘에 쓰이는 용어들 본문 (Text) : 탐색 대상이 되는 문자열을 의미 패턴 (Pattern) : 탐색어를 의미 이동 (Shift) : 본문에서 탐색 위치를 옮기는 일

6. 보이어-무어 알고리즘

5. KMP 알고리즘

Reference: - 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어 - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 KMP 알고리즘 KMP (Knuth-Morris-Pratt) 알고리즘 : '고지식한 탐색' 처럼 탐색 위치를 본문 왼쪽부터 시작해서 오른쪽으로 옮겨가며 문자를 직접 비교하는 방식으로 동작 ==> 하지만 요령을 눈곱만큼도 부리지 않는 고지식한 탐색과 달리, KMP 알고리즘은 비교할 필요 없는 부분은 지나치고 비교가 필요한 부분만 비교를 수행하는 똑똑한 알고리즘 ==> '어떤 정보'가 무엇인지와 이 정보를 '어떻게 활용하는가'에 대한 것 KMP 알고리즘의 동작 방식 어느 문자..

4. DFA 알고리즘

Reference : - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 DFA 알고리즘 Naive 알고리즘에서 각 숫자에 대한 표기를 좀 더 하는 방식이다. 첫 글자와 일치하는 곳이 발견되면 그곳에 1을 표기하고, 그 이후로도 일치할 경우 1씩 더 증가시키면서 표기한다. 만약 표기하려는 수가 이미 표기된 수보다 작다면 표기할 수 없다. abcabcd에서 abcd를 찾는다면 abcabcd에는 1231234가 표기될 것이다. 찾으려는 글자의 길이 값이 표기된 갯수가 정답의 갯수가 될 것이다. 이에 대한 경우의 수를 표로 만들어 저장하고, 이를 활용한다. 다음은 abcabcd를 찾을 때 경우의 수 표이다. 위 숫자의 ..

3. 카프-라빈 알고리즘

2. Naive 알고리즘 (고지식한 탐색 알고리즘)

Reference: - 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어 - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 고지식한 탐색 알고리즘 (Naive Search or Brute Force Search Algorithm) : 본문의 앞에서부터 끝까지 차근차근 탐색하는 알고리즘 본문 : 'ABCABACDC' 패턴 : 'BA' => 이 알고리즘은 이름 그대로 요령 부리지 않고 우직하게 일하는 일꾼처럼 동작한다 본문 길이 : N 패턴 길이 : M 패턴을 찾기 위해 최악의 경우 N x M 번의 비교를 수행 => 굉장히... 느림 일치하는 경우 해당 경우의 끝나는 값에 1을 표기한다 1의 갯수..