archives

http://bigocheatsheet.com/ 에서 그대로가져옴. 참고용

https://www.acmicpc.net/problem/1254 http://qkqhxla1.tistory.com/738의 10942번 문제의 dp테이블이 해당 범위에서 팰린드롬인지 판단하는 함수이다. 1. 팰린드롬인지 판단해놓는다. 끝에 x개의 문자를 덧붙이는것이므로 i~끝까지의 팰린드롬이 가장 긴 범위를 찾는다. i가 2라서 2~끝까지 팰린드롬이다. 그러면 앞의 0,1은 팰린드롬이 아니라는 소리이므로 0,1번 인덱스 문자 두개만 붙여주면 된다 즉 길이 + 2가 답이다 이경우엔. 이런식으로 품 # -*- encoding: utf-8 -*- s=raw_input() dp = [[0 for i in xrange(1002)] for j in xrange(1002)] for i in xrange(len(s)..

https://www.acmicpc.net/problem/2011 # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(10000000) def password(index): if index =0 and 10 0: b = max(eat(1,w-1,ct), eat(1,w-1,ct+1)) temp += max(a,b) dp[p][w][ct] = max(dp[p][w][ct], temp) return dp[p][w][ct] t,w=map(int..

기초적이지만 그래도 정리... 파이썬 # -*- encoding: cp949 -*- def binary_search(l, data): low,high = 0,len(l) while low data: high = mid else: low = mid if bl==low and bh==high: return False return False a=sorted(map(int,raw_input().split())) print binary_search(a, input()) C++ #include #include #include #include #include #include #include using namespace std; bool binary_search(int l[100], int data) { int low..

https://www.acmicpc.net/problem/1480 와 미친.. dp 왜이렇게 재밌는지 모르겠다 이 문제는 배낭 문제+비트마스크다. 가장 큰 문제는 가방이 여러개라는거다. 처음에는 가방 1에서 모을수있는만큼 최대한 보석을 모으고 그 목록을 따로 저장 후 다음 가방으로. 이런식이었는데 이렇게 하면 안된다. 각각의 최댓값이 전체 문제의 최댓값이 안 될수도 있기 때문이다. 따라서 모든 경우의 수를 조합해야된다. 보석 수나 가방 용량 등을 봤을때 수가 적어서 모든 수를 조합하고 적당히 메모이제이션 하면 잘 나올거라고 예측 가능하다. # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(1000000) def getmax(m, capacity, j..

https://www.acmicpc.net/problem/2302 일단 문제를 어떻게 풀까 생각해보면 예시대로 4,7번이 고정좌석이라면 1~3번의 경우의수 * 5,6의 경우의수 * 8,9의 경우의수 가 답인걸 알수있다. 그럼 여기서 더 들어가서 1~3번의 경우의 수는 어떻게 구할수 있을까? 노가다 결과 피보나치수임을 깨달았다. 좌석이 1개일경우 경우의수는 1개, 2개는 2개, 3개는 3개, 4개는 5개, ..... 여기까지 생각하면 다 푼거다. # -*- encoding: cp949 -*- dp = [0 for i in xrange(41)] n=input() m=input() m_list=[input() for i in xrange(m)] dp[1] = 1 dp[2] = 2 for i in xrange(..

https://www.acmicpc.net/problem/10164 굳이 설명이 필요없음. # -*- encoding: cp949 -*- n,m,k=map(int,raw_input().split()) dp = [[0 for j in xrange(m)] for i in xrange(n)] dp[0][0] = 1 if k==0: k=n*m row = (k-1)/m col = (k-1)%m #print row,col for i in xrange(n): dp[i][0] = 1 for i in xrange(n): dp[i][col] = 1 for i in xrange(m): dp[0][i] = 1 for i in xrange(m): dp[row][i] = 1 for i in xrange(1,row+1): for ..

첫 글을 너무 대충 정리해서... 공부하다보니 다이나믹 프로그래밍의 엄청난 공부량을 느끼고 재정리. 한개나 두개정도 글을 더 쓸수도 있을듯 싶다. 첫글 : http://qkqhxla1.tistory.com/585 다이나믹 프로그래밍의 프로그래밍 패턴. 1. 재귀적으로 짜는 패턴. dp = [[-1 for j in xrange(10)] for i in xrange(10)] def function(a, b): if ~~~: return ~~~ #기저 사례. 미로찾기면 끝에 도달했다던가 하는등. ret = dp[a][b] #c++에서는 참조형으로 int& ret = dp[a][b];처럼 쓴다. if ret != -1: return ret #이미 a,b에 대한 값을 구한 적이 있으면 즉시 반환. 위에서 리스트 ..

