algoshipda의 블로그

https://www.acmicpc.net/problem/11583 trailling zero를 최소화 한다는 것은 그 수를 소인수분해 했을때 2와 5의 지수 중 작은 것을 최소화 하는 것과 같다. 2의 지수만을 보고 구한 것과 5의 지수만을 보고 구한 것 중 작은 값이 답이 된다. 이것은 다이나믹 프로그래밍으로 쉽게 구할 수 있다.

https://www.acmicpc.net/problem/1587 생각해보면 A집합 정점 갯수와 B집합 정점 갯수 둘 중 하나라도 짝수인 것이 있으면 같은 집합내에서 인접한애들끼리만 짝지어도 무조건 최대를 만들 수 있다는 것을 알 수 있다. 만약 둘 다 홀수라면 A의 홀수번 정점에서 B의 홀수번 정점으로 가는 것 말고는 이득을 볼 것이 없다는 것을 알 수 있다. 따라서 A의 홀수번 정점에서 B의 홀수번 정점으로 가는 간선이 있는지만 체크해서 답을 구하면 된다.

INC 2007 H번 https://www.acmicpc.net/problem/7812 루트를 하나 잡고 DFS를 통해 루트에서 다른 모든 정점으로 가는 비용의 합을 구해 놓는다. 이 때 정점 u(1 ~ n)를 루트로 하는 서브트리의 정점 갯수도 구해 놓는다. 다시 DFS를 돌리는데 이때 처음에 루트에서 아까 구한 비용의 합을 들고 시작하면서 최소답을 갱신시켜 나간다. cost(u, v) = 간선(u, v)의 비용 count(u) = u를 루트로 하는 서브트리의 정점의 갯수 라 하자. 간선(u, v)를 탈때 cost(u, v) * count(v) 만큼 답이 줄어들고 cost(u, v) * (n - count(v)) 만큼 답이 늘어나는걸 이용하면 된다. 시간 복잡도는 O(N). 답이 int범위를 벗어 날 수 있음에 주의한다.

http://codeforces.com/blog/entry/8219

http://community.topcoder.com/stat?c=problem_statement&pm=2989&rd=5869 http://community.topcoder.com/stat?c=problem_statement&pm=3994&rd=6532 http://community.topcoder.com/stat?c=problem_statement&pm=1848&rd=4675 (DP) http://community.topcoder.com/stat?c=problem_statement&pm=3510&rd=6527 http://community.topcoder.com/stat?c=problem_statement&pm=3509&rd=6528 http://community.topcoder.com/stat?c=problem_statement&pm=4450&rd=7217 http://community.topcoder.com/stat?c=problem_statement&pm=1954&rd=5006 풀고싶다 http://community.topcoder.com/stat?c=problem_statement&pm=1849&rd=4675

동전 https://www.acmicpc.net/problem/2293 https://www.acmicpc.net/problem/2294 https://www.acmicpc.net/problem/2624 https://www.acmicpc.net/problem/9084 https://www.acmicpc.net/problem/2294 게임 DP https://algospot.com/judge/problem/read/NUMBERGAME https://www.acmicpc.net/problem/11062 중간에 잘라서 하는거 https://www.acmicpc.net/problem/11066 https://www.acmicpc.net/problem/11049 트리 DP (시간복잡도 계산에 주의) https://www.acmicpc.net/problem/2213 https://www.acmicpc.net/problem/2533 http://codeforces.com/problemset/problem/581/F https://www.acmicpc.net/problem/2584 https://www.acmicpc.net/problem/9013 https://www.acmicpc.net/problem/11503 https://www.acmicpc.net/problem/2197 https://www.acmicpc.net/problem/1805 http://www.spoj.com/problems/VOCV/ http://www.spoj.com/problems/PT07F/ http://www.spoj.com/problems/PT07X/ LIS https://www.acmicpc.net/problem/1666 https://www.acmicpc.net/problem/2568 https://www.acmicpc.net/problem/2565 비트마스크 https://www.acm

