2110 공유기, 1939 중량제한, 1991 트리 순회

2110 공유기, 1939 중량제한, 1991 트리 순회

2110 공유기

n, c = map(int, input().split(' '))
array = []
for _ in range(n):
	array.append(int(input()))
array = sorted(array)
minval = array[1] - array[0] # 제일 짧은 거리 
maxval = array[-1] - array[0] # 제일 긴 거리
result = 0
while minval <= maxval: # 거리를 임의로 정해서(시작 값은 중간) 공유기 개수와 비교하며 조절
	gap = (minval + maxval) // 2
	value = array[0]
	count = 1
	for i in range(1, len(array)):
		if array[i] >= value + gap:
			value = array[i]
			count += 1
	if count >= c:
		minval = gap + 1
		result = gap
	else:
		maxval = gap - 1
		
print(result)

- bfs 개념 필요함 아래 링크 참고

www.youtube.com/watch?v=66ZKz-FktXo&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98

- 반복 학습 필요

 

1939 중량제한

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
def bfs(c): # bfs 함수 생성
	queue = deque([start_node])
	visited = [False] * (n + 1)
	visited[start_node] = True
	while queue:
		x = queue.popleft()
		for y, weight in adj[x]:
			if not visited[y] and weight >= c:
				visited[y] = True
				queue.append(y)
	return visited[end_node] # 끝까지 도달했는지 True, False로 반환
	
start = 1000000000
end = 1
for _ in range(m):
	x, y, weight = map(int, input().split())
	adj[x].append((y, weight))
	adj[y].append((x, weight))
	start = min(start, weight)
	end = max(end, weight) # 다리와 중량 정보를 받아 최대, 최솟값 구하기
	
start_node, end_node = map(int, input().split())

result = start
while start <= end:
	mid = (start + end) // 2
	if bfs(mid):
		result = mid
		start = mid + 1
	else:
		end = mid - 1 # 이진 탐색 수행
		
print(result)

- bfs 반복 학습

- 이진트리 반복 학습

 

1991 트리 순회

class Node:
	def __init__(self, data, left_node, right_node):
		self.data = data
		self.left_node = left_node
		self.right_node = right_node
		
def pre_order(node):
	print(node.data, end='')
	if node.left_node != '.':
		pre_order(tree[node.left_node])
	if node.right_node != '.':
		pre_order(tree[node.right_node])
		
def in_order(node):
	if node.left_node != '.':
		in_order(tree[node.left_node])
	print(node.data, end='')
	if node.right_node != '.':
		in_order(tree[node.right_node])
		
def post_order(node):
	if node.left_node != '.':
		post_order(tree[node.left_node])
	if node.right_node != '.':
		post_order(tree[node.right_node])
	print(node.data, end='')
	
n = int(input())
tree = {}
for _ in range(n):
	data, left_node, right_node = input().split()
	tree[data] = Node(data, left_node, right_node)
	
pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

- 딕셔너리 형태로 트리 쉽게 구현 가능

- 트리 만들때는 노드 클래스 생성

- 트리 순회시 재귀 함수 이용