전체 글

플로이드 알고리즘은 모든 정점끼리의 최단경로를 구하는 문제입니다. void floyd(int n, int S[][N], int P[][N]){ for(int i=0; i

이항계수 알고리즘은 누구나 한 번쯤 들어봤을 법한 파스칼의 삼각형, 조합을 구하는 알고리즘입니다. 고등학교 수학에서 nCk라 표현하던 식은 2*1 행렬로 표현할 수 있습니다. 위의 식을 참고해서 분할정복으로 풀어보면, int binomial(int n, int k){ if(k==0 || k==n) return 1; return binomial(n-1,k-1)+binomial(n-1,k); } 다음과 같은 간단한 코드가 나옵니다.. 본래 DP로 접근해야 할 문제인데, 분할정복으로 접근했을 때 얼마나 비효율적인지 구해봅시다. 무려 시간복잡도가 n! 가 나옵니다. 가장 높은 수준이라고 할 수 있지요. 이제 DP로 접근해볼건데, 분할정복과 아이디어는 같습니다. int binomial(int n, int k){ ..

Quick Sort는 Merge Sort와 같이 분할정복을 이용한 정렬법이지만, 공간을 n만큼 더 사용하는 merge sort와 달리 in-place sort 입니다. pivotpoint가 항상 맨 앞일 때를 가정한 코드는 다음과 같습니다. int partition(int S[], int low, int high){ int pivotpoint = low; int j=low; for(int i=low+1; i

알고리즘은 아니지만, 재귀 문제의 시간 복잡도를 계산하는데에 큰 도움이 되는 theorem입니다. 위와 같은 식이 있을 때, master theorem에서 필요한 값은 a와 b, f(n)입니다. 여기서 3가지 경우로 나누어집니다. ε는 0이상의 상수이며, f(n)이 어느 식에 해당하는지 확인해야 합니다. 먼저 Case 1과 Case 2에 해당할 때엔, 간단하게 위와 같은 시간 복잡도가 구해집니다. 다만 Case 3일때는 추가적인 조건이 필요합니다. 위에서 제시한 Case3 조건과 위 조건에 전부 해당하면 시간 복잡도는 위와 같습니다. Case 1,2,3에 속하지 않다면, 위의 Auxiliary Master Theorem를 참고하시길 바랍니다.

병합정렬은 분할정복을 이용한 sort algorithm입니다. 먼저 배열을 1개 단위로 쪼갠 뒤, 다시 합치며 정렬하는 방법입니다. 코드는 다음과 같습니다. void merge(int S[], int U[], int low, int mid, int high){ int i=low, j=mid+1, k=low; while(i

이분탐색은 오름차순 정렬된 배열에서 특정 값을 찾아 인덱스를 반환하는 search algorithm입니다. 코드는 다음과 같습니다. int binarySearch(int A[], int x, int low, int high){ int mid; if(low>high) return -1; else{ mid = (low+high)/2; if(A[mid]==x) return mid; else if(A[mid]>x) return binarySearch(A,x,low,mid-1); else return binarySearch(A,x,mid+1,high); } } low와 high의 초기값은 각각 탐색하고자 하는 배열의 처음 인덱스와 마지막 인덱스입니다. 즉 mid는 현재 탐색하고 있는 배열의 가운데 인덱스를 가리키..

https://www.acmicpc.net/problem/2011 >s; int size = s.size(); if(s[0]=='0'){ cout

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2≤n≤1000, 2≤m≤1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다. www.acmicpc.net 지도에서 모든 땅에 대해 2 에서부터의 거리를 출력하는 간단한 문제이다. 즉, 입력받은 2를 시작점으로 BFS를 이용해 벽을 제외한 나머지 땅까지의 최단 거리를 구하면 된다. 2(목표 지점)나 0(벽)같은 특수한 숫자는 입력을 받을 때 방문했는지를 확인하는 배열에 음수를 넣어두는 방법을 사용하였다. 출력할 때, 미리 지정해 둔 음수를 ..