one Book a Day

너무나 명백하게 플로이드 워셜을 쓰라고 문제에 주어졌다. 플로이드 워셜을 통해 거리배열을 얻어내고 치킨집 2마리를 조합으로 묶어내면서 각 거리의 합을 미니멈으로 비교하는 문제이다. 인접리스트를 사랑하는 입장에서 인접행렬문제는 늘 까다롭다. 아직 코드가 손에 안익어서 그럴수도.. import sys input = sys.stdin.readline N,M = map(int,input().split()) graph = [[float('inf') for _ in range(N)] for _ in range(N)] for i in range(M): a,b = map(int,input().split()) graph[a-1][b-1] = 2 graph[b-1][a-1] = 2 for i in range(N): gra..

문제해결에 선행또는 후행 하는 순서가 있으면 위상정렬을 이용하면 쉽게 풀 수 있다. 위상정렬이란 위상이 0 즉 앞뒤에 뭐가 없는 node부터 위로 찬찬히 쌓아 나가는 것. 위상0인 문제를 해결했으면 그 바로 연결된 노드들의 위상을 1씩 낮추면서 계산해 나간다. 나는 배열에 쌓기 위해서 앞에 나와야 하는 노드를 위상0으로 두었지만 반대로 뒤가 없는 노드들을 먼저 쌓고 역순으로 출력할 수도 있을 것이다. import sys from collections import defaultdict,deque input = sys.stdin.readline def topological_sorting(): queue = deque() for i in range(1, N+1): if level[i] == 0: queue.a..

모든 노드에서 모든 노드까지의 정보를 구해야하는 플로이드 워셜 문제다. 요새 최단거리 문제해결 연습을 많이하고있는데 플로이드 워셜의 핵심은 이것. "내가 저기 갈껀데 다른곳의 정보를 이용해서 가는게 빠르냐 아니면 그냥 가는게 빠르냐?" 이거다. 여기선 전자를 이용할 수 있느냐를 물어보는 문제. (다른곳의 정보는 나뿐만아니라 도착지에서도 알고있어야한다.) 알고있다면 1 아니면 0 import sys input = sys.stdin.readline N, M = map(int, input().split()) knowing_tall = [[0 for _ in range(N)] for _ in range(N)] # 플로이드 워셜은 인접행렬을 쓴다. for i in range(M): high, low = map(i..

LIS 시리즈 문제중 하나이다. 역순으로도 구해서 각 지점 카운트합이 가장 높아지는 부분이 꺽이는 부분. N = int(input()) A = [0] + list(map(int, input().split())) LDS = [1]*(N+1) LIS = [1]*(N+1) Bi = [] # 바이토닉 수열의 핵심은 앞에서 LIS하고 역순 LIS dp를 각각 만들어 # 두 dp 인자의 합 = 올라갔다 내려오는 cnt를 만드는 것. # 싸피 CT문제 예제로 나오는 문제라 아이디어는 매우 쉬웠다. for i in range(1,N+1): for j in range(1,i): if A[i]>A[j] and LIS[i]A[-j] and LDS[-i]

그냥 문제 나온대로 읽고 BFS만들어서 풀었다. 더 좋은 방법이 있을지도.. import sys input = sys.stdin.readline from collections import deque def BFS(i,j): candy_max = 0 queue = deque() queue.append([i,j]) visited_candy = [[-1 for _ in range(M)] for _ in range(N)] visited_candy[i][j] = maze[i][j] while queue: x,y = queue.popleft() if x==N-1 and y==M-1: if visited_candy[x][y] > candy_max: candy_max = visited_candy[x][y] for nx..

많은 방법이 있겠지만 나는 전체 다 구하는걸 좋아하므로 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]+..