본문 바로가기
Algorithm/유형별 문제 풀이

Chapter 11. 탐욕 알고리즘

by mean. 2020. 8. 10.
728x90
반응형

탐욕 알고리즘 (기초 문제풀이)

혼자 힘으로 풀어 보기

거스름돈: https://www.acmicpc.net/problem/5585

문제 제목 : 거스름돈
문제 난이도: 하(Easy)
문제 유형: 그리디
추천 풀이 시간: 10분

문제 풀이 핵심 아이디어

  • 거스름돈의 최소 개수를 계산해야 합니다.

  • 가장 기초적인 탐욕 알고리즘 문제 유형입니다.

  • 단순히 '큰 화폐 단위' 순서대로 잔돈을 거슬러 주면 최적의 해를 얻을 수 있습니다.

  • '큰 화폐 단위' 순서대로 잔돈을 거슬러 줍니다.

  • 거슬러 줄 돈: 620

  • 거스름 돈의 개수: 0

  • 거슬러 줄 돈: 120

  • 거스름 돈의 개수: 1

  • 거슬러 줄 돈: 20

  • 거스름 돈의 개수: 2

  • 거슬러 줄 돈: 20

  • 거스름 돈의 개수: 2

  • 거슬러 줄 돈: 0

  • 거스름 돈의 개수: 4

  • 거슬러 줄 돈: 0

  • 거스름 돈의 개수: 4

  • 거슬러 줄 돈: 0

  • 거스름 돈의 개수: 4

소스코드

changes = 1000 - int(input())
count = 0

for i in [500, 100, 50, 10, 5, 1]:
    count += changes // i
    changes %= i

print(count)

혼자 힘으로 풀어 보기

뒤집기: https://www.acmicpc.net/problem/1439

문제 제목: 뒤집기
문제 난이도: 하(Easy)
문제 유형: 그리디
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

  • 문자열에 있는 숫자를 모두 0 혹은 모두 1로 만들어야 합니다.
  • 다음의 두 가지 경우를 모두 계산하면 됩니다.
  • 문자열 S의 길이는 100만 이하이므로, 시간 복잡도는 O(N)에 해결해야 합니다.

  • 구체적인 알고리즘 예시) 모두 1로 만드는 경우
    • 첫 번째 원소가 0인 경우
    • 2개씩 원소를 비교할 때, 1에서 0으로 바뀌는 경우

소스코드

data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우

if data[0] == '1':
    count0 += 1
else:
    count1 += 1

for i in range(len(data) - 1):
    if data[i] != data[i + 1]:
    # 다음 수에서 1로 바뀌는 경우
        if data[i + 1] == '1':
            count0 += 1
    # 다음 수에서 0으로 바뀌는 경우    
    else:
        count1 += 1

print(min(count0, count1))

혼자 힘으로 풀어 보기

등수 매기기: https://www.acmicpc.net/problem/2012

문제 제목: 등수 매기기
문제 난이도: 하(Easy)
문제 유형: 그리디
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

  • 예상된 등수와 실제 등수의 차리를 최소화해야 합니다.
  • 이를 위해서, 예상된 등수를 오름차순으로 정렬하면 됩니다.

소스코드

n = int(input())
array = []

for _ in range(n):
    array.append(int(input()))

# 오름차순 정렬 수행
array.sort()

# 불만도의 합 계산
result = 0
for i in range(1, len(array) + 1):
    result += abs(i - array[i - 1])

print(result)

혼자 힘으로 풀어 보기

배: https://www.acmicpc.net/problem/1092

문제 제목: 배
문제 난이도: 중(Medium)
문제 유형: 그리디
추천 풀이 시간: 35분

문제 풀이 핵심 아이디어

  • 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 계산해야 합니다.
  • 매 분마다, 모든 크레인에 대하여 옮길 수 있는 박스를 선택하여 옮기도록 합니다.
  • 박스를 무게 기준으로 내림차순 정렬한 뒤에, 무거운 것부터 옮기도록 하면 됩니다.
  • 시간 복잡도 O(NM)에 문제를 해결할 수 있습니다.
  • 크레인과 박스를 내림차순 정렬합니다.
  • 매 분마다, 모든 크레인에 대하여 옮길 수 있는 박스를 선택하여 옮기도록 합니다.

