목록프로그래밍/C언어 알고리즘 (11)

Computer Security

#11 라빈 카프 문자열 매칭

라빈 카프 문자열 매칭 -아스키 코드 기반의 해시함수(Hash Function)을 이용해 특정한 문자열에 대한 해시 값을 구한다. -'연속적인 문자열이 이어지는' 상황이므로 해시함수의 동작에 있어서 연산 속도가 O(1)이다. 라빈 카프 문자열 매칭: 해시 함수 -라빈 카프 문자열 매칭 알고리즘에서 해시 함수는 '각 문자의 아스키 코드 값에 2의 제곱 수를 차례대로 곱해 더한 값'을 구한다. -일반적으로 서로 다른 문자열의 경우 해시 값이 다르게 나온다. 해시 함수에 기반한다는 점에서 해시 충돌에 대한 처리가 필요하다. (해시 함수(hash function) 또는 해시 알고리즘 또는 해시함수알고리즘은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.) ex) 문자열: “bbacdab” = ..
프로그래밍/C언어 알고리즘 2022. 6. 11. 18:30
#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
#8 세그먼트 트리

세그먼트 트리 선형적으로 그냥 구간 합을 구하는 것은 비효율적이다. 트리 구조를 활용해 구간합을 구하는 과정은 O(logN)의 시간복잡도를 가진다. 구간합트리는 부모에서부터 왼쪽 자식과 오른쪽자식에게 절반을 나누어 주어서, 쭉쭉 내려가는 트리이다. 예를들어 맨위에 start Node 가 40이라면 0~20까진 leftChild 21~40은 rightChild 로 쪼개지고, 또 leftChild 에서의 leftChild가 0~10 , leftChild의 rightChild 가 10~20을 담당하게 된다. 이런식으로 차례로 내려가는 트리를 만든뒤(구간이 세세히쪼개짐) 구간에 해당하는 부분 노드를 더해나가면 된다. 코드예시 #define _CRT_SECURE_NO_WARNINGS #include #define..
프로그래밍/C언어 알고리즘 2022. 5. 10. 18:30
Prev 1 2 3 Next