✅ 문제 풀이 - BOJ (이분 탐색)
🎈 2512 예산
정해져있는 국가예산 총액 하에 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다
- 모든 요청이 배정될 수 있는 경우 요청 금액을 그대로 배정한다.
- 모든 요청이 배정될 수 없는 경우 특정 정수 상한액을 계산해 그 이상인 예산요청에는 모두 상한액을 배정한다 상한액 이하의 예산요청에 대해서 요청 금액 그대로 배정한다.
입출력은 다음과 같다.
- 입력: 첫줄에는 지방 수 n, 둘째 줄에는 각 지방의 예산요청을 표현하는 n개의 정수, 마지막 줄에는 총 예산을 나타내는 m이 주어진다.
- 출력: 배정된 예산들 중 최대값인 정수를 출력하는 문제
import sys
input = sys.stdin.readline
n = int(input())
country = list(map(int, input().split()))
m = int(input())
start = 0
end = max(country)
while start <= end:
mid = (start + end) // 2
num = 0
for i in country:
if i >= mid:
num += mid
else:
num += i
if num <= m:
start = mid + 1
else:
end = mid - 1
print(end)< 풀이 과정 >
💯전형적인 이분 탐색 문제!
n, country(나라 별 예산 금액), m(총 예산 금액)을 입력받고, 이분탐색 진행을 위해 초기값 0, 끝 값 max(country)를 지정해준다.
while문으로 start <= end조건을 걸어 루프를 도는데 mid값을 부여하고 총 예산 비교를 위해 num도 0으로 지정한다.
이후 for문으로 country를 탐색하며 주어진 나라 별 예산이 mid보다 크면 mid를 num에 추가해주고 나라 별 예산이 더 작다면 나라 별 예산을 num에 추가해준다.
이후 계산된 예산 합이 총 예산 금액 보다 작다면 start를 mid보다 1크게 하며 다음 비교를 진행하고, 아닌 경우 end를 mid보다 1작게 만들어 다음 비교를 진행한다.
✅ 문제 풀이 - BOJ (Graph Search)
🎈 1068 트리
트리에서 리프 노드란 자식 개수가 0인 노드를 말한다.
트리가 주어졌을 때 노드 하나를 지울 것이다. 그때 남은 트리에서 리프 노드 개수를 구하는 프로그램을 작성하시오
입출력은 다음과 같다
- 입력: 트리노드 개수 n이 주어지고 둘째 줄에는 0번 노드부터 n-1노드까지 각 노드의 부모가 주어진다. 만약 부모가 없다면 -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
import sys
input = sys.stdin.readline
n = int(input())
tree = list(map(int, input().split()))
m = int(input())
def dfs(remove_node):
# 제거해야 하는 위치 -2 처리
tree[remove_node] = -2
# 부모노드가 remove_node값인 경우 재귀 탐색
for i in range(n):
if tree[i] == remove_node:
dfs(i)
dfs(m)
answer = 0
for i in range(n):
# 주어진 노드의 부모노드 삭제된 노드가 아니고, 리프노드가 없다면 + 1
if tree[i] != -2 and i not in tree:
answer += 1
print(answer)
< 풀이 과정 >
문제를 푸는데 있어 주요 핵심은 주어진 트리가 이진트리가 아닐 수도 있다는 점이다.
주어진 입력값을 순서대로 input 이후, dfs 함수로 탐색을 진행한다.
제거해야하는 노드를 dfs함수에 넣어 해당 value를 -2로 처리하고, 부모 노드가 remove_node인 자식 노드에 한해 dfs 재귀함수를 이용해 탐색을 실시한다.
dfs(m) : m번 노드를 제거한 이후 for문으로 모든 노드에 대해 확인하는데, 해당 노드의 부모노드가 -2가 아니고 리프노드가 없는 경우 + 1로 처리한다.
🎈 1967 트리의 지름
트리는 사이클이 없는 무방향 그래프로 트리의 지름은 트리에 존재하는 모드 경로들 중 가장 긴 것의 길이를 의미하고, 입력으로 루트가 있는 트리의 가중치가 있는 간선들로 줄 때 트리의 지름을 구하는 문제
입출력은 다음과 같다.
- 입력: 첫 줄엔 N개의 노드, 이후 N-1줄 만큼 간선에 대한 정보가 a, b, c로 주어진다. a는 부모 노드 번호, b는 자식 번호를 의미하고 c는 간선의 가중치를 나타낸다.
부모노드 번호가 작은 것이 먼저 입력되고, 부모 노드 번호가 같으며 자식 노드 번호가 낮은 것이 먼저 입력된다. (루트노드는 항상 1)- 출력: 트리 지름
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
distance = [-1] * (n+1)
distance[1] = 0
def dfs(node, dist):
for i in graph[node]:
next_node, d = i
if distance[next_node] == -1:
distance[next_node] = dist + d
dfs(next_node, dist + d)
dfs(1, 0)
start = distance.index(max(distance))
distance = [-1] * (n + 1)
distance[start] = 0
dfs(start, 0)
print(max(distance))< 풀이 과정 >
양방향 그래프로 (도착지, 거리)를 저장해준다.
distance라는 리스트를 -1로 (n+1)만큼 만들어주고, 시작지점은 0으로 값을 새겨준다.
이후 dfs 탐색을 활용해 노드와 간선 가중치를 매개변수로 입력하여 다음 노드에 한해 방문하지 않은 곳이면 가중치만큼 길이를 더해 주며 탐색을 진행한다.
루트 노드 ~ 리프 노드까지의 탐색을 1차로 진행하고 제일 가중치 합이 긴 노드를 시점으로 다시 탐색을 진행하여 지름을 구하면 되는 문제.
(루트 노드가 원의 중심이라는 말이 없어 2배를 해주어선 안되는 것이 핵심!)