https://www.acmicpc.net/problem/1535 배낭 문제. 체력이 0이되면 죽은것이므로 초기 체력을 100이아닌 99로 설정해준다. # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(1000000) def getmax(capacity, index): ret = 0 if index == n: return 0 unselected = getmax(capacity, index+1) selected = 0 if capacity >= weight[index]: selected = getmax(capacity-weight[index], index+1) + value[index] return max(unselected, selected) n=i..

잘 정리된 곳 : http://blog.naver.com/mycho/220725983486 개요. 특정 용량의 배낭이 있고 n가지의 물건을 담을 수 있다. n가지의 물건은 각각 가치와 무게가 있으며 가치가 최대로 되도록 배낭에 담는 형식의 문제. 이 배낭 알고리즘에는 3종류가 있다고 한다. 1. 물건 당 물건의 수량이 1개밖에 없고 물건을 쪼갤 수도 없는 경우.(0-1 Knapsack problem) 2. 물건 당 물건의 수량이 여러개이고, 쪼갤 수 없는 경우.(Bounded Knapsack problem) 3. 물건의 갯수가 무한개이고, 쪼갤 수 없는 경우(Unbounded Knapsack problem) 1. 0-1 Knapsack problem. 물건 당 물건의 수량이 1개이고, 물건을 쪼갤 수 없..

https://www.acmicpc.net/problem/3878 1. n의 점 집합에 대해 볼록 껍질을 만든다.2. m의 점 집합에 대해 볼록 껍질을 만든다.3. 두 볼록 껍질이 교차하는지 검사한다. 교차하면 NO. 교차안하면 YES다.종만북에서 소스를 가져왔다. #include #include #include #include #include #include #include #include using namespace std; const double EPSILON = 1e-8; const double PI = 2.0 * acos(0.0); // 2차원 벡터를 표현한다 struct vector2 { double x, y; explicit vector2(double x_ = 0, double y_ = 0)..

https://www.acmicpc.net/problem/12781 종만북에서 소스를 가져왔다. 벡터로 선분이 평행한지 조사해서 평행하면 0, 아니면 4조각으로 자를 수 있다는 뜻이므로 1을 리턴했다. #include #include #include using namespace std; const double PI = 2.0 * acos(0.0); struct vector2 { double x, y; vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_) {} // 두 벡터가 같은 경우 bool operator == (const vector2& rhs) const { return x == rhs.x && y == rhs.y; } // 벡터의 덧셈과 뺄셈, 단항 연산..

https://www.acmicpc.net/problem/9934 풀긴했는데 그닥 만족스럽지 못한 코드다. 이렇게 하는게 맞는건지... # -*- encoding: cp949 -*- import Queue def bfs(k): q = Queue.Queue() q.put([k,k/2]) while not q.empty(): p = q.get() temp = [] flag = False for e in p[:-1]: temp.append(e-p[-1]-1) temp.append(e+p[-1]+1) if e+p[-1]-1len(n)-1: flag = True print n[e], print if flag: return temp.append(p[-1]/2) q.put(temp) k=input() n = map(..

https://www.acmicpc.net/problem/1967 알면 간단하다. 어떤 한 점에서던지 가장 먼 노드의 거리를 구하면 그 노드는 가장 먼 두 점중 한 점이다. 그러니까 아무 점에서 시작해서 가장 먼 노드를 구한다. 그리고 그 노드에서 가장 먼 점의 거리를 구하면 그게 답이다. 아래 dfs함수에서 확인할수 있다. # -*- encoding: cp949 -*- def dfs(y): visited = [0 for i in xrange(10002)] s = [[y,0]] visited[y] = 1 max_weight,node = 0,1 while s: p = s.pop() if max_weight < p[1]: max_weight = p[1] node = p[0] for i in xrange(le..

https://www.acmicpc.net/problem/7562 #include #include #include #include using namespace std; int t,n,c[2],m[2]; int _y[]={-2,-1,1,2,2,1,-1,-2}; int _x[]={1,2,2,1,-1,-2,-2,-1}; int bfs(int c[2],int m[2]) { int visited[300][300]={0,}; queue q; vector t; t.push_back(c[0]); t.push_back(c[1]); t.push_back(0); q.push(t); while(!q.empty()) { vector p = q.front(); q.pop(); if(p[0]==m[0] && p[1]==m[1]) ..

https://www.acmicpc.net/problem/1509, https://www.acmicpc.net/problem/2079 1. 글자들을 팰린드롬 이 가능한지 나눠준다. [x,y]범위에서 팰린드롬이 가능한지 설정해준다. 이것을 dp리스트에 저장해둔다. 2. 나눠진 팰린드롬을 나눈다. 이게 dp2리스트의 일이다. # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(1000000) dp = [[0 for i in xrange(2502)] for j in xrange(2502)] dp2 = [0 for i in xrange(2502)] def divide(p): if p

