one Book a Day

최대힙과 최소힙을 써 중앙 인덱스를 반출하기 쉬운 자료구조를 만든다. 양쪽 큐의 길이값 조절에 따라 중앙 인덱스뿐만아니라 일정 순위의 아이템에 접근하기도 용이하게 짤 수 있따. import sys import heapq n = int(sys.stdin.readline()) max_h, min_h = [], [] # max_h[0][1]값을 기준으로 큰 값은 min_h, 같거나 작은 값은 max_h에 삽입 for _ in range(n): num = int(sys.stdin.readline()) if len(max_h) == len(min_h): heapq.heappush(max_h, (-num, num)) else: heapq.heappush(min_h, (num, num)) # 왼쪽 힙의 큰값이 오른쪽..

import sys input = sys.stdin.readline from math import factorial N,K = map(int,input().split()) print((factorial(N)//(factorial(K)*factorial(N-K)))%10007) 사실 모듈써서 푸는게 의도는 아닐것 같은데 귀찮아서 썼다.. 본의도는 파스칼의 삼각형의 구현이었을 것 같아 관련코드도 가져왔다. n, k = map(int, input().split()) dp = [[0] * 1 for i in range(1001)] dp[1].append(1) for i in range(2, 1001): for j in range(1, i + 1): if j == 1: dp[i].append(1) elif j =..

딱히 소수판별을 체를 사용해서 할 필요는 없을 것 같아서 더한값들 개별적으로 진행해줬다. 조합은 DFS로 구성. import sys input = sys.stdin.readline def DFS(start,depth,sum_cow): if depth==M: if isPrime(sum_cow): answer.add(sum_cow) for i in range(start,N): if not visited[i]: visited[i]=True DFS(i+1,depth+1,sum_cow+H[i]) visited[i]=False def isPrime(n): if n

리스트쓰니까 시간초과나서 딕셔너리로 고쳐서 통과 역시 갓셔너리. import sys input = sys.stdin.readline N,M = map(int,input().split()) S = {} for _ in range(N): S[input().rstrip()] = 1 cnt=0 for _ in range(M): a = input().rstrip() try: if S[a] ==1: cnt+=1 except: continue print(cnt)

dp_dists 만들어서 거리 저장하고 max값 뽑는대로 동일한 애들 숫자 다 세주고 끝냈슴니당. 가중치가 모두 1로 같아서 그냥 BFS 돌렸슴니당. import sys input = sys.stdin.readline from collections import deque def BFS(start): queue = deque() queue.append(start) dp_dists[start] = 0 while queue: cur_node = queue.popleft() for next_node in graph[cur_node]: if dp_dists[next_node]==-1: dp_dists[next_node] = dp_dists[cur_node] + 1 queue.append(next_node) # 헛..

이문제는 시간조건이 조금 까다로웠다. heap에 들어가는 간선 갯수를 N^2개가 아닌 N개수준으로 맞춰야 하는 상황. 좌표거리에 대해 각각 정렬한 뒤 가장 가까운 좌표들로 push했다. 각 노드번호를 matrix에 더해주고 좌표거리와 노드번호로 heap에 정렬. 3(N-1) 개의 간선 조사로 크루스칼을 돌렸다. import sys input = sys.stdin.readline from heapq import heappop,heappush def kruskal(): min_dists = 0 while dists: dist,a,b = heappop(dists) if find(a) != find(b): union(a,b) min_dists+=dist return min_dists def find(x): if..

마을 최소 도로로 잇기.+ 2개마을로 분리(실상 간선 갯수만 마지막 하나 안그으면 마을이 2개가 된다,) import sys input = sys.stdin.readline from heapq import heappop,heappush def find(a): if parents[a] == a: return a parents[a] = find(parents[a]) return parents[a] def union(a,b): a = find(a) b = find(b) if b>a: parents[b] = a else: parents[a] = b # N개의 집 M개의 길(쌍방향) / 마을 분리. # 나머지 길의 유지비 합 최소 / 마을 2개로 분리,길 최소로. # 1번은 분리(유니온 파인드에서 마지막 하나만 ..

대놓고 MST문제이다. 간선위주고 거리값 구해서 heappush하고 최소 거리단위부터 잇고 이어져있으면 패스 안 이어진곳에서 최소 값을 heap을 통해 union하면서 거리값을 더해주는 kruskal로 해결. prim은 아직 못한다.. import sys input = sys.stdin.readline from heapq import heappop,heappush def kruskal(): answer = 0 while dists: ab_dists,star_a,star_b = heappop(dists) if find(star_a) !=find(star_b): answer += ab_dists union(star_a,star_b) return answer def union(a,b): a = find(a) ..

LIS는 예전에는 dp를 통해 이전값들을 검사해주며 모든 count를 계산해 풀었다면 이제는 이진탐색으로 직접dp수열을 관리하며 들어가야할 자리를 찾고 나보다 큰수는 나로 교체해주는 식으로 진행된다. 물론 내가 제일 크다면 그냥 오른쪽에 append한다. 이렇게하면 최종 dp에 남는 수열은 LIS는 안되지만 그 길이는 lis의 길이이다. 알고리즘은 의외로 heap을쓰는 회의실 배정문제와 비슷한 편. from bisect import bisect_left #이진탐색 코드, 같은 수일 경우 왼쪽 index를 돌려준다 input() A = list(map(int, input().split())) dp = [] for i in A: k = bisect_left(dp, i) #자신이 들어갈 위치 k if len(..

이건 그냥 평범한 dp였다. 그전 조건이있는 칸부터 떨어진만큼 제곱을 더해서 기록해주는 방식. import sys input = sys.stdin.readline N = int(input()) BOJ_avenue = input().rstrip() # 스타트 i i+1부터N번까지 점프 가능 K만큼 점프하는 에너지 k*k # 가장 가까운 BOJ를 순서대로 밟기. # 누적 -> dp(전 상태에 따라 변화값이 존재하는 조건.) dp = [float('inf')]*N dp[0] = 0 for i in range(1,N): for j in range(i): if BOJ_avenue[j]=='B' and BOJ_avenue[i]=='O': dp[i] = min(dp[i],dp[j]+ pow(i-j,2)) elif B..