카라추바 알고리즘 10만자리 곱하기 10만자리같은 곱셈은 애시당초 자료형으로 표현할 수도 없고, 문자열로 바꾸어 하나하나 곱하면 $O(N^2)$의 복잡도를 갖게 된다. 이때 등장하는 것이 카라추바 알고리즘. 시간복잡도를 $O(N^{log3})$으로 줄여준다. 그 방법을 한번 살펴보자. 일단 256자리의 두 정수 a, b를 곱한다고 생각해볼때 a와 b를 다음과 같이 나눈다. $a = a_1\times10^{128}+a_0​$ $b = b_1\times10^{128}+b_0​$ a1,b1은 각각 a,b의 첫 128자리, a0,b0는 각각 a,b의 뒷 128자리를 나타낸다. 그럼 이제 a * b의 계산 과정은 다음과 같이 나타낼 수 있다. $a\times b = (a_1 \times b_1) \times 10..

최단 경로 (다익스트라) 최단 경로를 찾는 문제는, 한 정점으로부터 다른 모든 정점으로 가는데 걸리는 최단 경로를 통해 결국은 원하는 지점으로 최단경로를 찾는 방법이다. 다익스트라는 여기서 첫 점을 기준으로 정점들을 추가하며 거리를 갱신시킨다. D(z)를 x에서 z까지의 최단 경로라 한다면 $D(z) = Min(D(z) , D(y) + c(y,z))$ 의 식을 계속 진행하여 전체 경로에 대한 최단 경로를 알아낸다. //최단 경로 수도 코드 //입력 : 가중치 그래프 G //출력 : distance 배열, distance[u]는 v에서 u까지의 최단 거리 shortest_path(G,v) S = v; for(G의 각 정점 w) do distance[w] = weight[v][w]; while 모든 정점이 ..

