목록알고리즘 (7)

Computer Security

#10 KMP 문자열 매칭

단순 비교 문자열 매칭 1.단순 비교 문자열 매칭 알고리즘은 두 문자열을 처음부터 끝까지 계속 비교하는 알고리즘입니다. 2.단순 비교 문자열 매칭 알고리즘은 O(NM)의 시간 복잡도를 가집니다. ex) ABCDEFG 에서 EF를 찾는 경우 AB랑 EF를 비교, BC랑 EF를 비교 ... 이런식으로 하나하나 찾아 나간다. 코드예시 #include #include char* parent = "ABCDEFG"; char* pattern = "EF"; int main(void) { int parentSize = strlen(parent); int patternSize = strlen(pattern); for (int i = 0; i 0 && pattern[i] != pattern[j]) { j = table[j..
프로그래밍/C언어 알고리즘 2022. 6. 10. 18:30
#9 인덱스 트리

인덱스 트리 트리 구조로 구간 합 구하기 -세그먼트 트리는 구현하는 과정이 복잡하고 어렵다는 점에서 구간 합을 더 쉽게 구할 방법이 필요하다. -인덱스 트리는 구현이 매우 간단하다. -인덱스 트리를 활용해 구간 합을 구하는 과정도 O(logN)의 시간 복잡도를 가진다. -인덱스 트리는 세그먼트 트리에 비해서 메모리 효율성이 높다. 특정한 숫자의 마지막 비트 구하기 -특정한 숫자 A의 가장 마지막 비트를 구하고자 할 때는 A& -A를 구하면 된다. ex) A가 14일 때 이를 비트 형태로 표현하면, A = 00000000 00000000 00000000 00001110 -A = 11111111 11111111 11111111 11110010 A & -A = 00000000 00000000 00000000 ..
프로그래밍/C언어 알고리즘 2022. 6. 9. 18:30
#1. 깊이 우선 탐색

깊이 우선 탐색(Depth First Search)은 DFS 라고도 불리우는데 탐색을 할때 보다 깊은것 부터 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색(DFS)는 전체 노드를 맹목적으로 탐색하고자 할 때 사용한다. 깊이 우선 탐색 알고리즘은 스택 자료구조를 통해 만들 수 있다. 장점 1.단지 현 경로상의 노드들만 기억하면 된다 --> 저장공간의 수요가 비교적 적다. .2목표 노드가 깊은 단계에 있을 경우 , 깊은것 부터 우선적으로 탐색하기 때문에 빠르게 해를 구할 수 있다. 단점 1.깊은 경우일때, 해가 없는 경우에 빠져버리면 수행하기 어려울 수 있다. 2.얻어진 해가 최단경로다! 라고 말하기 어렵다. 목표에 이르는 경로가 여러가지 일때, 깊이우선탐색을 시행했을때, 최적화 된 방법이 아닐 수 있다..
프로그래밍/C언어 알고리즘 2022. 5. 3. 22:45
Prev 1 2 Next