one Book a Day

많은 방법이 있겠지만 나는 전체 다 구하는걸 좋아하므로 counter썼다. from collections import Counter n,d = input().split() n_list = ''.join(map(str,list(range(1,int(n)+1)))) b = Counter(n_list) print(b[d])

워낙 유명한 문제. 사용중인 회의실의 end시간기준 최소힙을 만들어 start기준 오름차순 정렬된 input과 비교하면 간단히 풀린다. import sys input = sys.stdin.readline from heapq import heappop,heappush N = int(input()) meeting_schedule = [list(map(int,input().split())) for _ in range(N)] meeting_schedule.sort() cnt = 0 heap = [] for start,end in meeting_schedule: if not heap or heap[0] > start : cnt +=1 heappush(heap,end) else: heappop(heap) heapp..

최단거리 문제연습. 모든 정점에서 모든 정점. 주의 할 점은 동일 출발, 동일 도착 간선이 있고 때문에 입력 시 최솟값만을 입력해주어야함. 플로이드 워샬은 간선이 없는 전 구간에 대해 조사하기 때문에 사실 인접리스트의 의미가 좀 없는 것 같다. 인접행렬로 표현하는게 더 효율저일듯 싶다. import sys input = sys.stdin.readline def floid_washal(): dp_dists = [[float('inf') for _ in range(n+1)] for _ in range(n+1)] for cur_node in graph: for next_node,dist in graph[cur_node]: if dp_dists[cur_node][next_node] > dist: dp_dists..

커맨드가 주어지고 최종값을 뽑는 문제는 실제 커맨드대로 다 하면 망한다. index만 바꾸거나 slice를 한다거나 최대한 소요를 줄이는 방법으로 사고하자. import sys input = sys.stdin.readline from collections import deque # R 뒤집기, D 버리기함수 # 비어있을때 D쓰면 에러. T = int(input()) for test in range(T): p = input().rstrip() n = int(input()) xi = input().rstrip().rstrip(']').lstrip('[').split(',') Xi = deque() if not n: xi.pop() flag=0 switch = 0 for x in xi: Xi.append(x)..

최단거리 알고리즘 연습하는중. 음수 간선이 있을 시 다른 모든 정점으로 가는 최단거리를 구하는 문제이다. 밸만포드로 구했다. import sys input = sys.stdin.readline def bellman_ford(start): dp_dists[start] = 0 # 모든 정점 수만큼 검사 for i in range(N): # 매 정점마다 모든 간선 검사(그 점에서 타 점까지) for cur_node in graph: for next_node, dist in graph[cur_node]: # 방문 안했거나 다음점보다 지금 가는 경로가 더 짧으면 갱신 if dp_dists[cur_node] !=float('inf') and dp_dists[next_node] > dp_dists[cur_node]+..

최단 경로 알고리즘. 주요 알고리즘 BFS (완전탐색 알고리즘) 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다 다익스트라 알고리즘 (Dijkstra Algorithm) 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm) 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 전체 쌍 최단 경로 문제, 다수출발, 단일도착 하나의 정점에서부터 다른 하나의 정점까지의 최단 경로를 구하는 경우 A*알고리즘이 적합하다. 다익스트라 특정 노드에서 다른 모든 노드로 가는 최단경로를 갱신. 음의 간..

아이디어 1. 추 무게의 합을 전부 구해서 dp에 체크 2. 모든 무게에 다시한번 추를 빼주며(반대쪽 저울에 올려놓으며) dp체크 사실 같은 추를 두번사용하는 즉 왼쪽에도 오른쪽에도 올려놓는 경우를 체크하기는 하나 양쪽에 올려봤자 안올렸을 때의 dp와 같으므로 문제없다. (같은걸 두번 더하거나 두번뺄때가 아니면 결과 집합은 같다.) import sys input = sys.stdin.readline chu_N = int(input()) chu_list = list(map(int,input().split())) glass_ball_N = int(input()) ball_list = list(map(int,input().split())) dp_chu = {i:False for i in range(sum(ch..

숨바꼭질보다 조금 쉬운 하위문제 느낌? 어차피 이동의 모든 가중치는 같으므로 따로 우선순위큐나 appendleft없이 차례로 탐색하면 된다. 어차피 먼저 도착하면 먼저 출력된다. import sys input = sys.stdin.readline from collections import deque def BFS(F,S,G,U,D): dp_count = {i:float('inf') for i in range(1,F+1)} dp_count[S] = 0 queue = deque() queue.append(S) while queue: cur_stair = queue.popleft() if cur_stair == G: print(dp_count[G]) return for next_stair in (cur_sta..

루트노드를 줬으니 루트노드부터 BFS로 전위순회 하며 부모를 기록해줬다. import sys input = sys.stdin.readline from collections import deque # BFS로 루트부터 전위순회. def BFS(start): queue = deque() visited = [False]*(N+1) visited[start] = True queue.append(start) while queue: cur_node = queue.popleft() for next_node in graph[cur_node]: if not visited[next_node]: visited[next_node] = True super_node[next_node] = cur_node queue.append(..

에라토스테네스의 체 란? 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 단일 숫자 소수 여부 확인 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다. 만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다. 소수 구하기 n=100 def isPrime(a): if(a 소수의 배수들을 배제하는 방법으로 남는 소수를 가져갈 수 있지 않을까? 에라토스테네스의 체 원리 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당..