algoshipda의 블로그

루프 불변성 Initialization : 첫 루프를 시작하기 전에 참이다. Maintenance : 루프 돌기 전에 참이라면 다음 루프때에도 참이다. Termination : 루프가 종료 되었을때 루프불변성이 알고리즘의 정당성을 증명하는데 유용한 성질을 가져야 한다. 예 )  Insertion sort (삽입정렬) int a[ 10 ] = {0,5,2,7,10,22,1,6,8,55}; for ( int j= 1 ;j< 10 ;++j){ int k = a[j]; int i = j-1; while(i>=0 && a[i]>k){ a[i+1] = a[i]; --i; } a[i+1] = k; } Initialization : 첫 루프를 시작하기전에 a[0] (j보다 작은) 은 오름차순으로 정렬 된 상태이다. Maintenance : j일때 a[0 ~ j-1]이 오름차순으로 정렬된 상태라고 하자. 내부에 while문은 i<0 이거나 a[i]<=k 일때 빠져나오게 된다. 만약 i<0 이라면 이는 k가 a[0~j]중에서 제일 작다는 뜻이고 a[0]에 k를 넣으면 다음 루프에서 j+1 일때 a[0 ~ j]가 오름차순으로 정렬된 상태가 되므로 보존성을 지킨다. 만약 a[i]<=k 이기 때문에 while문을 빠져 나왔다면 k는 a[i+1]의 위치에 들어가면 다음루프에서 j+1 일때 a[0 ~ j]가 오름차순으로 정렬된 상태이므로 마찬가지로 보존성을 지킨다. Termination : j가 10(배열의 크기)가 되어 for 루프를 빠져나왔을때 위에서 보였듯이 a[0~9(j-1)]은 오름차순으로 정렬된 상태일 것이다. 따라서 위 삽입정렬의 알고리즘은 올바르다.

상호배타적 집합( 서로소집합 )을 표현할때 쓰는 자료구조. 초기에 모든 노드의 부모노드를 자기자신으로 초기화한다. find연산 어떤 노드가 포함된 집합이 어딘지 알기 위해서는 그 노드 자신이 부모노드인 노드가 나올때가지 노드의 부모노드를 타고 올라간다. 이때 이 노드가 그 집합을 대표하는 노드가 되며 만약 어떤 다른 두 노드를 find연산한 결과가 같다면 그 둘은 같은 집합안에 있다. 나중에 find연산시 드는 시간을 줄이기 위해 path compression을 사용 할 수 있다. (return parent[x] = findSet(parent[x])로 부모노드를 바로 이어준다.) union연산 두 집합을 합치는 연산, 어떤 한 집합을 대표하는 노드의 부모노드를 다른 한쪽의 대표노드로 바꿔주면 된다. 이때 find연산시 지나가는 노드 숫자를 줄이기 위해 rank를 비교하여 그에 따라 어떤 집합이 parent가 될지 정한다. (path compression때문에 정확한 rank를 보존 할 수는 없다.) 관련문제 https://www.acmicpc.net/problem/1717 https://www.acmicpc.net/problem/1197 https://www.acmicpc.net/problem/1976 http://codeforces.com/problemset/problem/500/B void init (){ for(int i=0;i<n;++i) parent[i]=i; } int findSet (int x){ if(x==parent[x]) return x; return parent[x] = findSet(parent[x]); } void unionSet (int a, int b){ a = findset(a); b = findSet(b); if(a==b)return; if(rank[a]>rank[b]) parent[b] = a; else

해당하는 구간의 순열을 알아서 만들어준다. 자세한것은 http://www.cplusplus.com/reference/algorithm/next_permutation/ 내부구현은 http://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation 이런식이라고 한다. next_permutation을 활용한 소스 https://www.acmicpc.net/problem/1007 # include <cstdio> # include <algorithm> # include <cmath> # include <vector> using namespace std; struct Point{ int x; int y; Point (){ x=0;y=0; } Point (int _x, int _y){ x=_x; y=_y; } Point operator + (Point p){ Point ans; ans.x = x + p.x; ans.y = y + p.y; return ans; } Point operator - (Point p){ Point ans; ans.x = x-p.x; ans.y = y-p.y; return ans; } void init (){ x=0; y=0; } double scalar (){ return sqrt((double)x*x+(double)y*y); } }; void pointInit (Point point[]){ for(int i=0;i<22;++i)point[i

BIT(Binary Indexed Tree)라고도 한다. O(lgN)에 0부터 해당하는 인덱스까지의 부분합 ( 또는 점차 누적되는 정보 )을 알 수 있다. 기존에 쉽게 사용하는 부분합 배열 (단순히 0~N까지의 합을 각각의 배열 N인덱스에 저장) 은 O(1)에 부분합을 구할 수 있지만 이 경우 한번 모든 부분합을 구해놓고 나서 중간에 값을 갱신할때 다시 O(N)의 갱신이 필요하다. 하지만 펜윅트리는 이를 O(lgN)에 할 수 있게 해준다. 자세한것은 탑코더 튜토리얼 참고 http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/binary-indexed-trees/#add 소스코드는 '프로그래밍 대회에서 배우는 알고리즘 문제해결전략2 - 구종만'에 나온 소스코드를 참고하였다. # include <cstdio> # include <vector> using namespace std; struct FenwickTree{ vector<int> tree; FenwickTree (int n) : tree(n+1){} int sum (int pos){ ++pos; int ret = 0; while(pos>0){ ret+=tree[pos]; pos&=(pos-1); } return ret; } void add (int pos, int val){ ++pos; while(pos<tree. size ()){ tree[pos]+=val; pos+=(pos & -pos); } } }; int main (){ FenwickTre

어떤 구간의 최대,최소를 O(lgN)에 알게 해주는 자료구조  정의되는 연산 1.) 원소값 갱신 2.) a~b의 최대 또는 최소값 반환 완전이진트리를 배열로 구현  ( 들어갈 원소 숫자만큼의 단말노드를 가질 수 있도록 크기를 조정 , 편의상 그냥 4 * N으로 잡으면 된다. 값은 단말노드를 통해서만 들어간다.                예 : 들어갈 원소가 9개라고 한다면 최소한 단말노드가 9개                      여야 하므로 비단말노드 15개, 단말노드 16개를 가지는                      완전이진트리 형태가 되어야 할것이다.  ) 원소값 갱신: 원소가 하나 추가될때마다 부모노드와 비교하여 최대, 최소 ( 또는 다른 그 구간을 대표할만한)을 갱신한다. a~b의 최대,최소 반환: a (왼쪽끝 노드)에 있는 노드가 오른쪽노드일때 그 부모노드가 구간을 대표하는 값을 가질 수 없다는점을 이용하여 노드의 위치가 오른쪽일때는 그 오른쪽에 에 위치하는 왼쪽노드  (이 두 노드는 서로 다른 부모노드를 가진다.) 로, 왼쪽노드일때는 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 반대로 b(오른쪽끝 노드) 노드는 왼쪽노드일때 그 노드의 왼쪽에 있는 오른쪽노드, 오른쪽 노드일때 그 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 두 위치가 교차되거나 겹칠때 루프를 종료한다. const int INF = 2e9 ; struct Tree { int first; vector<int> tree; Tree (int n) { for(first=1;first<n;first<<=1); tree = vector<int>( n<<2, INF); } void update (int pos, int val) { pos += first;

1. 최적해의 구조와 특징을 찾는다. 2. 최적해의 값을 재귀적으로 정의한다. 3. 최적해의 값을 계산한다. 4. 계산된 정보들로부터 최적해를 구성한다.