[백준] 회의실 배정 (1931번)
그리디 알고리즘
수업에서 설명을 먼저 들어서, 어렵지 않게 풀었다.
회의 종료 시간이 가장 이른 회의부터 개수를 세는 방식으로 알고리즘이 구성된다.
(스스로 해결이 가능하려면 좀 더 노력해야겠다 😓)
n = int(input())
meetings = []
for i in range(n):
m = list(map(int, input().split()))
meetings.append(m)
meetings = sorted(meetings, key=lambda x: (x[1], x[0]))
end_time = 0
answer = 0
for m in meetings:
if m[0] >= end_time:
end_time = m[1]
answer += 1
print(answer)sorted 안에 지정한 값을 기준으로 정렬하기 위해 lambda를 썼다.
먼저 회의 종료 시간(x[1])을 기준으로 오름차순 정렬한 후, 회의 종료 시간이 같을 경우에는 회의 시작 시간(x[0])을 기준으로 오름차순 정렬했다.
[백준] 최댓값 (2566번)
다차원 배열
이 문제는 스스로 해결함
board = []
for i in range(9):
board.append(list(map(int, input().split())))
answer = -1
for idx, row in enumerate(board):
if max(row) > answer:
answer = max(row)
row_num = idx + 1
col_num = row.index(max(row)) + 1
print(answer)
print(row_num, col_num)[백준] 수 찾기 (1920번)
이진 탐색 (binary search)
완전 탐색으로 해결하려고 했더니, 코드 자체는 돌아가지만,
백준에 제출했을 때 시간 초과가 떴다.
결국 이진 탐색(binary search) 으로 중간 값부터 조회하는 방식으로 진행을 했다.
이건 이진 탐색이라는 걸 몰라서, 인터넷 서칭으로 풀었음 🥲
n = int(input())
arr = list(map(int, input().split()))
m = int(input())
test = list(map(int, input().split()))
arr = sorted(arr)
for t in test:
start = 0
end = n-1
found = 0
while start <= end:
mid = (start + end) // 2
if arr[mid] == t:
found = 1
break
elif arr[mid] < t:
start = mid + 1
else:
end = mid - 1
print(found)[백준] 랜선 자르기 (1654번)
이진 탐색 (binary search)
구글링 도움 받음
k, n = map(int, input().split())
length = [int(input()) for i in range(k)]
left = 1 # 최소 길이
right = max(length) # 최대 길이
while left <= right: # 최소 길이 ~ 최대 길이에서 이진 탐색
mid = (left + right) // 2
lan = 0 # 랜선 개수
for i in length:
lan += i // mid # 현재 길이(mid)로 각 랜선에서 자른 개수 구하기
if lan >= n: # 필요한 랜선 개수 이상으로 만들면
left = mid + 1 # mid+1 부터 right 까지 다시 탐색
else: # 필요한 랜선 개수 보다 적게 만들면
right = mid -1 # left 부터 mid1 까지 다시 탐색
# left 가 right 보다 커지면 자동으로 종료
print(right)이진 탐색에서 left는 알고리즘의 종료 조건으로서 사용되고,
이진 탐색 자체는 최댓값을 찾기 위해 right의 값을 조정해 가면서 답을 찾기 위한 알고리즘이다.
[백준] 나무 자르기 (2805번)
이진 탐색 (binary search)
혼자 품
n, m = map(int, input().split()) # 나무의 수 n, 필요한 나무 길이 m
trees = list(map(int, input().split())) # 나무의 높이
left = 1
right = max(trees)
while left <= right:
mid = (left + right) // 2
cut = 0
for tree in trees:
if tree > mid: # 이 부분에서 tree - mid > 0 으로 했더니 시간 초과 뜸
cut += tree - mid
if cut >= m: # cut이 m 이상이면 나무를 더 높게(적게) 자르도록 이동
left = mid + 1
else: # cut이 m 보다 작으면 나무를 더 낮게(많이) 자르도록 이동
right = mid - 1
print(right)조건문에서 tree - mid > 0 으로 했더니 시간 초과가 떴다.
이렇게 하면, 모든 나무에 대해 계산을 해야 하므로, 이진 탐색을 하는 의미가 없어진다고 한다.
그러므로 tree > mid 로 해야, 조건에 맞는 나무만 확인할 수 있어 시간 복잡도가 O(log n) 으로 유지된다.
흠.. 어렵드아 ㅠㅠ
