archives

파이썬으로짜면 시간초과가 나는걸 알기에 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

설명 잘 된 블로그 : http://kks227.blog.me/220796029558 블로그에 나온 것처럼 그래프에서 어떤 정점에서 다른 정점으로 갈 경우 최소값을 구하는 알고리즘이다. 다익스트라 알고리즘은 모든 비용이 음수가 아닐 경우에만 동작한다. 시간 복잡도 : O(|E|lg|V|) (정점 V, 간선 E) 그림은 위의 블로그에서 퍼왔다. 1. 정점 0이 시작점이고 여기서 출발하여 다익스트라로 각 점까지의 최솟값을 구한다고 하자. 각 점까지의 거리는 초기치를 무한대로 설정해놓는다. 2. 첫 정점에서 갈수 있는 점들을 큐에 저장해놓고 가장 비용이 적은 점부터 방문한다. 방문후 비용을 초기화해준다. 3. 다음 시작점중 비용이 가장 적은 1부터 방문한다. 왜 비용이 적은것부터 방문하냐면, 아래 그림의 3이..

https://docs.python.org/2/library/heapq.html 여기껄 클래스화시켰다. 큐의 순서는 출력해보면 알겠지만 우선순위에 따라서 출력된다.# -*- encoding: cp949 -*- from heapq import * class priority_queue(): def __init__(self): self.pq = [] # list of entries arranged in a heap self.entry_finder = {} # mapping of tasks to entries self.REMOVED = '' # placeholder for a removed task def put(self, task, priority=0): 'Add a new task or update the ..

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://1ambda.github.io/91/algorithm/algorithm-part2-4/ 시간복잡도는 하나하나 검사할경우 O(N*M)이지만 KMP는 O(N+M)이란다. 방법론.1. next배열을 만든다. 아래는 패턴 10100111에 대한 next배열을 만드는거다.사진에 대해서 설명하면.0) next배열을 구하기 위해서 위쪽과 아래쪽에 같은 문자열을 둔다. 아래쪽은 한칸 오른쪽인 상태로 시작한다.2) 불일치가 발생하면 아래쪽의 비교문자열을 불일치 이후에 첫글자가 첫번째로 일치하는 곳으로 이동시켜준다. 또 j==4일때 불일치가 발생했는데 불일치가 발생한 곳부터 1을 검색해보면 바로 뒤에 1이 있으므로 거기로 위치를 옮겨준다. 이런식으로 계속 한다.불일치가 발생하지 않으면, 아..

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

예전에 알고리즘 수업시간에 과제로 짜놨던건데 유용하게 쓰일것 같아서 올려놓는다. 언어는 c++이다. #include #include #include using namespace std; const int N = 500000; void printList(int a[], int n) { int i; for (i = 1; i l;i--) b[i-1] = a[i-1]; for(j=m;j=1; j/=2){ if(a[v] >= a[j]){ swap(a,v,j); v = j; } else break; } } void HeapSort2(int a[], int n) { ..

잘 설명된 블로그 : http://jinsolkim.kr/220069891025 먼저 선행되는 작업들 이후에 어떤 작업이 가능하다고 할 경우에 최소한의 시간을 구하는 그런 알고리즘. 아래는 코드. 입력값은 아래처럼 넣어보자. 4 4는 점 4개에, 간선이 4개라는 소리이고, 1 2는 노드 1에서 노드 2로가는 간선 하나가 있다는 소리이다. 나머지도 그런 소리이다. %입력이 다양하게 주어질 경우 그 중에서 가능한 한 경우만 출력한다. 다른 경우를 출력하려면 따로 돌려야 될듯 싶다. 4 4 1 21 32 43 4 # -*- encoding: cp949 -*- import Queue v,e = map(int,raw_input().split()) #노드,간선수 입력받음 adj = [[] for i in range..

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

이진 트리를 만들고 전위, 중위, 후위 탐색을 구현했다. 처음 배울때는 이걸 어떻게 짜냐... 했는데 지금 보니까 그리 어렵지도 않다. 아래에 main함수에서 addnode호출하는 부분을 보면 알수있듯이 1~10의 숫자를 무작위로 넣었다. 넣은 순서는 1->7->2->8->10->9->3->5->4->6 순서로 넣었고 이리 넣게 되면요렇게 이진 트리가 그려진다. 이걸 전위 중위 후위 순위하면 아래처럼 나온다. #include #include struct Node { int data; Node *leftchild; Node *rightchild; }; Node* newnode(int data) { Node* node = (Node *)malloc(sizeof(Node)); node->data = data;..

스택. 배열로 구현. #include int stack[100]; void push(int *top, int data) { if(*top>99) { printf("stack full\n"); return; } *top += 1; stack[*top] = data; } void pop(int *top) { if(*top==-1) { printf("stack empty\n"); return; } stack[*top] = -1; *top -= 1; } void print_stack() { int i; for(i=0;idata = data; newitem->next = NULL; s = head; } int pop(stack *s) { stack *temp = s; stack *last; int ret; whi..

단일연결리스트 c 코드. 개념 보고 짜봤는데 오랜만에 자료구조 공부하는거라 이 코딩이 맞는지 모르겠다. #include #include struct Node { int data; struct Node *next; }; Node* createnode(int data) { Node *n = (Node *)malloc(sizeof(Node)); n->data = data; n->next = NULL; printf("data = %d의 새 노드 생성\n",data); return n; } void deletenode(Node *n) { free(n); } void appendnode(Node *head, Node *n) { if(head->next == NULL) { head->next = n; printf("..

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