</note>

Karatsuba 알고리즘.. 간단히 소개하자면 큰수에 대한 효율적인 곱셈 알고리즘 N자리 K진수 A, B가 주어졌을 때, 두 수의 곱을 연산하는데 쓰이는 알고리즘. long long 자료형의 범위(-9223372036854775808 - 9223372036854775807) 즉 최소 N이 20넘어가는 순간부터는 이런 특이한 알고리즘을 사용하지 않으면 계산이 안될것 같다.. 이 알고리즘의 특이한 점은 수를 하나의 정수 자료형에 두고 사용하는게 아니라 배열에 넣어놓고 연산해서 연산 도중 B값을 넘거나, 0보다 작아지는 경우에 대해 직접적으로 처리를 해주어야 한다는 점인거 같다. 이 알고리즘을 사용하지 않고 단순히 수학적으로 계산을 하게 된다면 위와 같은 방식으로 계산이 될것이고 이경우 코드는 아래와 같이 ..

mississippi라는 문자열이 있다. 여기에서 ssi라는 문자열을 찾으려고 한다면 어떻게 해야 할까? 완전 탐색을 사용한다면 O(NM)의 시간 복잡도 안에서 해결할 수 있을거라고 생각한다. 앞글자가 일치하는 단어를 찾고 그 이후부터 글자가 동일한지 아닌지를 비교하면 될것이다. 하지만 이런 방법은 당연히 시간초과가 날 수 밖에 없다. 하지만 Rabin-Karp알고리즘을 사용하면 그 문제를 해결 할 수 있다. Rabin - Karp 알고리즘은 문자열 검색을 할 때 해시값을 이용하는 기법이다. 패턴 내의 문자들을 일일이 비교하는 대신에 패턴의 해시값과 비교할 문자열의 부분 문자열의 해시값만을 비교한다. 최악의 경우에 O(NM)의 시간복잡도를 가지지만, 평균적으로는 선형시간의 시간 복잡도를 가지기 때문에 효..

Binary Search(이분탐색)은 정렬된 배열 안에서 특정한 값의 위치를 찾는 알고리즘이다. 처음에 중간값을 임의의 값으로 설정하고 그 값과 찾고자 하는 값과 크고 작음을 비교해서, 만일 임의의 값이 찾고자 하는 값보다 크다면 임의의 값을 최소값으로 해서 다시한번 중간값을 탐색하고, 작다면 임의의 값을 최대값으로 해서 중간값을 탐색하게 하는 알고리즘이다. 정렬된 상태에서만 가능하다는 단점이 있지만, 정렬되어 있을 경우 이분 탐색이 선형 탐색을 할 때보다 더 나은 성능을 보장한다. (선형 탐색의 경우 O(n)의 시간 복잡도를 가지는 반면에 이분 탐색의 경우 O(log n)의 시간 복잡도를 가진다.) 일반적인 이분 탐색은 위와 같지만 경우에 따라서 임의의 값을 최대값으로 할 지 최소값으로 할 지 결정해서..

보통 해싱은 해시 함수를 통해 임의의 데이터를 고정된 길이의 데이터로 매핑하는 것이라고 한다. 데이터베이스에서 테이블에서의 빠른 탐색을 위해서 테이블 내의 각각의 튜플에 대해서 색인(Index)을 만들어서 색인 만으로 데이터를 검색하는데 이용한다. 해싱을 알고리즘 문제 풀이에 어떤 식으로 사용하는지 설명 해보려고 한다. 알고리즘에서 해싱이 사용되는 분야는 문자열이 대부분이어서(아직 공부가 부족해서 문자열밖에 접해보지 못했다.) 대부분의 설명이 문자열에 관한 내용이 될 수밖에 없을 것 같다. 사람의 시각으로 보면 당연히 문자열은 하나의 의미 덩어리이고 그냥 눈으로 보면 비교가 가능한 것이지만 컴퓨터의 관점에서 보면 문자들의 배열이기 때문에 비교하려면 하나하나 다 확인하는 수밖에 없어서 시간이 많이 걸릴 수..

SW Expert Academy에서 트리의 지름에 관련된 문제를 풀게 되었다. (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PN4CqACYDFAUq&) 이 문제를 처음 봤을 때 트리의 지름, 반지름, 중심에 관련된 문제이구나 하는 생각이 들어서 문제를 푸는데 안풀린다.. 아는 개념이라고 생각했었는데 잘 안풀려서 이번 기회에 복습해 보려고 한다. 이 문제의 풀이는 다음과 같다. 1. 모든 독립된 연결 요소들을 하나의 트리를 보고 각각의 트리에서 지름을 구한다. 2. 지름을 구하는 과정에서 구한 지름의 양끝점 u에서 v로 가는 경로를 탐색하면서 반지름을 구한다. 3. 반지름들을 이용해서 연결요소들을 연결 할 ..

Fenwik Tree(Binary Index Tree)는 구간합을 구할때 많이 사용되는 자료구조이다. 처음 배울 때 분명히 이해 했는데 매번 다시 볼때마다 새로워서 계속 코드를 보면서 공부해야할것 같다. Fenwik Tree를 구현하려면 어떤 수 N을 이진수로 만들었을 때 마지막 1의 위치를 구할 수 있어야 한다 L[i]배열의 값을 직접적으로 사용하지는 않지만 Fenwik Tree를 이해하기 위해서는 이해하고 있어야 할 듯 하다. 따라서 L[i]값을 수식으로 구하면 (i & -i)가 된다. (L[i] = (i & - i)) 그리고 배열 A[1] ~ A[N]에 N개의 수가 들어있다고 할 때 Tree[i]에는 A[i - L[i + 1]] ~ A[i]까지의 합이 저장되게 하면 된다. Fenwik Tree를 U..