archives

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

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

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

파이썬으로짜면 시간초과가 나는걸 알기에 c++로 짰다. 파이썬 카테고리인데.... https://www.acmicpc.net/problem/1238 다익스트라 문제. 숫자가 적어서 (가는거 + 오는거) 계산하면 된다. #include #include #include using namespace std; const long long INF = 999999999; int n,m,x,u,v,w; vector adj[1001]; long long dist[1001]; void dijkstra(int src) { for(int i=0;i>n>>m>>x; for(int i=0;i>u>>v>>w; adj[u].push_back(make_pair(v,w)); } int max = -1; for(int i=1;i

https://www.acmicpc.net/problem/1753 한 10번넘게 시도해봤는데 다 시간초과가 뜬다. c++로 코드를 바꾸고 일부 설정을 바꾸니 통과하는걸로보아 그냥 파이썬이 느린 것 같다. 코드를 공부하면서 느낀건데 위상 정렬하고 알고리즘이 비슷한거같다. 추가. c++로 코드를 짤 경우 cin>>이 느리덴다. scanf가 빠르고. 또 coutE>>K; for(int i=0;i>u>>v>>w; adj[u].push_back(make_pair(v,w)); } dijkstra(K); for(int i=1;i>S>>K; dijkstra(S); cout

https://www.acmicpc.net/problem/1697 bfs문제. # -*- encoding: cp949 -*- import Queue short = 99999999 def bfs(n,k): global short visited = [[0,0,0] for i in xrange(1000000)] #-, +, *2 의 방법으로 방문했었는지 체크 q = Queue.Queue() q.put([n,0]) #첫번째위치와 거리 0으로 시작하므로 0. for i in xrange(3): #첫번째 위치는 다 방문했다고 초기화 visited[n][i] = 1 while not q.empty(): p = q.get() if p[0]==k: #도착했을때 가장 짧은 경로로 세팅 if short > p[1]: sho..

https://www.acmicpc.net/problem/1991 이진 트리를 구현하면 된다. 근데 일반적인 이진 트리와 조금 다르게 잘 구현하면 된다. 숏코딩을 보면 파이썬으로 내 코드보다 1/7길이로 구현해놨던데 그게 가능한지 궁금하다... # -*- encoding: cp949 -*- from __future__ import print_function class node: def __init__(self, data): self.left = 0 self.right = 0 self.data = data class binarytree: def __init__(self): self._node = node(0) def insert(self, data): self.cur_node = self._node if ..

https://www.acmicpc.net/problem/2193 앞의 1904번 문제하고 비슷하다.#1 = [1]#2 = [10]#3 = [100, 101]#4 = [1000, 1001, 1010]#5 = [10000, 10001, 10010, 10100, 10101] 아랫쪽 파란색은 위쪽 파란색에서 만들어지고 빨간색도 그렇다. 색 표시 안한것들은 -2칸전의 값+01한 값이다. 피보나치처럼 계산하면 될거라는걸 알수있다. # -*- encoding: cp949 -*- #1 = [1] #2 = [10] #3 = [100, 101] #4 = [1000, 1001, 1010] #5 = [10000, 10001, 10010, 10100, 10101] n = int(raw_input()) dp = [0 for i..

https://www.acmicpc.net/problem/9465 스티커를 하나 고르면 예시를 보고 대충 파악할수 있겠지만 다음 스티커는 대각선으로 골라야 한다. 그리고 예시에 나와있듯이 max(위에서 시작하는 대각선, 아래에서 시작하는 대각선) 은 답이 아니다. max(한칸전 대각선+현재 값, 두칸전 대각선+마지막 4칸중에서의 최대값) 이 답이다. # -*- encoding: cp949 -*- for t in xrange(int(raw_input())): dp = [[0 for j in xrange(100001)] for i in xrange(2)] n = int(raw_input()) st = [map(int,raw_input().split()) for i in xrange(2)] dp[0][1] =..