참조 1 : http://blog.naver.com/jyuno426/220794422838 참조 2 : https://algospot.com/wiki/read/Manacher's_algorithm 회문에 관한 알고리즘이라고 한다. 각 문자를 중심으로 하는 팰린드롬을 알아내는 알고리즘이라고 함. 각 문자를 중심으로하기때문에 짝수 길이의 팰린드롬은 찾을수 없다고 한다. 찾으려면 더미 문자를 끼워넣어서 a#b#c#d#d#c#b#a 꼴로 만들면 된다고 한다. ex) aaa의 중심은 중간의 a이고, 팰린드롬은 a와 aaa두개가 있다. aabaa의 중심은 b이고 팰린드롬은 b, aba, aabaa가 있다고 한다. 알고리즘 부분은 알고스팟에서 그대로 가져왔다.알고리즘은 다음과 같다:i는 0부터 n−1(n=|S|)까지..

https://www.acmicpc.net/problem/11057 기초 dp # -*- encoding: cp949 -*- n=input() dp = [[0 for i in xrange(10)] for i in xrange(1020)] for i in xrange(10): dp[0][i] = 1 for i in xrange(1,n+1): for j in xrange(10): for k in xrange(j,10): dp[i][j] += (dp[i-1][k]%10007) dp[i][j] %= 10007 print dp[n][0]https://www.acmicpc.net/problem/1937 bfs같이 보였었는데 bfs를 쓰면 시간초과난다. 첫 코드는 대나무의 크기 순서대로 정렬한 후 크기 순서대로 방문..

https://www.acmicpc.net/problem/2573 파이썬으로 코딩하니 시간초과가 나서 C++로 바꿨더니 됬다. 망할. #include #include using namespace std; int n,m; int _count; int _y[] = {1,0,-1,0}; int _x[] = {0,-1,0,1}; int temp_arr[301][301]; void bfs(int y, int x) { int visited[301][301]={0,}; queue q; q.push(make_pair(y,x)); while(!q.empty()) { int p0 = q.front().first; int p1 = q.front().second; q.pop(); for(int i=0;in-1 || tx>m-..

https://www.acmicpc.net/problem/10868 http://qkqhxla1.tistory.com/734 의 세그먼트트리를 조금 변경한다. #include #include #include #include using namespace std; long long init(vector &a, vector &tree, int node, int start, int end) { if (start == end) { return tree[node] = a[start]; } else { return tree[node] = min(init(a, tree, node*2, start, (start+end)/2), init(a, tree, node*2+1, (start+end)/2+1, end)); } } ..

https://www.acmicpc.net/blog/view/9 의 내용을 정리해왔습니다. 예로 길이 N의 배열 A가 있고 여기서 L~R구간의 합을 M번 구해서 출력해야한다고 가정합시다. 수행해야 하는 연산의 시간복잡도는 O(M(R-L)) 번입니다. 그런데 앞에서부터 차례대로 합을 구해놓는 방식으로 문제를 풀어서 시간복잡도를 줄일수 있습니다. S[i] = A[1] + ... + A[i] 라고 했을 때, i~j까지 합은 S[j] - S[i-1]라고 할수 있습니다. 만약 A배열의 중간에 어떤 값이 하나 바뀐다고 하면 S[i]값은 A배열의 처음부터 다시 세서 만들어줘야 합니다. 따라서 M과 중간의 값이 변경되는 양이 너무 크게 되면 시간이 너무 오래걸리게 됩니다. (O(M*변경되는양)의 시간복잡도가 걸리겠죠...

https://www.acmicpc.net/problem/10827 a^b를 어떻게 정확하게 구현할수 있을까? 소숫점을 없애고 큰 수 상태로 곱셈을 한다. 그 이후에 문자열로 만들어서 소수점 처리를 해주면 된다. # -*- encoding: cp949 -*- a,b=raw_input().split() p = len(a[a.index('.')+1:]) a = a.replace('.','') result = str(int(a)**int(b)) p=str((10**p)**int(b)) index = len(result)-len(p)+1 if index >=0: print result[:index]+'.'+result[index:] else: print '0.'+'0'*(-index)+resulthttps://..

