one Book a Day

구현을 처음풀때는 막막했지만 브루트포스에 대해 알고난 이후로 어렵게 느껴지지는 않는 문제. 이제는 왜 골드5인줄 알겠다. 벽을 어떻게 고를 것인가? 여유공간은 어떻게 산출할 것인가? import sys input = sys.stdin.readline from itertools import combinations from collections import deque def bfs(walls): q = deque() visited = [[False]*M for _ in range(N)] ret = 0 for wall in walls: i, j = wall lab[i][j] = 1 for v in virus: x, y = v q.append((x,y)) visited[x][y] = True while q: x..

중복조합 서로다른 n개의 원소 중, 중복을 허락하여 r개를 뽑는 것. nHr = (n+r-1)C(r) 조합에서의 중복만 허용하므로 순서는 여전히 상관하지 않는다.(조합) dfs에서 i+1이 넘어가면 조합, i가 넘어가면 중복조합 def dfs(idx, depth): if depth == r: print(*comb) for i in range(idx,n): comb[depth] = arr[i] dfs(i, depth + 1) n-1개의 칸막이를 뽑아야하는 요소들 r개 사이에 배치하는 경우의 수. = n-1개의 막대기로 구분된 영역에 요소를 집어넣는 경의의 수. nHr = n-1+r C n-1 = n-1+r C r 다음에 예제 풀어 첨부할 것.

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net fireball data를 어떻게 다룰것이냐? 나는 deque를 써서 반복문을 진행했고 중간에 이동연산은 dictionary를 이용해 각 속성을 모아줬다. 한번에 통과. import sys input = sys.stdin.readline from collections import deque def bfs(): cnt = 0 while fireballs: fi..

dfs로 통과시키긴 했는데 다른분들 답보니 그냥 w/리프노드의 수 이게 답이더라. 생각해보니 내 답도 결국 (총 물의 양)/(리프노드의 수) 이거였는데.. 통과된게 신기할 따름.. import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(cur_node, water): visited[cur_node] = True n = len(tree[cur_node])-1 if not n: ans.append(water) return unit = water/n for next_node in tree[cur_node]: if not visited[next_node]: dfs(next_node,unit) N, W = map(int, input()..

파라매틱 서치. k번 이상 자를 수 있는지 결정하는 문제. 자주나오는데 아직 좀 사고가 더디다. import sys input = sys.stdin.readline def is_minimum(mini): left = 0 cnt = 0 for right in cut_points: if right - left >= mini: left = right cnt += 1 if cnt > k: return True return False N, M, L = map(int, input().split()) cut_points = [int(input()) for _ in range(M)] + [L] for _ in range(N): k = int(input()) # M개의 지점 중 k개 선택. 사잇값의 최솟값이 가장 큰. ..

정렬해 작은 순으로 먹으면 되는 간단한 문제. import sys input = sys.stdin.readline N, L = map(int, input().split()) h_arr = list(map(int, input().split())) h_arr.sort() for h in h_arr: if L >= h: L += 1 continue break print(L)

냅색문제고 dp로 풀었습니다. import sys input = sys.stdin.readline for _ in range(3): N = int(input()) coins = {} target = 0 for _ in range(N): a, b = map(int, input().split()) coins[a] = b target += a*b if target&1: print(0) continue target //= 2 dp = [1] + [0] * (target) for coin in coins: for money in range(target,coin-1,-1): if dp[money-coin]: for j in range(coins[coin]): if money + coin*j

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS에서 연속성만 부여하면 된다. 같을때 대각선 위값을 계승. 틀릴때 그냥 0 import sys input = sys.stdin.readline str1, str2 = (input().rstrip() for _ in range(2)) n, m = len(str1), len(str2) dp = [[0]*(m+1) for _ in range(n+1)] max_v = 0 for i in ..

말 그대로 귀찮은 문제. 하지만 많이 보던 파일 합치기의 idea가 일부 사용된 문제기도 하다. 가장 작은 부분부터 해결하는게 최소 비용을 보장한다. import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr.sort() total = sum(arr) answer = 0 for num in arr: answer += num * (total - num) total -= num print(answer)

파서의 종류 상향식 : 구문의 낮은수준에서 높은 수준으로 일치하는 부분을 찾음. 항, 항연산자, 표현식, 표현식 연산자 순으로 일치하는 표현식을 하나씩 스택에 쌓음 =이동-감소 파서 : 입력값의 오른쪽으로 포인터가 이동하기때문에 구문 규칙에 남는 것이 점차 감소. ex.) 2+3-1 -> +3-1 -> 3-1 -> -1, 1, 하향식 : 상위 구조로부터 일치하는 부분을 찾음. 표현식부터 쌓음 파서 자동 생성 : 수동파서 최적화는 어렵기때문에 웹킷은 어휘생성을 위한 플렉스와 파서 생성을 위한 바이슨을 사용한다. 플렉스는 토큰의 정규표현식 정의를 포함하는 파일을 입력 받고 바이슨은 BNF 형식의 언어 구문 규칙을 입력 받는다. HTML 파서 마크업을 파싱 트리로 변환 문법은 W3C에 명세로 정의 전통적 파서..