archives

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

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/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://..

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..

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..

https://www.acmicpc.net/problem/11277 https://www.acmicpc.net/problem/11280 #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)..

https://www.acmicpc.net/problem/2150 #include #include #include #include #include using namespace std; const int MAX = 10001; int V, E, cnt, dfsn[MAX], SN, sn[MAX]; vector adj[MAX]; bool finished[MAX]; stack S; vector SCC; int DFS(int curr){ dfsn[curr] = ++cnt; S.push(curr); int result = dfsn[curr]; for(int next: adj[curr]){ if(dfsn[next] == 0) result = min(result, DFS(next)); else if(!finished[..

9월 한달동안 진짜 밥먹고 코딩만 했습니다. 아래는 9월 25일쯤 찍어놓은 월간 순위입니다. 월간 2등... 오늘까지 400문제정도 풀었는데 캡쳐하려고 월간 순위 들어가보니 서버가 에러떠서 못보겠네요... 근데 저도 밥먹고 코딩만 했는데 1등은 잠도안자고 코딩만 했나보네요...

https://www.acmicpc.net/problem/1717 기본 문제. cin,cout쓰면 시간초과가 걸리므로 printf, scanf를 쓰자. #include #include #include #include using namespace std; // 트리를 이용해 상호 배제적 집합을 구현한다. struct OptimizedDisjointSet { vector parent, rank; OptimizedDisjointSet(int n) : parent(n), rank(n, 1) { for(int i = 0; i < n; i++) parent[i] = i; } // u 가 속한 트리의 루트의 번호를 반환한다 int find(int u) { if(u == parent[u]) return u; retur..

https://www.acmicpc.net/problem/5052 트라이를 이용하면 된다. 전화번호 목록을 받아서 긴 길이->짧은 길이 순으로 정렬한다. 그 후에 insert를 하기전에 이 전화번호가 다른곳에 포함되있는지 확인한다.#include #include #include #include #include #include #include #include using namespace std; const int ALPHABETS = 10; int toNumber(char ch) { return ch - '0'; } struct LinkedListNode { int elem; LinkedListNode* next; LinkedListNode(int _elem, LinkedListNode* _next) : ..

https://www.acmicpc.net/problem/5582 Suffix Automaton 문제. #include #include using namespace std; #define max(a,b) (a>b?a:b) const int MN = 270500; const int maxState = (MN id = size++; point->depth = dep; return point++; } void init() { point = pool; size = 0; root = sink = newState(0); } void insert(int a) { State *p = newState(sink->depth+1); State *cur = sink, *sufState; while (cur && !cur->g..

https://www.acmicpc.net/problem/9248 접미사 배열과 LCP를 구하는 문제. #include #include #include #include #include #include #include using namespace std; #define MAXN 500005 int N,SA[MAXN],lcp[MAXN]; char S[MAXN]; void SuffixArray() { int i,j,k; int m = 26; vector cnt(max(N,m)+1,0),x(N+1,0),y(N+1,0); for (i=1;i

https://www.acmicpc.net/problem/1927 최소 힙. # -*- encoding: cp949 -*- from heapq import * h = [] for n in xrange(input()): x=input() if x==0: if len(h)==0: print 0 else: print heappop(h) else: heappush(h,x) https://www.acmicpc.net/problem/11279 위는 최소 힙. 이번문제는 최대 힙이다. 파이썬에는 최대 힙이 구현되어 있지 않다. 어떻게 할까..? 스택오버플로우에서 봤는데 어떤분이 '최소 힙을 사용하되, 숫자를 넣을때 -로 넣고 뺄때 -를 붙이면 최대 힙이 되!' 라는 답글을 보고 천재라고 생각했다..... # -*- ..

https://www.acmicpc.net/problem/1671 상어의 저녁식사. 처음에 그냥 그래프로 모델링해서 냈는데 실패했다. 어떤분이 문제 조건에 있는 a상어가 b상어를 먹고, 먹힌 b상어가 a상어를 다시 먹는 이상한 현상이 발생할수 있다고 해주셔서 생각을 해봤으나 안되서.. 질문했더니 능력치가 같은 상어가 있을 경우 나중의 상어가 현재의 상어를 못먹게끔 설정해주면 된다고 하셨다. #include #include #include #include using namespace std; const int MAX_X = 2005; const int MAX_V = 2005; int V; int capacity[MAX_X][MAX_V], flow[MAX_X][MAX_V]; int ability[MAX_X]..

