archives

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

설명 잘된 블로그 : http://blog.qwaz.io/problem-solving/scc%EC%99%80-2-sat (설명보면 힐링..) 위의 블로그에서 가져와서 정리해왔습니다. SCC. scc는 strongly connected component로 강한 연결 요소를 뜻한다. 강한 연결 요소는 다음 조건을 만족한다.1. 같은 scc안의 임의의 두 정점은 서로 도달 가능하다.2. 어떤 정점이나 간선도 1의 조건을 만족하면서 scc에 추가될 수 없다. 임의의 방향 그래프가 주어졌을때 scc를 찾는 알고리즘으로 코사라주의 알고리즘과 타잔의 알고리즘이 있다고 한다. 둘 모두 시간복잡도는 O(V+E)라고 하지만 쉬운 코사라주의 알고리즘만 가져옴. 1. 방향 그래프 G, 빈 스택 S, G의 간선 방향을 뒤집은 ..

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

설명 잘됨 : http://jinsolkim.kr/50194124086 n명의 사람들이 파티에 왔다고 하자. 레크리에이션 강사가 생일이 같은 사람들끼리 팀을 구성하라고 한다. 사람들이 서로 그룹을 만드는데, 생일이 같은 사람들 찾으면 둘은 한 그룹이 되고 또다른 사람들을 찾아나설것이다. 만약 다른 팀을 찾았는데 생일이 같으면 또 그룹이 합쳐질것이다. 이런것들을 표현하는 자료구조라고 보면 된다. 이를 구현하기 위해 3가지 연산이 필요하다. 1. 초기화, 2. 합치기, 3. 찾기. 따로 상호 배타적 집합으로 쓰이기보다는 최소 신장 트리 등 다른 자료구조의 안에 쓰인다고 한다. 아래 소스코드에 다 구현되있다. #include #include #include #include using namespace std;..

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

문자열 변수를 비교할땐 문자열의 길이가 있으므로 정수등과 다르게 오래걸린다. 예로 어떤 한 문자열 a가 있고 문자열 b가 있다고 하자. a가 b문자열 안에 들어있는지 확인하는데는 너무 오래걸린다. 이를 해결하기 위해 문자열 특화 자료 구조의 대표적인 예가 트라이다. 문제점은 필요로 하는 공간이 너무 크다는 점. 그래서 트라이로 접미사 트리를 만들수 있지만 사용하기가 어렵다고 한다.(접미사가 필요하면 앞에 글중 하나인 접미사 배열 부분을 주로 쓴다.) 문자열 집함 s={"BE","BET","BUS","TEA","TEN"}; 이 있다고 할때 이걸 트라이에 저장하면 아래처럼 된다. 이처럼 접두사 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을때 두 노드는 부모 자식 관계로 연결된다. 노드의 깊이가 늘어날수록 ..

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

아래 소스코드는 접미사 배열을 구하는 함수. 어떤 문자열의 모든 접미사를 사전순으로 정렬해둔것. 출처 : http://blog.myungwoo.kr/57 사진 뜻. 0번째 접미사 배열은 아래 문자열 banana의 5번째부터 끝까지다. == a 1번째 접미사 배열은 아래 문자열 banana의 3번째부터 끝까지다. == ana 2 : anana, 3 : banana, 4 : na, 5 : nana *같은 문자로 시작하는 접미사 배열은 인접해 있음. a로 시작하는 접미사배열은 0,1,2의 경우. b로 시작하는 접미사배열은 3, n은 4,5에 있다. LCP 란 i번째 접미사와 i-1번째 접미사의 '가장 긴 공통 접두사의 길이'라고 한다. ex) i번째 접미사 : a, i+1번째 접미사 : ana라고 하면 lcp..

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://en.wikipedia.org/wiki/Sieve_of_Eratosthenes # -*- 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*2,max_n+1,i): p[j] = 1 prime = [i for i in xrange(2,max_n+1) if p[i]==0] return prime print prime_number(100) #2~100까지 소수 목록을 리스트로 반환. 100 포함한..

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

n개의 정점이 있을때, 두개씩 짝지어 주는 방법론. 각각의 연결된 정점은 끝점을 공유하지 않는다. 아래의 왼쪽 그림처럼 끝점을 공유하면 안되고, 오른쪽의 녹색 라인처럼 2개씩 짝지어져야함. ex)1. 아래와 같은 그래프가 있다. 파란 선은 도달 가능함을 의미한다. A부터 시작해서 하나씩 매칭해보자. A에서 2로 도달 가능하므로 이어준다.2. B에서 매칭을 시도하는데 B에서도 2로 가는게 가능하다. A에서 2 대신 5와 매칭이 가능하므로 A-5로 다시 매칭을 해주고 B는 2와 이어준다. 이런식으로 매칭을 시켰을때 가장 많은 쌍을 구하는걸 최대 매칭 문제라고 한다.

