본문 바로가기

백준99

마인크래프트-18111번 python3에서 시간초과가 뜨면 pypy로 제출하면 정답이다. import sys y_axis, x_axis, inven = map(int,input().split()) graph = [] for i in range(y_axis): inn = list(map(int,sys.stdin.readline().split())) graph.append(inn) avg = 0 for i in graph: avg += sum(i) avg = avg//(x_axis*y_axis) avg_cost = [inven,0,avg] for y in range(y_axis): for x in range(x_axis): gap = graph[y][x] - avg if gap>0: avg_cost[1] += gap*2 avg_co.. 2022. 11. 8.
키로거 - 5397번 덱을 2개를 만든다. 하나는 비밀번호를 담아둘 덱이고, 나머지 하나는 화살표로 이동했을 경우 기존 비밀번호에서 pop하여 잠시 담아둘 덱이다. 패스워드는 스택형식으로 받고 화살표로 이동해서 비밀번호의 중간을 수정할 때를 위하여 잠시 담아두는 덱도 스택처럼 이용하였다. 도움되었던 반례 : 1 >>>ABC->>e 2022. 11. 7.
절댓값 힙 - 11286번 최대힙을 사용할 때 처럼, 위치를 결정해주는 키 값에 조작을 가하는데, abs( )를 사용하여 절댓값으로 사용한다. import sys import heapq t = int(input()) h = [] result = [] for _ in range(t): inn = int(sys.stdin.readline()) if not inn and h: r = heapq.heappop(h) result.append(r[1]) print(r[1]) elif not inn and not h: result.append(0) print(0) else: heapq.heappush(h,(abs(inn),inn)) # print(result) 2022. 10. 31.
후위 표기식 - 1918번 입력받은 식을 하나씩 꺼내면서 각 기호마다 해야할 역할을 조건문 내부에 적어주었다. 곱셈 나눗셈이 나왔을 때, 덧셈 뺄셈이 나왔을 때, '(' 가 나왔을 때, ')' 가 나왔을 때 각 4 가지 경우에 대해 만들어줘야한다. 그리고 식 탐색이 끝났을 때 스택에 남아있는 기호들을 pop으로 빼준다. 도움된 반례 input : A*B-C*D/E output : AB*CD*E/- from collections import deque inn = input() stack = deque() result = '' math = ['(',')','*', '/','+','-'] for i in range(len(inn)): t = inn[i] if t==math[0]: stack.append('(') elif t==math[.. 2022. 10. 31.
최대 힙 - 11279번 파이썬의 heapq는 최소힙만 사용가능하다. 최소힙만 가능한 상황에서 최대힙을 사용하고 싶으면 heappush에서 (-1 * 값, 값) 을 넣어주면된다. heappop 시에는 반환값의 인덱스 1 값을 사용하면 원래의 값을 이용할 수 있다. import sys import heapq t = int(input()) h = [] for _ in range(t): inn = int(sys.stdin.readline()) if not inn and h: r = heapq.heappop(h) print(r[1]) elif not inn and not h: print(0) else: heapq.heappush(h,(-1*inn,inn)) 2022. 10. 31.
최소 힙 - 1927번 파이썬의 모듈 heapq는 중복을 허용하지 않고, 작은 값을 root에 두도록 정렬하는 최소힙구조이며, pop을 할 경우 root의 값이 없어지면서 반환된다. import sys import heapq t = int(input()) h = [] for _ in range(t): inn = int(sys.stdin.readline()) if not inn and h: r = heapq.heappop(h) print(r) elif not inn and not h: print(0) else: heapq.heappush(h,inn) 2022. 10. 31.
덩치 - 7568번 본인보다 덩치가 큰사람이 k 명있으면 본인의 등수는 k+1이 된다는 것에 유의하며 2중for 문을 돌려주었다. import sys t = int(input()) w = [] h = [] for _ in range(t): a,b = map(int,sys.stdin.readline().split()) w.append(a) h.append(b) i = 0 j = -1 result = [t for _ in range(t)] for i in range(t): r = 1 for j in range(t): if i==j: continue if w[i] < w[j] and h[i] < h[j]: r+=1 print(r,end=' ') 2022. 10. 31.
최대공약수와 최소공배수 - 2609번 유클리드 호제법으로 최대공약수를 구한다. 최소공배수 = "두수의 곱 / 최대공약수" 이다 a,b = map(int,input().split()) if a < b: a,b = b,a def gcd(a,b): while a%b != 0: a, b = b, a%b return b def lcm(a,b, gcd_result): return int(a*b/gcd_result) gcd_result = gcd(a,b) lcm_result = lcm(a,b,gcd_result) print(gcd_result) print(lcm_result) 2022. 10. 30.
부녀회장이 될테야 - 2775번 다이나믹 프로그램으로 해결하였다. 0층에 대한 사람수를 저장해 놓은 배열을 준비한 후, 1층씩 올라가면서 각 호실에 몇명이 있어야 하는지 계산하여 넣어준다. k층까지 반복해준뒤, n호실에 몇명이 있는지 출력해준다. import sys t = int(input()) for _ in range(t): a = [i for i in range(15)] k = int(sys.stdin.readline()) n = int(sys.stdin.readline()) for i in range(k): for j in range(1,15): if j == 1: a[j] = 1 else: a[j] = a[j-1] + a[j] print(a[n]) 2022. 10. 26.
균형잡힌 세상 - 4949번 deque를 이용하였다. (stack기능만 사용) 소괄호와 대괄호가 번갈아 들어왔을 때 pop하기 전에 가장 마지막으로 어떤 종류의 괄호가 들어왔었는지 확인이 필요하다. for 문이 끝나고 stack 이 비어있어야 yes이다. from collections import deque while True: inn = input() if inn=='.': break stack = deque() can_yes = True for i in inn: if i=='(': stack.append(i) elif i=='[': stack.append(i) elif i==')': if stack and stack[-1]=='(': stack.pop() else: can_yes = False break elif i==']': .. 2022. 10. 26.
덱 - 10866번 기존에 파이썬에 있는 deque를 사용한다. import sys from collections import deque t = int(input()) deque = deque() for _ in range(t): # print(deque) instruct = sys.stdin.readline().strip() if instruct[:4] == 'size': print(len(deque)) elif instruct[:4] == 'fron': if deque: print(deque[0]) else: print(-1) elif instruct[:4] == 'back': if deque: print(deque[-1]) else: print(-1) elif instruct[:4] == 'empt': if deque.. 2022. 10. 26.
큐 - 10845번 입력 받을 때, sys.stdin.readline().strip()을 써줘야 속도가 빨라진다. 큐 사용을 위해 deque를 가져왔다. 큐가 비어있는지 확인하려면 if que: 로 확인해주면 된다. 비어있으면 False를, 뭔가 들어있으면 True를 반환한다. import sys from collections import deque t = int(input()) que = deque() for _ in range(t): # print(que) instruct = sys.stdin.readline().strip() if instruct[:4] == 'push': que.append(instruct[5:]) elif instruct[:3] == 'pop': if que: r = que.popleft() pri.. 2022. 10. 26.

티스토리툴바