공부 기록장

https://www.acmicpc.net/problem/14244 코드n, m = map(int, input().split())cnt = 0for i in range(n-1): print(cnt, i+1) # cnt가 n-m 이상이면 cnt는 그대로 유지가 되므로, 리프 노드에 노드들을 이어붙일 수 있게 됨 if n-m > cnt: cnt += 1 접근 방법- 연결을 어떤 식으로 하든, 리프 노드는 최소 2개 이상이다.- n개의 노드 중에서 m개의 노드가 리프 노드이면, n-m개의 노드가 리프 노드가 아니다.- n-m번은 순차적으로 연결을 해주고, 그 이후 연결은 마지막 노드에 전부 연결해 준다. 배운 점- 트리의 최소 리프 노드 개수를 토대로, 어떠한 방식으로 리프 노드를..

https://www.acmicpc.net/problem/17298 코드from collections import dequeimport sysinput = sys.stdin.readlinen =int(input())num = list(map(int, input().split()))ans = [-1] * nstack = deque()for i in range(n): while stack and num[stack[-1]]  접근 방법- 문제 자체는 단순하고 쉬워보이지만, 수열의 크기가 최대 백만일 수 있기 때문에 시간 복잡도를 고려해야 한다- 현재 값을 기준으로 더 큰 값을 '효율적으로' 찾을 방법이 필요하다- 순차적으로 배열을 처리하면서, 특정 조건을 만족하는 경우 값을 처리하는 자료구조로 "스택"을..

https://www.acmicpc.net/problem/11779 코드import heapqimport sysINF = int(1e9)input = sys.stdin.readlinen = int(input())m = int(input())graph = [[] for _ in range(n+1)]for _ in range(m): s, e, c = map(int, input().split()) graph[s].append([e, c])a, b = map(int, input().split())dist = [INF] * (n+1)prev_node = [0] * (n+1) # 최단 경로 출력을 위한 변수def dijkstra(a): q = [] heapq.heappush(q, (0, ..

https://www.acmicpc.net/problem/1238 코드# 다익스트라 두 번 쓰는 풀이import heapqINF = int(1e9)def dijkstra(start): distance = [INF] * (N+1) distance[start] = 0 q = [] heapq.heappush(q, (0, start)) while q: dist, now = heapq.heappop(q) if distance[now]  접근 방법- 플로이드 워셜로 풀면 되겠다고 생각했지만 시간 초과- N이 최대값인 경우 10억번의 연산이 필요하게 되고, 시간 초과 발생- 다익스트라를 2번 사용하는 풀이 참고 배운 점- 플로이드 워셜을 복습할 수 있었다- 다익스트..