소스코드

import sys

n = int(input())
cranes = list(map(int, input().split()))

m = int(input())
boxes = list(map(int, input().split()))

# 모든 박스를 옮길 수 없는 경우
if max(cranes) < max(boxes):
    print(-1)
    sys.exit()

# 각 크레인이 현재 옮겨야 하는 박스의 번호 (0부터 시작)
positions = [0] * n
# 각 박스를 옮겼는지의 여부
checked = [False] * m
# 최적의 해를 구해야 하므로, 내림차순 정렬
cranes.sort(reverse=True)
boxes.sort(reverse=True)

result = 0
count = 0

while True:
    if count == len(boxes): # 박스를 다 옮겼다면 종료
        break
    for i in range(n): # 모든 크레인에 대하여 각각 처리
        while positions[i] < len(boxes):
            # 아직 안 옮긴 박스 중에서, 옮길 수 있는 박스를 만날 때까지 반복
            if not checked[positions[i]] and cranes[i] >= boxes[positions[i]]:
                checked[positions[i]] = True
                positions[i] += 1
                count += 1
                break
            positions[i] += 1
    result += 1
print(result)

탐욕 알고리즘 (핵심 유형 문제풀이)

혼자 힘으로 풀어 보기

센서: https://www.acmicpc.net/problem/2212

문제 제목: 센서
문제 난이도: 하(Easy)
문제 유형: 그리디
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

  • 최대 K개의 집중국을 설치해야 합니다.
  • 집중국들의 수신 가능 영역의 길이의 합을 최소화하는 것이 목표입니다.
  • 사실상 정렬만 수행하면 되므로 O(NlogN)으로 문제를 해결할 수 있습니다.
  • 각 센서들을 위치를 기준으로 오름차순 정렬을 수행합니다.

  • 문제의 요구 사항은, 정렬된 센서들을 최대 K개의 영역으로 나누는 것과 동일합니다.
  • K = 2일 때, 각 집중국의 수신 가능 영역은 다음과 같습니다.

  • 따라서, 문제의 알고리즘은 다음과 같습니다.
    • 각 센서를 오름차순 정렬합니다.
    • 각 센서 사이의 거리를 계산합니다.
    • 가장 거리가 먼 순서대로 K-1개의 연결 고리를 제거합니다.

소스코드

import sys

n = int(input())
k = int(input())

# 집중국의 개수가 n 이상일 때
if k >= n:
    print(0) # 각 센서의 위치에 설치하면 되므로 정답은 0
    sys.exit()

# 모든 센서의 위치를 입력 받아 오름차순 정렬
array = list(map(int, input().split(' ')))
array.sort()

# 각 센서 간의 거리를 계산하여 내림차순 정렬
distances = []
for i in range(1, n):
    distances.append(array[i] - array[i - 1])
distances.sort(reverse=True)

# 가장 긴 거리부터 하나씩 제거
for i in range(k - 1):
    distances[i] = 0
print(sum(distances))

혼자 힘으로 풀어 보기

도서관: https://www.acmicpc.net/problem/1461

문제 제목: 도서관
문제 난이도: 중(Medium)
문제 유형: 그리디
추천 풀이 시간: 40분

문제 풀이 핵심 아이디어

  • 일직선상의 각 책들을 원래의 위치에 놓아야 합니다.
  • 0보다 큰 책들과 0보다 작은 책들을 나누어서 처리합니다.
  • 두 개의 우선순위 큐를 이용하여 문제를 효과적으로 해결할 수 있습니다.
  • 마지막 책을 놓을 때는 다시 0으로 돌아올 필요가 없으므로, 가장 먼 책을 마지막으로 놓습니다.
  • 책의 개수(N) = 7, 한번에 들 수 있는 책의 개수(M) = 2
  • 음수와 양수에 대해여 개별적으로, M개씩 묶어서 처리합니다.
  • M개씩의 묶음 중에서 가장 거리가 먼 책만큼 이동해야 합니다.

소스코드

import heapq

n, m = map(int, input().split(' '))
array = list(map(int, input().split(' ')))
positive = []
negative = []

# 가장 거리가 먼 책까지의 거리
largest = max(max(array), - min(array))