https://www.acmicpc.net/problem/1978 # -*- encoding: cp949 -*- def prime_number(max_n): p = [0 for i in xrange(max_n+1)] for i in xrange(2,max_n+1): for j in xrange(i,max_n+1,i): if j!=i: p[j] = 1 prime = [i for i in xrange(2,max_n+1) if p[i]==0] return prime input() n = map(int,raw_input().split()) print len([i for i in n if i in set(prime_number(1000))]) https://www.acmicpc.net/problem/2960 # ..

https://www.acmicpc.net/problem/2252 옛날의 위상정렬 코드를 가져와서 변경했다. http://qkqhxla1.tistory.com/640 #include #include using namespace std; int main() { int n,m,a,b; vector adj[33000]; int indegree[100001]={0,}; cin>>n>>m; for(int i=0;i>a>>b; indegree[b]++; adj[a].push_back(b); } queue q; for(int i=1;i

https://www.acmicpc.net/problem/1912 기초적인 dp문제. # -*- encoding: cp949 -*- n = input() num = map(int,raw_input().split()) dp = num[:] dp[0] = num[0] for i in xrange(1,n): dp[i] = max(dp[i], dp[i-1] + num[i]) print max(dp) https://www.acmicpc.net/problem/2293 일반적인 dp문제중 하나. # -*- encoding: cp949 -*- n,k = map(int,raw_input().split()) coin = [0] + [input()for i in xrange(n)] dp = [0 for i in xrange..

https://www.acmicpc.net/problem/2352 LIS를 구해주면 되는데 포트가 최대 40000개다. O(n^2)의 시간복잡도를 가지는 소스로는 시간 초과 에러가 뜨는데 lis는 최대 O(nlogn)으로 줄여줄 수 있다. 아래는 소스코드. #include #include #include using namespace std; int n,idx; int num; int arr[40001]; int main() { ios::sync_with_stdio(false); cin>>n; vector vt; vector::iterator itor; for(int i=0;i>arr[i]; vt.push_back(0); for(int i=0;i

https://www.acmicpc.net/problem/11053 https://www.acmicpc.net/problem/11568 https://www.acmicpc.net/problem/1965 기본적인 LIS문제. 세개다 똑같은 소스로 해결된다. O(n^2)의 시간복잡도 #include #include #include using namespace std; int n; int cache[1001], S[1001]; int lis(int start) { int& ret = cache[start+1]; if(ret != -1) return ret; ret = 1; for(int next = start+1; next < n; ++next) if(S[start] < S[next]) ret = max(re..

https://www.acmicpc.net/problem/19924개로 분할하여 푼다. # -*- encoding: cp949 -*- import sys def quad(x1, y1, x2, y2): flag = False #print 'h =',x1,y1,x2,y2, for i in xrange(y1, y2+1): for j in xrange(x1, x2+1): if maps[y1][x1] != maps[i][j]: flag = True break if flag: break if not flag: #print 'here =',x1,y1,maps[y1][x1] sys.stdout.write(maps[y1][x1]) if flag: h_x = (x1+x2)/2; h_y = (y1+y2)/2 sys.stdo..

https://www.acmicpc.net/problem/2098, https://www.acmicpc.net/problem/10971 유명한 TSP문제. dp와 더불어 비트마스크도 써야 한다. 문제에 안써있는데 1번 도시부터 출발해서 돌아오는 경우로 해야 한다. 1. 마을을 방문했다는 뜻의 visited변수는 정수 하나다.(리스트 아님.) visited변수의 비트를 이용해서 방문했는지 표시를 한다. ex) visited가 1이면 이진수로 1이므로 1번 도시를 방문했다. visited가 3이면 이진수로 11이므로 1,2번 도시를 방문했다. ... visited가 (2의n승)-1이면 이진수로 1111~~1111 이므로 1~n번까지 도시를 전부 방문했다라고 해석할수 있다. ex) n==4일경우 (2의4승-1..

https://www.acmicpc.net/problem/11375 기본적인 이분 매칭 #include #include #include #include using namespace std; const int MAX_N = 1001; const int MAX_M = 1001; int n, m; bool adj[MAX_N][MAX_M]; vector aMatch, bMatch; vector visited; bool dfs(int a) { if(visited[a]) return false; visited[a] = true; for(int b = 0; b < m; ++b) if(adj[a][b]) if(bMatch[b] == -1 || dfs(bMatch[b])) { aMatch[a] = b; bMatch[b]..