https://www.acmicpc.net/problem/10937 https://www.acmicpc.net/problem/1657 https://www.acmicpc.net/problem/11111 https://www.acmicpc.net/problem/8992 https://www.acmicpc.net/problem/3640 https://www.acmicpc.net/problem/11493 위 3문제는 MCF를 찾는건데 bellman-ford나 SPFA돌리면서 sink로의 cost가 양수 일때 중지 하면 된다. 8992번 문제는 정점을 공유하지 않으면서 최소 비용인 경로 2개를 찾는건데 정점을 공유하지 않는다는 조건은 한 정점을 두개로 분리하여 중간에 capacity가 1인 간선을 넣어줘서 만족 시킬 수 있다. 3640번 문제는 전형적인 MCMF 문제이다. 11493 : ACM ICPC 2015 대전 리저널 A번 문제 https://www.acmicpc.net/problem/1210 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1616  (min cut) http://poj.org/problem?id=3041 (이분 매칭) https://www.acmicpc.net/problem/1867 https://www.acmicpc.net/problem/11375 https://www.acmicpc.net/problem/11376 https://www.acmicpc.net/problem/11377 https://www.acmicpc.net/problem/11378 http://community.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709 https://www.acmicpc.net/problem/1348 https://www.acmicpc.net/problem/11495 https://www.

https://www.acmicpc.net/problem/11000 https://www.acmicpc.net/problem/1666 https://www.acmicpc.net/problem/1933 https://www.acmicpc.net/problem/1379 https://www.acmicpc.net/problem/1374 https://www.acmicpc.net/problem/11108 https://www.acmicpc.net/problem/10672

어떤 테스크가 N개 주어진다. 각 테스크는 시작시간, 종료시간, 가중치를 가지고 있다. 같은 시간에 2개 이상의 테스크를 처리할 수 없을 때 최대로 얻을 수 있는 가중치의 합을 구하라 https://www.acmicpc.net/problem/11108 https://www.acmicpc.net/problem/1666 (2차원이지만 접근법이 비슷하다고 생각함) 방법: 간단히 dp로 n^2에 풀 수 있지만 nlgn으로 줄일 수 있다.  테스크들의 시작점과 끝점을 분리하고 인덱스를 같이 저장하여 시간 순으로정렬한다. (이때 시작점인지 끝점인지 알 수 있도록 한다.) 정렬한 데이터를 선형으로 보면서 시작점일 경우 이전에 구한 최대값과 같이 계산해서 저장해 놓는다.(최대값을 바로 갱신하지 않는다.) 끝점일 경우 최대값을 갱신한다. (binary search로 현재 보는 테스크와 겹치지 않고 인덱스가 가장 큰 테스크를 찾아도 될것 같다.)

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2615 m개의 쿼리가 들어 온다. a,b 쿼리는 b가 a의 서브트리에 속하는가? 쿼리가 많으므로 한 쿼리를 O(1)로 처리해야 한다. DFS로 각 노드의 DFS 시작시간과 종료시간을 기록해두면 저 쿼리를 O(1)로 처리 할 수 있다. 각각의 시작시간을 Start, 종료시간을 Finish라 하면 Start(a) < Start(b) and Finish(b) < Finish(a) 이면 b는 a의 서브트리이다. # include <bits/stdc++.h> using namespace std ; int n,m; vector< vector< int > > adj; vector< int > start; vector< int > finish; int main () { int t; scanf("%d",&t); for(int tc=1;tc<=t;++tc){ scanf("%d",&n); int cnt = 0; int curtime = 0; adj. clear (); for(int i=0;i<n;++i){ adj. push_back (vector<int>()); int x; scanf("%d",&x); for(int j=0;j<x;++j){ adj[i]. push_back (++cnt); } } start = vector<int>(cnt+1,0); finish = vector<int>(cnt+1,