# 최대 힙(Max Heap)을 위해 원소를 음수로 구성
for i in array:
    # 책의 위치가 양수인 경우
    if i > 0:
        heapq.heappush(positive, -i)
    # 책의 위치가 음수인 경우
    else:
        heapq.heappush(negative, i)

result = 0

while positive:
    # 한 번에 m개씩 옮길 수 있으므로 m개씩 빼내기
    result += heapq.heappop(positive)
    for _ in range(m - 1):
        if positive:
            heapq.heappop(positive)

while negative:
    # 한 번에 m개씩 옮길 수 있으므로 m개씩 빼내기
    result += heapq.heappop(negative)
    for _ in range(m - 1):
        if negative:
            heapq.heappop(negative)

# 일반적으로 왕복 거리를 계산하지만, 가장 먼 곳은 편도 거리 계산
print(-result * 2 - largest)

혼자 힘으로 풀어 보기

컵라면: https://www.acmicpc.net/problem/1781

문제 제목: 컵라면
문제 난이도: 중(Medium)
문제 유형: 그리드
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

  • 데드라인을 초과하는 문제는 풀 수 없다는 점을 기억해야 합니다.
  • 데이터의 개수(N)는 최대 200,000입니다.
  • 정렬 및 우선순위 큐를 이용하여 O(NlogN)의 시간에 해결할 수 있습니다.
  • 가장 먼저, 문제 데이터 중에서 데드라인을 기준으로 오름차순 정렬을 수행합니다.

  • 각 문제의 '컵라면 수'를 우선순위 큐에 넣으면서, 데드라인을 초과하는 경우에는 최소 원소를 제거합니다.

  • 우선순위 큐(Min Heap)의 크기: 0

  • 각 문제의 '컵라면 수'를 우선순위 큐에 넣으면서, 데드라인을 초과하는 경우에는 최소 원소를 제거합니다.

  • 우선순위 큐(Min Heap)의 크기: 1

  • 각 문제의 '컵라면 수'를 우선순위 큐에 넣으면서, 데드라인을 초과하는 경우에는 최소 원소를 제거합니다.

  • 우선순위 큐(Min Heap)의 크기: 1

  • 각 문제의 '컵라면 수'를 우선순위 큐에 넣으면서, 데드라인을 초과하는 경우에는 최소 원소를 제거합니다.

  • 우선순위 큐(Min Heap)의 크기: 2

  • 각 문제의 '컵라면 수'를 우선순위 큐에 넣으면서, 데드라인을 초과하는 경우에는 최소 원소를 제거합니다.

  • 우선순위 큐(Min Heap)의 크기: 2

  • 각 문제의 '컵라면 수'를 우선순위 큐에 넣으면서, 데드라인을 초과하는 경우에는 최소 원소를 제거합니다.

  • 우선순위 큐(Min Heap)의 크기: 3

  • 각 문제의 '컵라면 수'를 우선순위 큐에 넣으면서, 데드라인을 초과하는 경우에는 최소 원소를 제거합니다.

  • 우선순위 큐(Min Heap)의 크기: 3

  • 각 문제의 '컵라면 수'를 우선순위 큐에 넣으면서, 데드라인을 초과하는 경우에는 최소 원소를 제거합니다.

  • 우선순위 큐(Min Heap)의 크기: 4

소스코드

import heapq

n = int(input())
array = []
q = []

# 문제 정보를 입력 받은 이후에, 데드라인을 기준으로 정렬
for i in range(n):
    a, b = map(int, input().split(' '))
    array.append((a, b))
array.sort()

for i in array:
    a = i[0]
    heapq.heappush(q, i[1])
    # 데드라인을 초과하는 경우에는 최소 원소를 제거
    if a < len(q):
        heapq.heappop(q)

print(sum(q))
728x90
반응형

'Algorithm > 유형별 문제 풀이' 카테고리의 다른 글

Chapter 12. 백트래킹  (0) 2020.08.10
Chapter 10. 그래프 고급 탐색 알고리즘  (0) 2020.08.10
Chapter 09. 그래프 기본 탐색 알고리즘  (0) 2020.08.10
Chapter 08. 동적 프로그래밍  (0) 2020.08.10
Chapter 07. 고급 탐색 알고리즘  (0) 2020.08.10

관련글

티스토리툴바