http://kks227.blog.me/220810623254 에서 가져와서 핵심만 정리했습니다. 어떤 그래프에서 유량을 흘리는데 최대 유량을 흘리고자 합니다. 그런데 최소한의 비용을 들여서 흘리는게 목적입니다. 비용은 간선마다 다르며, 어떤 간선의 비용이 d이고, 유량이 f만큼 흐른다고 하면 비용은 d*f입니다.(d*k라고 나와있는데 오타인 듯..) 예로 위에서 빨간색으로 유량이 흐른다고 할때 비용은 17입니다. 방법론 : 포드 폴커슨, 에드몬드 카프 알고리즘과 비슷한데 매번 찾는 경로가 최단 경로입니다. 매번 최단 경로를 찾고, 이 경로로 흐를수 있는 최대 유량을 흘려보내면서 경로값*유량을 더해주면 된다네요.(위의 d*f를 말하는듯) 주의점 : 음의 가중치가 있는 그래프에서도 잘 작동해야 함. 역방향..

https://www.acmicpc.net/problem/9461 # -*- encoding: cp949 -*- dp = [0 for i in xrange(150)] dp[1]=1 dp[2]=1 dp[3]=1 dp[4]=2 dp[5]=2 for i in xrange(6,101): dp[i] = dp[i-1] + dp[i-5] for t in xrange(input()): n=input() print dp[n]https://www.acmicpc.net/problem/10844 # -*- encoding: cp949 -*- dp=[[0 for j in xrange(10)] for i in xrange(102)] n=input() for i in xrange(10): dp[1][i] = 1 for i in x..

http://kks227.blog.me/220796029558 에서 핵심만 가져와 정리해왔습니다. 이 그래프에서 a와 e를 분리시키고 싶다고 합시다. 자르는 방법은 여러가지가 될 수 있지만 아래처럼 자를수 있습니다.이처럼 자르면 A,B,C와 D,E로 분리됩니다. 이렇게 그래프를 자르는걸 컷이라고 한답니다. 컷에는 비용이 있는데 위처럼 자르면 선이 3개가 잘리므로 비용이 3입니다. A바로 오른쪽에서 자르면 비용이 2로 A와 E를 분리시킬수 있겠네요. 이렇게 임의의 두 정점을 정하고, 두 정점을 다른 컴포넌트로 분리시키는 비용을 최소화하는걸 미니멈 컷이라고 한답니다. 이처럼 가중치가 있는 그래프라면 단순히 선을 조금 자르는것보다 비용을 생각해서 자르는게 효율적입니다. 이렇게 자르면 비용이 9로 A와 E를 자..

https://www.acmicpc.net/problem/2580 파이썬으로 짰는데 시간초과가 났다........ c로 다시 짜니까 됬다. #include #include #include #include #include using namespace std; int sudoku[9][9]; bool global_end_flag = false; void check(int row,int col,int t_sudoku[][9]) { int _sudoku[9][9]; for(int i=0;i

https://www.acmicpc.net/problem/11724 파이썬으로 짰더니 시간초과가 났다. #include #include #include #include using namespace std; int c = 0; int visited[1001]; vector graph[1001]; void dfs(int p) { if(visited[p]==0) c++; else return; visited[p] = 1; stack s; s.push(p); while(!s.empty()) { int p = s.top(); s.pop(); visited[p] = 1; for(int i=0;i

문제 카테고리 : https://www.acmicpc.net/problemset/?search=%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98 읽어볼것 : https://www.acmicpc.net/blog/view/28 몰랐던 코드. https://www.acmicpc.net/problem/2749 , https://www.acmicpc.net/problem/11444 를 풀기위한 코드. 행렬을 사용해서 하는거라함. n번째 피보나치 수를 구하는 코드. mod = 1000000 def gob(a,b): c = [[0,0],[0,0]] for i in xrange(2): for j in xrange(2): for k in xrange(2): c[i][j] += a[i][k] * b[k][..

https://www.acmicpc.net/problem/9251, https://www.acmicpc.net/problem/9252 LCS 란 어떤 두 문자열의 '모든 부분 수열' 중에서 가장 긴 길이를 말한다. 앞에서 했던 suffix automaton과 비슷한거 같지만 suffix automaton은 접미사가 같은 것들중 가장 긴것을 구하는거고 (즉 연속해서 나와야 한다.) 이건 연속해서 나오지 않아도 된다. http://blog.naver.com/power2845/220677085876 참고. 아래는 9252번 소스. 9151은 r[0]만 출력. def LCS(a,b): ret = [] LCS_length = 0 s1='0'+a s2='0'+b table = [[0 for i in xrange(l..

https://www.acmicpc.net/problem/2207 #include #include #include #include #include #include #include using namespace std; typedef pair P; const int MAX = 100001; int N, M, cnt, dfsn[MAX], SN, sn[MAX]; vector adj[MAX]; bool finished[MAX]; stack S; vector SCC; inline int oppo(int n){ return n%2 ? n-1 : n+1; } int DFS(int curr){ dfsn[curr] = ++cnt; S.push(curr); int result = dfsn[curr]; for(int next..