그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료 구조이다. 수학자 오일러에 의해 처음 창안되어 그래프 이론은 컴퓨터 학문 분야의 활발한 연구 주제이다. 그래프에 관한 아주 간단한 설명은 이전 게시글에 있다. 2. 자료구조 (2) - 트리, 그래프 트리 트리 = 노드(node)로 이루어진 자료 구조. 하나의 루트 노드가 존재하고, 이로부터 0개 이상의 자식 노드들이 존재합니다. 이 노드들이 서브트리(subtree)를 구성합니다. 루트와 서브 트리, 각� howtolivelikehuman.tistory.com 인접 행렬 vs 인접 리스트 그래프를 표현하는 방법은 두가지가 있다. 인접 행렬과 리스트 인접행렬 M의 각 원소를 아래와 같은 규칙에 따라 그래프를 메모리에 표현할 수 있다. if(간선 x..

순열 순열과 조합은 경우의 수 등 가능한 가짓수를 생각할때 가장 바탕이 된다. 우선 순열은 순서가 있는 묶음으로, 7명을 등수를 매기는 방법과 같이 각각 구분되는 형식에 데이터를 나누는 방법이다. 수학적으로 보면 ${}_n\mathrm{P}_{k} = \frac{n!}{(n-k)!}$ 7명을 등수를 매기는 방법 $7! = 7\times6\times5\times4\times3\times2\times1 = 5040$ 7명 중 1,2,3등을 매기는 방법 $\frac{7!}{(7-3)!} = 7\times6\times5 = 210$ 으로 볼 수 있다. 이러한 순열을 직접 사용하는 경우는 내 생각엔 보통 완전 탐색 등에서 모든 가짓수를 체크하기 위해 사용하는 것 같다. 7명중 1,2,3등을 매길 때 ~ 무슨 조건..

순차 탐색 주어진 값들에서 최대, 최소를 찾는 방법은 다양하다. 아마 우리가 자주 사용하는 방법은 데이터를 첫 번째 부터 읽어서, 현재까지 저장해놓은 최대값과 계속 비교해 나아가는 방법일 것이다. //c++ int findMax(int data[], int length){ int max = INT_MIN; // 사용 //int min = INT_MAX; int i; for(i = 0; i data[i]) min = data[i]; } return max // or min } 이러한 방법을 사용하였을 때, 우리는 필연적으로 $n-1$ 번의 비교를 해야한다. 더 효율적인 방법은 없을까? 우리가 실생활..

선형탐색 순서대로 하나 하나씩 찾는 방법. $O(N)$의 시간복잡도. public int LinearSearch(int data[], int key){ for(int i=0; i 폴딩이라고 한다. 탐색 키가 문자열일 경우 주의할 점. 가장 보편적인 방법은 아스키 코드 값을 모두 더하는 것 but 탐색 키들이 동일한 문자로 이루어져있지만 위치가 다른 경우 ex) are, ear 같은 경우 구분할 수 없다. 아스키 문자 코드가 65~122이기 때문에, 3자리인 경우 195~366으로 해시 주소가 집중될 수 있다. 이를 해결하기 위해 아스키 코드 x 문자의 위치를 사용한다. 문자열 s가 n개의 문자이고, i번째 문자의 값을 $u_i$라 할때 $u_0g^{n-1} +u_1g^{n-2} + ... + u_{n-2..

합병 정렬 폰 노이만에 의해 만들어진 정렬 방법이다. 분할 정복(Divide and Conquer)를 이용한 정렬 방법으로, 문제를 작은 문제로 나누고 각각을 해결한 다음, 그 결과로 큰 문제를 해결하는 방법이다. 합병 정렬(Merge Sort)은 3가지 과정으로 구성된다. 분할(Divide) = 배열을 같은 크기의 배열 두개로 분할한다 정복(Conquer) = 이 두 개의 배열을 정렬한다. (크기가 아직 크면 순환 호출로 다시 분할) 결합(Combine) = 배열들을 다시 합치면서 원래의 정렬된 배열로 만든다. 코드 //머지소트 c++ 코드 void MergeSort(int sort[], int data[], int first, int last) { int mid; //1개 남았을때는 멈추게 if (f..

삽입 정렬 모든 요소를 앞에서부터 차례대로 정렬된 부분과 비교하여 위치를 찾아 삽입하는 방법. void InsertionSort(int[] data){//삽입정렬 for (int i = 1; i = 0; j--) { //앞에 정렬되어 있는 부분에서 해당하는 위치를 찾아 삽입 if (data[j] > key) { data[j + 1] = data[j]; //한칸 옆으로 이동 } else { break; } } data[j + 1] = key; } } 시간복잡도 BestCase : 이미 정렬된 경우 -> 이동 없이 각각 1번의 비교씩 $O(N)$ WorstCase : 입력 자료가 역순인 경우 등 (마지막이 4 3..

완전 탐색 완전 탐색은 모든 경우의 수를 다 해보는 것으로 Brute Force라고도 한다. 컴퓨터의 빠른 계산 능력을 이용하여 모든 경우의 수를 해보지만, 시간 역시 최대로 소모된다. for문을 사용하여 정말 모든 경우를 탐색하는 방법과, 재귀, DFS/BFS/ 백트래킹, 비트마스크 등이 존재한다. 위와 같은 방법들을 간단하게 소개하도록 하겠다. 재귀 호출 - 어느 함수가 자기 자신을 다시 참조하는 방법이다. $f(n) = f(n-1) + f(n-2)$ 등의 피보나치 수열, $n! = (n-1)! * n$ 과 같은 팩토리얼 연산 등에서 자주 등장한다. 하지만 재귀함수는 잘못 사용하면 복잡도가 어마어마하고, 함수가 끝날 때까지 자기 자신 호출 이후의 명령문이 수행되지 않는다. 또한 반드시 종료조건이 있어..

비트 조작 비트(bit)는 Binary Digit를 줄인 말로 데이터를 나타내는 최소 단위이다. 0과 1 두 값 중 하나를 가질 수 있다. 8bit가 모여서 1Byte가 되며 이후 단위들은 아래와 같다. 접두어(SI) 이름 계산법 접두어(IEC) 이름 계산법 킬로($10^3$) 1킬로바이트(kilobyte)/kB 1000B=1kB 키비($2^{10}$) 1키비바이트(kibibyte)/KiB 1024B=1KiB 메가($10^6$) 1메가바이트(megabyte)/MB 1000KB=1MB 메비($2^{20}$) 1메비바이트(mebibyte)/MiB 1024KiB=1MiB 기가($10^9$) 1기가바이트(gigabyte)/GB 1000MB=1GB 기비($2^{30}$) 1기비바이트(gibibyte)/GiB 10..