https://www.acmicpc.net/problem/6359 카테고리 분류는 dp인데 그냥 풀면 된다. # -*- encoding: cp949 -*- arr = [0]*101 t = int(raw_input()) for i in xrange(t): n = int(raw_input()) for j in xrange(1,n+1): #각 방을 돌면서 count = 1 for k in xrange(2,j+1): #상범이가 한번씩 왔다갔다하는거 계산 if j%k==0: count += 1 arr[j] = count #arr에 몇번 열고 닫는지 저장해둔다. inmate = 0 for j in xrange(1,n+1): #모든 방을 돌면서 if arr[j]%2==1: #홀수번이면 탈출할수 있다.(짝수번이면 닫힌..

https://www.acmicpc.net/problem/1213 # -*- encoding: cp949 -*- n_list = [0 for i in xrange(26)] name = raw_input() for c in name: n_list[ord(c)-65] += 1 answer = '' flag = True if len(name)%2==0: for i in xrange(26): if n_list[i]%2==1: print "I'm Sorry Hansoo" flag = False break if flag: for i in xrange(26): if n_list[i] > 0: for j in xrange(n_list[i]/2): answer += chr(i+65) print answer+answer[..

https://www.acmicpc.net/problem/1786 kmp코드로 탐색해서 보여주면 된다. 가장 기초적인 kmp문제다. # -*- encoding: cp949 -*- def getpartialmatch(N): m = len(N) pi = [0]*m begin = 1; matched = 0 while begin + matched < m: if N[begin + matched] == N[matched]: matched += 1 pi[begin+matched-1] = matched else: if matched == 0: begin += 1 else: begin += matched - pi[matched-1] matched = pi[matched-1] return pi def kmp(H,N): n..

https://www.acmicpc.net/problem/10828 stack = [] for i in xrange(input()): com = raw_input() if com[1]=='u': stack.append(int(com.split()[1])) elif com[0]=='p' and com[1]=='o': print -1 if len(stack)==0 else stack.pop() elif com[1]=='i': print len(stack) elif com[1]=='m': print 1 if len(stack)==0 else 0 elif com[1]=='o': print -1 if len(stack)==0 else stack[-1]https://www.acmicpc.net/problem/108..

https://www.acmicpc.net/problem/9012 스택을 이용하는 기본적인 문제이다. 스택을 이용해서 열리는괄호가 나오면 스택에 넣어주고, 아니면 스택에서 하나씩 빼서 괄호와 비교하면 된다. 물론 끝나고 나서는 스택에 아무것도 없어야 짝이 맞는다는 소리이므로 길이 체크도 해 주자. # -*- encoding: cp949 -*- bracket_dict = {'(':')'} for i in xrange(int(raw_input())): stack = [] flag = True for b in raw_input(): #print stack if b =='(': #열리는괄호면 스택에 넣고 stack.append(b) else: try: pop = stack.pop() #)같이 그냥 )가 들어왔을..

https://www.acmicpc.net/problem/11723 문제를 풀긴 풀었는데 파이썬이라 시간초과가 떠버린다. 파이썬으로 푼 사람이 없으면 못푸는 문제겠거니 하고 그냥 넘어가겠는데 푼사람이 한명 있어서.... 삽질을 엄청 해봤는데 시간초과를 극복할 방법이 안보인다. 비트마스크를 이용해서 빨리빨리 처리할수 있는것중 하나가 집합이랜다. 비트의 성질을 이용하는건데.. 1~5까지 저장하는 집합을 만든다고 하면 이진수 00000 이 있다고 가정하고, 맨 왼쪽부터 5,4,3,2,1 로 치고, 1이면 5라는 원소가 집합에 있고, 0이면 원소가 없다고 가정하며 프로그래밍하는 방식이다. 소스 1. set = 0 for i in xrange(int(raw_input())): com = raw_input() #입..

그리디(greedy) : 현재 상태에서 가장 최적의 답을 구함. 현재 상태에서의 최적의 답이 '최고'의 답이 아닐지라도 그냥 최적의 상태를 고름. 경우의 수가 너무 많은 경우 그냥 이 알고리즘을 씀. https://www.acmicpc.net/problem/1931 그리디 문제. # -*- encoding: cp949 -*- n = int(raw_input()) conf = sorted([map(int,raw_input().split()) for i in xrange(n)],key=lambda x:(x[1],x[0])) #입력받은후 끝나는 시간,시작되는 시간 기준으로 정렬 con_list = [conf[0]] for i in xrange(1,len(conf)): #돌아가면서 현재 맨 끝의 회의의 끝나는 ..