A n by n 행렬이 주어진다. a(i,j)에는 i*j가 써져있다. 1<=i,j<=n이다. 이 행렬에 쓰인 숫자 중 x와 같은 것들의 갯수를 구하는 문제이다. 행렬의 각 열과 각 행을 봤을때 같은 숫자는 없다. 따라서 1~n까지 돌리면서 x의 약수이면서 x를 나눴을때 n이하의 숫자가 나오는 것들만 갯수를 세면 된다. O(n) B 1<=n<=10^6 , 1<=m<=10^3 길이 n 의 수열이 주어진다. 이 중 1개 이상의 숫자를 뽑아서 합해서 m의 배수를 만들 수 있는지를 구하는 문제이다. m의 배수라는 것은 결국 합했을때 m으로 나눈 나머지가 0이라는 것을 의미한다. 따라서 주어진 수열에서 중요한것은 그 숫자가 아니라 나눈 나머지이다. DP(i,j)를 현재 i 번째 나머지숫자를 보고 있을때 현재까지 합한 숫자들의 나머지가 j인 경우가 있는가? 라고 정의하면 dp[i][j]가 1일 때 dp[i+1][j+a[i]]를 1이라고 하면 된다. 이 경우O(n*m)으로 풀 수 있다. 문제는 n이 최대 100만이라는 것인데(TLE ㅜㅜ) 비둘기집의 원리에 의해 n>m인 경우는 무조건 가능하다고 처리하면 시간안에 계산 수 있다. i번째를 구할때 i-1만 알면 되므로 슬라이딩 윈도우를 써서 메모리 사용량을 줄일 수 있다. C 1<=n<=10^3인 n이 주어진다. 1<=x<=n인 어떤 x를 맞추기 위해 이 x가 어떤 y로 나눠지냐는 질문을 할 수 있다. 문제는 x를 맞추기 위해서 해야할 질문의 최소 수와 이때의 질문 순서이다. 소수를 구해나가면서 소수의 거듭제곱이 <=n 일 동안 답에 추가하면 된다고 한다. 다른 사람들은 이 방법으로 풀었는데 나는 와닿지 않았다 ㅜㅜ sqrt해서 소수판별을 해도 되고 에라토스테네스의 체로 미리 구해놓고 해도 된다. O(nloglogn) D 모름 E 모름

1. 입력으로 점 A와 B가 주어진다. 점 A,B와 같지 않으면서 유클리드 거리 dist(A,B)>dist(B.C)인 C를 찾는 문제 인데 C가 있을 수 있는 범위가 -100<=x,y<=100이라는 조건이 있어서 그냥 200 * 200으로 돌려 보면 된다. 2. 길이 m인 이진수가 n개 주어진다. 이제 이 이진수들을 재배치 하는데 재배치 순서에 따라 그 이진수들의 cost가 결정 된다. cost는 이진수들을 순서대로 봤을때 그 이진수에서 이전에 등장하지 않은 1의 위치의 갯수의 제곱이다. 즉, 110 -> 100 이라면 110에서 처음 등장한 1의 위치 갯수는 2개 이므로 +4, 100에서 제일 왼쪽 1은 110에서 등장하므로 +0 전체는 4. 이런 식이다. 0<n,m<=20이므로 비트마스트 DP를 사용하면 O(m*2^n)의 시간복잡도로 해결 할 수 있다. 많은 사람들이 그리디로 접근해서 틀렸다. 3. 풀어보고 올리겠다.

https://en.wikipedia.org/wiki/3SUM https://www.acmicpc.net/problem/2473 https://www.acmicpc.net/problem/2470 3sum problem 주어진 리스트에서 i<j<k이고 a[i] + a[j] + a[k] = X를 만족하는 해가 있는지 찾는 문제. 먼저 주어진 리스트를 정렬한다. O(nlgn) i를 고정시키고 오른쪽 범위에서 a[j] + a[k] = X - a[i]를 만족하는 해가 있는지를 찾는 문제를 생각해보자. 이 문제는 O(n)에 해결 할 수 있다. a[j] + a[k] > X - a[i]라면 k를 1 감소 시키고 그 외는 j를 1 증가시킨다. 이러면 O(n)에 만족하는 j, k 를 찾을 수 있다. i를 1씩 증가시키면서 모든 구간에 대해 반복하면 최종적으로 O(n^2)에 답을 찾을 수 있다.

