archives

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

왠만하면 하루를 통째로 쉬지 않는데 오늘은 그냥 쉬었다. 쉬면서 덱스터 시즌 2를 끝냈고 그냥 멍하게 시간보내기도 하고 그랬다. 다음주가 벌써 개학인데 취업을 해야한다는 사실 때문인지 아니면 다른 이유인지는 모르겠는데 마음이 뒤숭숭하다. 매일 잠드는시간인 새벽 1시인데 자기가 싫다. 뭔가 불편하다.(취업 때문은 아닌거같다.) 가끔 저번 어딘가에 적은것처럼 이유없이 우울증같은거에 걸린것처럼 우울한 날이 있는데 오늘인가보다. 덱스터를 보면서, 보고나서도 그닥 만족감을 못느꼈다. 그냥 뭔가 빠지는 게임이라도 있으면 하루종일 할텐데 그런것도 없다. 아주 가끔 오버워치나 롤에 미쳐서 시간가는줄모르는애들이 부럽다. 옛날에는 미쳤었는데 요새는 시간이 있어도 할게없어서 인터넷으로 기사나 읽고 있다. 스트레스를 푸는 좋..

애들 다 하는 오버워치도 피방에서 한번 해봤는데 처음이라 그런지 그닥 재미가 없었다. 적당히 할수 있는 취미를 찾다가 좋은 미드를 찾았다. 연쇄살인마를 쫒은 연쇄살인마 이야기인 덱스터인데 나랑 맞는 미드인것 같다. 덱스터의 심리묘사나 생각이 인상적이다. 그래도 이걸 어느정도 보고 나면 특별한 다른 취미가 없어서 놀고싶어도 그냥 인터넷 검색이나 하는게 그리 좋은거같진 않다... 취직을 해야 마음이 편해지면서 맘놓고 뭔갈 할것 같다. 저번에 알고리즘 책을 샀었는데 그닥 안좋다. 1권은 400페이지짜리인데 얻은게 거의 없다. 솔직히 돈아깝다. 동적 계획법부분에서 어떻게 전략을 세울까 정도... 2권보고있는데 이건 아직까진 괜찮은거같다. 오늘 이것저것하느라 공부할시간이 별로 없었지만 그시간동안 kmp 알고리즘이..

잘 설명된 문서: 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>..

전에도 알고있었는데 그냥 그렇구나 하고 넘어갔던 문제이다. 알고리즘 문제를 풀면서 아 이랬어도 됬구나! 하면서 다시 깨달았다. 역시 코딩은 실전. 리스트에서 어떤 값을 찾는다고 했을때는 O(n)의 시간복잡도가 걸린다. 왜냐하면 하나하나 반복문을 돌면서 값이 맞는지 검사를 해야 하기 때문이다. 그런데 딕셔너리같은경우는 시간복잡도가 O(1)이다. 딕셔너리는 해쉬 테이블이기 때문에 메모리에 값을 직접 저장해놓기 때문이다. 즉 딕셔너리는 메모리를 조금 더 먹는 대신 어떤값을 찾을때 빠르다고 보면 되겠다. 알고리즘 문제를 풀때 파이썬의 특성상 시간초과가 나는 경우가 많이 있는데 이때 리스트대신 딕셔너리를 쓰면 해결될수 있을것 같다. http://stackoverflow.com/questions/513882/pyt..

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

알고리즘 문제를 푸는데 계속 막혀서.. 결국 비싼 책을 질렀다. 이것저것 찾아보고 평이 가장 좋은, 또 정렬이나 그런 이론적인 알고리즘보다는 문제풀이에 특화된 책이다. 가격도 45000원으로 오라지게 비싸 지만 미래를 위해 투자한다고 생각하고 하나 질렀다. 벤쿠버에서만 그런줄 알았던 감정 기복이 요새 점점 또다시 나타나기 시작한다. 이유없이 우울해지다가 괜찮아지다가 왜 공부하는지 모르겠다가 그냥 그렇다. 취업 걱정도 되고 그냥 마음이 복잡하다. 취업하게되면 그 이후로는 공부보다는 내 자신을 가꾸는(?) 쪽으로 노력해봐야겠다. 운동을 한다던지, 요리를 배운다던지, 여행을 간다던지 등등. 어느순간부터 취업때문에 저런것들을 하고싶어도 못한 것 같다. 코딩을 좋아해서 공부하는게 힘들거나 짜증나진 않은데 죽을때까..

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