https://www.acmicpc.net/problem/1005 저번에 정리한 위상 정렬 이론을 보면서 했더니 됬다. http://qkqhxla1.tistory.com/630 파이썬으로 짰는데 시간초과떠서 c++로 짰더니 됬다. # -*- encoding: cp949 -*- import Queue answer = [] for t in xrange(int(raw_input())): n,k = map(int,raw_input().split()) d = map(int,raw_input().split()) adj = [[] for i in xrange(1001)] indegree = [0 for i in xrange(1001)] for i in xrange(k): a,b = map(int,raw_input()..

https://www.acmicpc.net/problem/2468 처음엔 파이썬으로 짰는데 시간초과가 떴다. 답은 맞다고 생각해서 C++로 바꿨더니 성공했다. # -*- encoding: cp949 -*- import Queue, copy def bfs(y,x,k): global temp_map visited = [[0 for j in xrange(n)] for i in xrange(n)] q = Queue.Queue() q.put([y,x]) temp_map[y][x] = safe_area visited[y][x] = 1 while not q.empty(): p = q.get() for i in xrange(4): y,x = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i] if y>..

https://www.acmicpc.net/problem/4963 쉬운 백트래킹 문제. bfs나 dfs로도 풀수 있을듯 # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(100000) answer = '' def backtracking(y,x): global land_count global maps maps[y][x] = land_count for i in xrange(8): ty,tx = y+[1,0,-1,0,-1,-1,1,1][i],x+[0,-1,0,1,-1,1,-1,1][i] if ty > h-1 or tx > w-1 or ty < 0 or tx < 0 or maps[ty][tx]!=1: continue backtracking(ty,tx) wh..

https://www.acmicpc.net/problem/1920 정렬 문제다. 아주 옛날에 별생각없을때 푼적이 있는데 그땐 그냥 반복문으로 다 검사하는식으로 해서 시간초과가 뜨고 안했었다. 이번엔 뭔가 공부도 하고있겠다 구현해서 멋있게 통과해보자!!!! 하는 마음이 갑자기 들어서 구현했다. 참고로 바로 아래 소스는 답이 아니다.# -*- encoding: cp949 -*- def BinarySearch(a,l,r,x): if l > r: print 0 #return else: mid = (l+r)/2 if x < a[mid]: BinarySearch(a,l,mid-1,x) elif a[mid] < x: BinarySearch(a,mid+1,r,x) else: print 1#'find!',a[mid],m..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=388&sca=3070 파이썬이라 그런지 알고리즘이 문젠지 처음에는 시간초과가 나왔었다. 시간초과임에도 60점을 주는거보니 답은 맞았다 싶어서 시간초과를 없애는데 주력했다. 처음에는 그냥 말그대로 반복문을 다 돌면서 '하나하나' BFS로 거리를 구했는데 시간초과가 떴다. 곰곰히 생각하다가 BFS안에서 답이 나올때마다 저장해주자는 식으로 코드를 작성했고, BFS가 끝난 후 반복문을 다시 돌때 이미 답이 있으면 그냥 무시하고 도는 식으로 코드를 짰다. 시간이 3800ms정도 걸리던게 940정도로 확 줄면서 통과했다. # -*- encoding: cp949 -*- import Queue answer = [[0 f..

https://www.acmicpc.net/problem/2638 치즈 문제. 중간에 주석 풀면 치즈가 어떻게 변해가는지 볼 수있다. bfs()함수로는 0,0를 외부 공기의 시작점으로 보고 근처에 있는 공기들은 다 외부 공기로 바꿨다. (외부 공기는 -1이다.) 그다음 면적 2개가 닿는지 판별해서 뭘 죽일지 살릴지 판별했다.# -*- encoding: cp949 -*- import Queue time_count = 0 def bfs(maps): visited = [[0 for j in range(m)] for i in range(n)] q = Queue.Queue() q.put([0,0]) visited[0][0] = 1 while not q.empty(): p = q.get() maps[p[0]][p[..