http://codeforces.com/contest/574 A 제일 처음 숫자보다 크거나 같은 숫자가 없을때까지 나머지 숫자중에 제일 큰수에서 1을 감소시키고 제일 처음숫자에 더해주고 답을 갱신하면 된다. 숫자 하나 업데이트하고 나서 다시 처음부터 보지 않고 그냥 뒤에 쭉 봤더니 WA, 그래서 우선순위큐를 써서 없을때 까지 돌렸다. A는 틀리지 말자 ㅜㅜ B DFS로 cycle 길이 재는 문제를 접했던 적이 있어서 DFS로 길이 3인 cycle을 찾으려고 시도하였으나 계속 WA가 떴다. 너무나 당연히 된다고 생각했었는데 마침내 예외 케이스를 찾아냈고 안된다는걸 알았다(DFS에 대해 좀 더 깊이 파봐야겠다.). 그리고 그냥 단순하게 4000*4000 인접행렬 만들어 풀었다.. 메모리 제한 넉넉할땐 걱정하지 말고 잡자. C 2랑 3밖에 못곱하므로 결국 어떤 두 수가 같으려면 소인수분해 했을때 2와 3를 제외한 나머지 부분이 같아야 된다. 그래서 2로 안나눠질때까지 나누고 3으로 안나눠질때까지 나눈뒤에 비교 하면 된다. 쉬움. D 어떤 줄이 사라지는 시간은 왼쪽이 사라지는 시간 + 1, 오른쪽이 사라지는시간 + 1, 자기 높이 중 최소라는 사실은 알아냈으나 이후에 어떤식으로 접근해야 할지 방법이 떠오르지 않았다. DP로 풀면 된다고 하는데 아직 자세히 보지 않아서 모르겠다. ..editorial의 풀이는 와닿지가 않았는데 밑에 보니 dijkstra 풀이가 가능하다고 하더라. 각 블록들을 노드로 생각하고 가상의 소스노드에서 블록의 높이를 가중치로 가지는 간선을 연결한다. 인접한 블록들에 대해서는 가중치 1의 간선을 만들어 준다. 최종 답은 소스에서 다익스트라를 돌렸을때 최단거리가 가장 긴 노드까지 가는 거리가 된다. E 모르겠다.

https://www.acmicpc.net/problem/10167 http://www.spoj.com/problems/KQUERY/ http://codeforces.com/contest/380/problem/C -- 정보 http://codeforces.com/blog/entry/15890 http://codeforces.com/blog/entry/15729 struct SegmentTree { int n; vector<int> s; SegmentTree ():n(N),s(N<<2,INT_MAX){} void build (int id=1, int l=0, int r=N-1) { if(r==l){ s[id] = INT_MAX // or a[l]; return; } int mid = (l+r)>>1; build(id<<1, l, mid); build(id<<1|1, mid+1, r); s[id] = min(s[id<<1] , s[id<<1|1]); } void modify (int p, int x, int id=1, int l=0, int r=N-1) { s[id] = min(s[id], x); if(r==l)return; int mid = (l+r)>>1; if(p <= mid) modify(p, x, id<<1, l, mid); else modify(p, x, id<<1|1, mid+1, r); } int query (int x, int y, int id=1, int l=0, int

<pre style="background-color: #eeeeee; border: 0px; color: #111111; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, sans-serif; font-size: 13px; margin-bottom: 1em; max-height: 600px; overflow: auto; padding: 5px; width: auto; word-wrap: normal;"><code style="border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, sans-serif; margin: 0px; padding: 0px; white-space: inherit;">여기에 코드를 씁니다.</code></pre> 여기에 코드를 씁니다.

/etc/fstab 파일을 수정한다. <file system> <moutn point> <type> <options> <dump> <pass> 형식 외장하드의 경우 언제 연결 되도 일정한 곳에 mount 되게 하기 위해서 file system에 UUID를 사용하는것이 좋은듯 하다. UUID는 ls -ail /dev/disk/by-uuid 하면 볼 수 있다. (LABEL도 가능하다고 한다) sudo lsblk -o NAME,FSTYPE,SIZE,MOUNTPOINT,LABEL로 보고 맞춰서 하자. 예)UUID=136c242f-ce81-528e-a921-682c6fad9f26    /home    ext4    defaults    1     2 자세한것은 man fstab

