Study Blog

리스트란? 데이터 구조의 하나로, 데이터를 일직선으로 나열한 형태를 가지고 있음 데이터 추가나 삭제는 쉽지만, 원하는 데이터에 접근하려면 시간이 많이 걸림. = 삽입과 삭제가 빠름 연결 리스트를 단순한 배열로 구현하면 데이터를 삽입, 삭제할 때마다 데이터를 옮겨야 하므로 비효율적인 문제가 발생한다. 이 문제를 해결하기 위해 아래에서는 포인터를 이용하여 연결 리스트를 구현할 것이다. 위 그림이 리스트의 개념도이다. 여기서는 세 개의 문자열 'Blue', 'Yellow', 'Red'가 데이터로 저장되어 있다. 또한, 각 데이터에는 '포인터(Pointer)'가 있으며, 다음 데이터의 메모리 위치를 가리키고 있다. 'Red'는 마지막 데이터이므로 'Red'의 포인터는 아무것도 가리키지 않는다. 연결리스트에서 사..

보이어 무어법의 특징 이 알고리즘을 고안한 보이어와 무어의 이름을 따서 BM법이라고도 함 KMP법보다 효율적이어서 실제 문자열 검색에서 주로 사용 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정함 시간복잡도는 최악의 경우라도 O(n)이고 평균 O(n / m)이다. 보이어 무어법은 배열을 1개만 사용해도 충분히 빠르다. 보이어 무어법의 진행 과정 위 그림처럼 패턴에 포함되지 않는 문자를 텍스트에서 발견하면 그 위치까지는 건너뛸 수 있다. 그러므로 패턴을 비교하는 1~4번째 과정을 생략하고 패턴을 오른쪽으로 한번에 4칸 밀면 다음 그림과 같이 된다. 여기서 패턴의 마지막 문자 "C"를 텍스트와 비교하면 일치하므로 1칸 ..

KMP법이란? Knuth-Morris-Pratt법의 줄임말로 이 알고리즘을 고안한 크누스, 모리스, 프래트의 이름에서 따온 용어이다. 브루트 포스법은 일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검사를 수행하지만, KMP법은 검사 결과를 효율적으로 사용한다. KMP법 알아보기 1. 텍스트 "ZABCABXACCADEF"에서 패턴 "ABCABC를 검색할 때 KMP법 알고리즘을 생각해보면 다음과 같다. 먼저 위의 그림처럼 텍스트와 패턴의 첫 문자부터 차례로 검사를 수행한다. 텍스트의 첫 문자 "Z"는 패턴에 포함되지 않는 문자이므로 일치하지 않는다. 2. 이제 패턴을 오른쪽으로 1칸 민다. 그럼 위와 같이 비교하는데, 패턴의 앞쪽부터 차례로 검사를 수행해가면 패턴의 마지막 문자 "D"가 텍스트의 "X..

문자열 검색이란? 문자열 검색은 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것 예를 들어 문자열 "STRING"에서 "IN"을 검색하면 성공하지만, 문자열 "QUEEN"에서 "IN"을 검색하면 실패함 문자열 검색에서 검색되는 쪽의 문자열을 텍스트(text), 찾아내는 문자열을 패턴(pattern)이라고 함 브루트 포스법이란? 문자열 검색 알고리즘 중 가장 기초적이고 단순한 알고리즘. 선형 검색을 단순하게 확장한 알고리즘이라서 단순법이라고 불린다. 텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트 포스법으로 검색하는 순서는 다음과 같이 진행된다. 1. 텍스트의 첫 문자 "A"에서 시작하는 문자 3개가 패턴 "ABC"와 일치하는지 검..

힙 정렬이란? 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘 최소값이나 최대값을 빠르게 찾기 위해 완전 이진 트리를 이용하는 트리구조, 형제 트리의 대소관계가 일정하지 않은 것을 부분 순서 트리라고도 함 '부모의 값이 자식의 값보다 항상 크다 or 작다'는 조건을 만족하는 완전 이진 트리(왼쪽부터 자식 노드를 추가하여 상태를 유지하는 것) ⭐️그림으로 이해하는 용어 정리 최대 힙: 큰 값이 위로 오게끔 정렬(아래 그림 참고) 최소 힙: 작은 값이 위로 오게끔 정렬(아래 그림 참고) 이진: 부모가 가질 수 있는 자식 노드의 최대 개수가 2개인 것(아래 그림 참고) 루트: 트리의 최상단 노드(아래 그림 참고) 리프노드(단말노드): 트리의 최하단 노드(자식이 없는 노드) 힙의 원소를 배열에 저장하는 순서 ..