dfs : 끝까지 들어간후 다음걸로 넘어감. 스택으로 구현 가능(또는 재귀나 리스트 등등으로 구현 가능)bfs : 얇게 다 퍼진 후 그다음에 들어감. 큐로 구현 가능. acmicpc 1260번 문제를 대상으로 설명. https://www.acmicpc.net/problem/1260 도움 많이 됬던 블로그 : http://hyulim.tistory.com/345 + 책# -*- encoding: cp949 -*- import Queue def dfs(graph,v): global visited global answer stack = [] stack.append(v) while stack!=[]: j = stack.pop() if visited[j]==0: visited[j] = 1 answer += str..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=3030 앞에서 푼 백트래킹문제들과 크게 다를게 없다. 기본적인 처리만 조금 더 귀찮아졌고 큰 차이는 없다. # -*- encoding: cp949 -*- def divide(i,j): if i=n: return if maps[i][j]==0: maps[i][j] = count if i+1=0 and maps[i-1][j]==0: divide(i-1,j) if j+1=0 and maps[i][j-1]==0: divide(i,j-1) m,n,k = map(int,raw_input().split()) maps = [[0 for j in range(n)] for i in range(m)] for i..

https://www.acmicpc.net/problem/11726 피보나치 수열 문제처럼 동적 프로그래밍으로 풀면 된다. 2*1이면 1개, 2*2면 2개, 2*3 = 2*1개 + 2*2개, 2*n = 2*(n-1)+2*(n-2) 이다. # -*- encoding: cp949 -*- n = int(raw_input()) tile = [0 for i in range(1001)] tile[0] = -1 tile[1] = 1 tile[2] = 2 for i in xrange(3,n+1): tile[i] = (tile[i-1] + tile[i-2])%10007 print tile[n]https://www.acmicpc.net/problem/11727 11726이랑 거의 똑같다. 위 코드 중간에 식만 tile[i..

https://www.acmicpc.net/problem/2667 이거 하나 푸느라 한참 고생했다. count = 1 def check(i,j): maps[i][j] = count if i-1>=0 and maps[i-1][j]=='1': check(i-1,j) if i+1=0 and maps[i][j-1]=='1': check(i,j-1) if j+1=0 and field[i-1][j]==1: bug(i-1,j) if i+1=0 and field[i][j-1]==1: bug(i,j-1) if j+1

https://www.acmicpc.net/problem/1427 print ''.join(sorted(raw_input(),reverse=True))https://www.acmicpc.net/problem/1463 동적 계획법 문제. c 코드로 짤 경우 재귀로도 된다. http://blog.naver.com/swyu23/220757146631 처음에 요 분의 블로그와 비슷하게 짰는데 c로는 통과가 되는데 동일한 코드를 파이썬으로 바꿨을때 통과가 안 됬다. 그래서 아예 로직을 재귀를 안쓰도록 바꿨다. n = int(raw_input()) n_list = [-1 for i in range(1000001)] n_list[1] = 0 n_list[2] = 1 n_list[3] = 1 c = 4 while c ..

파이썬은 사기다. https://www.acmicpc.net/problem/1357a,b = raw_input().split() print int(str(int(a[::-1])+int(b[::-1]))[::-1]) https://www.acmicpc.net/problem/1252a,b = map(lambda x:int(x,2),raw_input().split()) print bin(a+b)[2:]https://www.acmicpc.net/problem/1212print bin(int(raw_input(),8))[2:] https://www.acmicpc.net/problem/1316# -*- encoding: cp949 -*- word = [raw_input() for i in range(int(raw_..

https://www.acmicpc.net/problem/1297 1297번 TV크기. import math t = map(int,raw_input().split()) for i in range(2): print int(math.sqrt(t[0]**2 / float(t[1]**2 + t[2]**2)) * t[i+1]), https://www.acmicpc.net/problem/1251 1251번 단어 나누기. word = raw_input() new_word = [] for i in range(1,len(word)): for j in range(i,len(word)): for k in range(j+1,len(word)): #new_word = word[0:i] +' '+ word[j:k] +' '+ w..