진진진 개발일지

- 정렬된 배열에 새로운 값을 추가하려면? 1. 삽입할 위치를 이진검색법으로 조사 2. 삽입할 위치 이후의 모든 요소를 뒤로 하나씩 이동 3. 새로운 값 대입 => 복잡도: O(n) 해시법: 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것 해시 함수(hash function): 키 값을 가지고 해시 값을 만드는 과정 해시 값(hash value): 배열의 키 값을 배열의 요소 개수로 나눈 나머지 등 해시 함수를 거친 값 해시 테이블(hash table): 해시 값을 정리한 표 버킷(bucket): 해시 테이블의 각 요소 충돌(collision): 저장할 버킷이 중복되는 현상 해시 함수는 가능하면 해시 값이 중복되지 않도록 고르게 분포된 값을 만들어야 함 충돌에 대한 대처: 체인법: 같은 해시 ..

트리: 데이터 사이의 계층 관계를 나타내는 자료구조 노드(node), 가지(edge) 루트(root): 가장 윗부분에 위치하는 노드 리프(leaf): 가장 아랫부분에 위치하는 노드 (=끝 노드, 바깥 노드) 안쪽 노드(internal node): 리프를 제외한 노드 자식(child), 부모(parent), 형제(sibling) 조상(ancestor): 어떤 노드에서 가지로 연결된 위쪽 노드 모두 자손(descendant): 어떤 노드에서 가지로 연결된 아래쪽 노드 모두 레벨(level): 루트로부터 얼마나 떨어져 있는지에 대한 값. 루트는 0 차수(degree): 노드가 갖는 자식의 수 높이(height): 루트부터 가장 멀리 떨어진 리프까지의 거리 널 트리(null tree): 노드, 가지가 없는 트리..

원형 리스트(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..

선형 리스트: 데이터를 순서대로 나열한 자료 구조 리스트의 데이터는 노드(node) 또는 요소(element)라고 함 각각의 노드는 다음 노드를 가리키는 포인터를 가지고 있으며, 처음과 끝에 있는 노드는 각각 머리 노드(head node), 꼬리 노드(tail node) 한 노드의 바로 앞에 있는 노드는 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드는 다음 노드(successor node) 배열로 선형 리스트 만들기의 문제 쌓이는 데이터의 크기를 미리 알아야 함 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 함 포인터로 연결 리스트 만들기 노드를 구현한 구조체 Node typedef struct __node { Member data; struct __node *next; } Nod..

Boyer-Moore법 -> KMP법보다 효율이 더 좋음 ! 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정함 건너뛰기 표 패턴의 문자열의 길이가 n일 때 옮길 크기는 다음과 같이 결정: 1. 패턴에 들어 있지 않은 문자를 만난 경우: n 2. 패턴에 들어 있는 문자를 만난 경우 2-1. 해당 문자가 패턴 안에 중복되지 않으면서 마지막에 있는 경우: n 2-2. 그 외의 패턴의 마지막 문자의 인덱스가 k일 때: n - k - 1 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산해야 하므로 건너뛰기 표의 요소 개수는 UCHAR_MAX + 1 (UCHAR_MAX: 표현할 수 있는 문자의 개수로 에 객체 형식 매크로로 정의되어 있..

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..

검색할 문자열을 패턴(pattern), 문자열 원본을 텍스트(text)라고 함 프루트-포스법 텍스트의 첫 문자부터 1칸씩 옮기며 순서대로 패턴과 비교 이전에 검사를 진행한 위치를 기억하지 못하므로 효율이 좋지 않음 #include int bf_match(const char txt[], const char pat[]){ int pt = 0; //txt 커서 int pp = 0; //pat 커서 while(txt[pt] != '\0' && pat[pp] !='\0'){ if(txt[pt] == pat[pp]){ pt++; pp++; } else{ pt = pt - pp +1; pp = 0; } } if(pat[pp] == '\0') return pt-pp; return -1; } int main(void){..

unsigned long형이 32비트라고 가정. 정수를 구성하는 비트의 나열을 비트 벡터(bit vector)라고 함 아래 비트부터 B0, B1, ..., B31이라고 할 때 32비트의 부호가 없는 정수 하나로 {0, 1, ..., 31}을 전체 집합으로 표현 가능 매크로 SetOf(no) typedef unsigned long BitSet; #define SetOf(no) ((BitSet)1 있으면 {n}, 없으면 0(공집합) int IsMember (BitSet s, int n){ return s & SetOf(n); } Add 함수 집합 s에 n을 추가하기 위해서는 집합 s와 {n}을 논리합(OR) 연산 -> 집합 s의 n에 대응하는 비트가 0에서 1로 변경됨 void Add(BitSet* s, i..

구조체 IntSet: int형 원소를 갖는 집합을 관리 typedef struc{ int max; //집합의 최대 크기 int num; //집합의 원소 개수 int* set; //집합 } IntSet; 헤더 파일 IntSet.h #ifndef ___IntSet #define ___IntSet typedef struct { int max; int num; int *set; } IntSet; int Initialize(IntSet *s, int max); int IsMember(const IntSet *s, int n); int IsFull(const IntSet *s); void Add(IntSet *s, int n); void Remove(IntSet *s, int n); int Capacity(cons..

힙(Heap) 부모의 값이 자식의 값보다 항상 크다(또는 작다)는 조건을 만족하는 완전이진트리 트리의 레벨 순서대로 배열에 저장하면 a[i] 노드에 대하여 다음과 같은 관계가 성립: 1. 부모는 a[(i-1) / 2] 2. 왼쪽 자식은 a[i*2 +1] 3. 오른쪽 자식은 a[i*2 +2] 힙 정렬(Heap sort) 가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘 -> 힙에서 루트를 없앤 다음 다시 힙을 만들어야 함 1. 마지막 요소를 루트와 바꿈 2. 큰 값을 가지는 자식과 위치를 바꾸며 내려가는 작업을 정렬되지 않은 부분에서 반복. 자식이 더 작거나 leaf에 도달하면 종료. static void downheap(int a[], int left, int right) { //힙을 만드는 ..