본문 바로가기
728x90

알고리즘47

해시법 - 정렬된 배열에 새로운 값을 추가하려면? 1. 삽입할 위치를 이진검색법으로 조사 2. 삽입할 위치 이후의 모든 요소를 뒤로 하나씩 이동 3. 새로운 값 대입 => 복잡도: O(n) 해시법: 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것 해시 함수(hash function): 키 값을 가지고 해시 값을 만드는 과정 해시 값(hash value): 배열의 키 값을 배열의 요소 개수로 나눈 나머지 등 해시 함수를 거친 값 해시 테이블(hash table): 해시 값을 정리한 표 버킷(bucket): 해시 테이블의 각 요소 충돌(collision): 저장할 버킷이 중복되는 현상 해시 함수는 가능하면 해시 값이 중복되지 않도록 고르게 분포된 값을 만들어야 함 충돌에 대한 대처: 체인법: 같은 해시 .. 2023. 9. 25.
트리(Tree) 트리: 데이터 사이의 계층 관계를 나타내는 자료구조 노드(node), 가지(edge) 루트(root): 가장 윗부분에 위치하는 노드 리프(leaf): 가장 아랫부분에 위치하는 노드 (=끝 노드, 바깥 노드) 안쪽 노드(internal node): 리프를 제외한 노드 자식(child), 부모(parent), 형제(sibling) 조상(ancestor): 어떤 노드에서 가지로 연결된 위쪽 노드 모두 자손(descendant): 어떤 노드에서 가지로 연결된 아래쪽 노드 모두 레벨(level): 루트로부터 얼마나 떨어져 있는지에 대한 값. 루트는 0 차수(degree): 노드가 갖는 자식의 수 높이(height): 루트부터 가장 멀리 떨어진 리프까지의 거리 널 트리(null tree): 노드, 가지가 없는 트리.. 2023. 9. 25.
원형 이중 연결 리스트 원형 리스트(Circular list) 선형 리스트의 꼬리 노드가 머리 노드를 가리키는 자료구조 원형 리스트 상태를 판단하는 방법 빈 원형 리스트 판단: list->head == NULL 노드가 1개인지 판단: list->head->next == list->head Node* p가 머리 노드인지 판단: p == list->head Node* p가 꼬리 노드인지 판단: p->next == list->head 이중 연결 리스트(Doubly linked list) 선형 리스트에서 각 노드가 다음 노드와 앞쪽 노드에 대한 포인터를 가지고 있는 자료 구조 typedef struct __node{ Member data; struct __node* prev; struct __node* next; } Dnode; Dn.. 2023. 9. 24.
선형 리스트(연결 리스트, linked list) 선형 리스트: 데이터를 순서대로 나열한 자료 구조 리스트의 데이터는 노드(node) 또는 요소(element)라고 함 각각의 노드는 다음 노드를 가리키는 포인터를 가지고 있으며, 처음과 끝에 있는 노드는 각각 머리 노드(head node), 꼬리 노드(tail node) 한 노드의 바로 앞에 있는 노드는 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드는 다음 노드(successor node) 배열로 선형 리스트 만들기의 문제 쌓이는 데이터의 크기를 미리 알아야 함 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 함 포인터로 연결 리스트 만들기 노드를 구현한 구조체 Node typedef struct __node { Member data; struct __node *next; } Nod.. 2023. 9. 24.
문자열 검색: Boyer-Moore법 Boyer-Moore법 -> KMP법보다 효율이 더 좋음 ! 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정함 건너뛰기 표 패턴의 문자열의 길이가 n일 때 옮길 크기는 다음과 같이 결정: 1. 패턴에 들어 있지 않은 문자를 만난 경우: n 2. 패턴에 들어 있는 문자를 만난 경우 2-1. 해당 문자가 패턴 안에 중복되지 않으면서 마지막에 있는 경우: n 2-2. 그 외의 패턴의 마지막 문자의 인덱스가 k일 때: n - k - 1 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산해야 하므로 건너뛰기 표의 요소 개수는 UCHAR_MAX + 1 (UCHAR_MAX: 표현할 수 있는 문자의 개수로 에 객체 형식 매크로로 정의되어 있.. 2023. 9. 23.
문자열 검색: KMP법 KMP법 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높임 '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 표로 만들어 저장 (건너뛰기 표, skip table) -> 패턴 내에서 중복되는 문자의 나열을 먼저 찾아야 함. 패턴과 패턴을 한 칸씩 비교 ! 연속해서 겹치는 횟수를 기록 예를 들어 패턴이 "ABCABD"일 때, 4번째에서 처음 겹치고(1) 5번째에서 연속으로 겹친다(2) 따라서 건너뛰기 표는 "- 0 0 1 2 0"가 된다. skip[idx]: idx번째 문자가 일치하지 않을 때 다시 되돌아가야 할 위치 ! KMP법으로 문자열 검색 #include int kmp_match(const char txt[], const c.. 2023. 9. 23.

티스토리툴바