https://www.acmicpc.net/problem/6086 주의할점 : a에서 b까지 가는 경로가 여러개 있을수 있어 대역폭을 더해줘야 함. #include #include #include #include using namespace std; const int MAX_V = 500; int V = 52; int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V]; vector adj[MAX_V]; int networkFlow(int source, int sink) { //memset(flow, 0, sizeof(flow)); for(int i=0;i> E; //V는 정점의 갯수, E는 대역폭의 갯수 //memset(capacity, 0, sizeof(capacity)); ..

현실세계의 인터넷이라고 가정하자. 서버 s에서 집 컴퓨터 t까지 경로가 여러개 있고, 각각의 경로에는 보낼수 있는 최대한의 대역폭이 있다. 집 컴퓨터 t에서 자료를 다운로드받는다고 하면 s에서 보낼 수 있는 대역폭의 최대량은 얼마일까? (받는 쪽에서는 들어오는 만큼 다 받을수 있다고 가정한다.) 를 구하는 문제이다. 역시나 설명 잘된 블로그 : http://kks227.blog.me/220796029558 1. s에서 t로 최대한 보낼 수 있는 대역폭의 양은 얼마일까? 아주 잠깐 살펴보면 (D에서 T로 가는) 2 + (E에서 T로 가는) 5 인 7이 일단 보이는 최대값임을 알수 있다. 하지만 만약 E로 도달할수 있는 길이 C에서 E하나뿐이고, C->E 대역폭이 4라면 E->T 대역폭이 5라도 최대 대역폭..

https://www.acmicpc.net/problem/1922, https://www.acmicpc.net/problem/1197 가장 기본적인 최소 신장 트리 문제. 둘다 문제가 동일하다. #include #include #include using namespace std; int n,m,a,b,c; vector adj[100001]; struct DisjointSet { vector parent, rank; DisjointSet(int n) : parent(n), rank(n, 1) { for(int i = 0; i < n; i++) parent[i] = i; } int find(int u) { if(u == parent[u]) return u; return parent[u] = find(pare..

역시나 이분 블로그 참조 : http://kks227.blog.me/220796029558 간선과 정점들이 있을때 서로 연결되서 가중치의 합을 최소인 트리가 스패닝 트리. 주의 : 사이클이 생기면 안된다, 한 정점에서 다른 정점으로 도달하여야 한다. 시간 복잡도는 ElongE라고 한다. 아래는 예시. 1. 아래와 같은 정점들과 간선들에 대한 가중치가 있다고 하자. 아직 하나도 연결 안됬다. 간선들을 가중치순서대로 오름차순으로 정렬한다.2. 가중치가 가장 낮은 AE부터 시작해서 서로 연결이 되어있지 않으므로 연결해준다. A와 E는 이제 하나의 집합으로 보자. 3. 순서대로 잇다 보면 3까지 아래처럼 잇게 된다. 4. 그다음 차례인 4를 이어야되는데 이걸 잇게 되면 사이클이 생기게 된다. 그러므로 잇지 않고..

https://www.acmicpc.net/problem/11404 플로이드. #include #include #include #include using namespace std; int n,m,v,a,b,c; int adj[101][101]; int w[101][101]; void floyd() { for(int k=1;kn>>m; for(int i=0;i>a>>b>>c; if(w[a][b]==0) w[a][b] = c; else w[a][b] = min(w[a][b], c); } floyd(); for(int i=1;i

https://www.acmicpc.net/problem/11657 이 카테고리의 바로 앞 다익스트라 알고리즘은 기본적으로 간선에 음수가 없다는 가정의 알고리즘이다. 하지만 이 문제의 벨만 포드 알고리즘은 간선에 음수가 있을수도 있다고 생각한다. 벨만 포드 알고리즘 : http://qkqhxla1.tistory.com/668 #include #include #include using namespace std; const long long INF = 999999999; int n,m,u,v,w; vector adj[801]; vector bellmanford(int src) { vector dist(501,INF); dist[src] = 0; int updated; for(int k=0;kn>>m; for..

잘 설명된 블로그 : http://kks227.blog.me/220796029558 (알고리즘 설명이 진짜 잘 되있네요) 앞의 다익스트라 알고리즘은 a에서 b로 갈때 가중치가 음수가 아니라고 가정한 상태에서 코딩을 한다. 하지만 이 벨만 포드 알고리즘으로 가중치가 음수일 경우까지 판별이 가능하다. 음수 검사까지 하므로 시간복잡도는 늘어나서 O(VE)이다. 사진은 역시 저 블로그에서 가져왔다. 0에서 2까지 가는 최소거리를 찾을때 다익스트라 알고리즘은 음수가 아니라고 가정한 상태이므로 8로 최소값을 잡는다. 그런데 진짜 최소거리는 1을 거쳐서 가는 5다. 이러한 음수판별까지하는게 벨만 포드 알고리즘이다. 그런데 음의 가중치가 있는 그래프를 판별시 항상 무한대 사이클을 염두해 두어야 한다.이 무한대 사이클을..