https://docs.python.org/2/library/sys.html#sys.setrecursionlimit https://www.acmicpc.net/problem/1012 파이썬 써본지 얼마 안되서 DFS를 구현하는 문제를 풀었는데 알고리즘상에 문제가 없어보이는데 자꾸 오답이 나왔다. 무슨 문젠가 몇시간 동안 고민했는데 이유는 재귀깊이 한계치가 작아서였다. import sys sys.setrecursionlimit(10**6) 을 추가해줬더니 정답처리 됐다. import sys sys.setrecursionlimit( 10 * * 6 ) bat = [] dx = [ 0 , 1 , 0 , - 1 ] dy = [ 1 , 0 , - 1 , 0 ] M = N = K = 0 def dfs ( x , y ): bat[x][y] = 0 for k in range ( 4 ): i = x + dx[k] j = y + dy[k] if (i >= M or i < 0 or j >= N or j < 0 ): continue if (bat[i][j] == 1 ): dfs(i,j) return for t in range ( input ()): (M,N,K) = map ( int , raw_input ().split()) cnt = 0 bat = [[ 0 for j in range (N + 1 )] for i in range (M + 1 )] for i in range (K): (a,b) = map ( int , raw_input ().split()) bat[a][b] = 1 for i in range (M): for j in range (N): if

특정 페이지 접속이 계속 잘 되지 않았는데 단순히 페이지 html 이름을 바꿨더니 정상적으로 작동한다. 이유는 알 수 없다.

manifest에서 android:theme="@android:style/Theme.NoTitleBar"

<meta name="viewport" content="width=device-width, initial-scale=1"> 에 content 부분에 user-scalable=no 추가하면 된다.

/etc/init/failsafe.conf  에서 sleep 부분의 숫자를 바꾸거나 주석처리하면 된다.

http://markup.su/highlighter/

http://www.valgrind.org/ C나 C++로 프로그래밍을 하다보면 동적할당을 해놓고는 해제를 해주지 않는 경우가 더러 생긴다. Valgrind를 사용하면 이러한 메모리 누수를 체크할 수 있다.

Settings - Compiler 에서 Have g++ follow the C++11 ISO C++ language standard [-std=c++11] 체크

완전탐색이란 상태공간에서 특정한 조건을 만족하는 해를 가지는 상태를 찾기 위해 모든 상태를 만들어나가며 탐색하는 것을 말한다. 초기 상태에서 시작하여 인접한 상태들로 DFS(깊이우선탐색)을 하는 것과 같다. 완전탐색의 시간복잡도는 만들 수 있는 모든 상태의 수와 관련있으므로 최대한 상태공간을 적게 만들도록 상태를 정의하는것이 완전탐색의 포인트이다. https://www.acmicpc.net/problem/1759  암호만들기 문제요약 : 입력으로 주어진 문자들 중 L개의 문자를 조합해 만들 수 있는 문자열 중 특정 조건을 만족하는 모든 문자열을 사전순으로 출력해야 한다. L개의 문자로 만든 문자열은 각 문자들이 오름차순으로 배치 되어 있어야 하고, 최소 한개의 모음과 최소 두개의 자음으로 이루어져 있어야 한다. 일단 문제를 간단히 하기 위해 입력으로 주어진 문자들을 정렬한다. 그러면 여기서 완전탐색을 할때 먼저 앞에서 어떤 문자를 고른다면 남은 문자는 뒤에서만 고르면 된다. 그리고 완성된 문자열들을 모아서 따로 정렬할 필요 없이 완전탐색 과정에서 만들어지는 문자열을 사전순으로 발견된다. 함수 재귀호출 과정에서 넘기는 파라매터는 현재까지 만들어진 암호, 그리고 현재 선택가능한 가장 작은 인덱스이다. 패스워드의 길이가 L과 같아졌다면 조건의 맞는 문자라면 출력하고 함수를 종료한다. # include <cstdio> # include <vector> # include <string> # include <algorithm> using namespace std ; int l, n; vector< char > charVector; char c; void printPassword (string& password){ int size = password. size (); int i,cnt=0;; for(i=0;i<size;i++){

루프 불변성 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. 계산된 정보들로부터 최적해를 구성한다.