</note>

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

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

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

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