오늘의 학습 키워드
GREEDY 욕심쟁이!
그리디란?
- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.
- 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있다.
- 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.
오늘의 문제
백준 13417번
https://www.acmicpc.net/problem/13417
입출력
그리디 적용해보기 (입력 예제 M K U 적용)
첫 번째 테스트 케이스: M K U
- 초기 상태: card = deque(['M', 'K', 'U']), result = deque([])
- 첫 번째 카드 M을 결과 덱에 추가 → result = deque(['M'])
- 두 번째 카드 K는 M보다 작으므로 앞에 추가 → result = deque(['K', 'M'])
- 세 번째 카드 U는 K보다 크므로 뒤에 추가 → result = deque(['K', 'M', 'U'])
결과: "KMU"
1. 기본 설정 및 입력 처리
T = int(input())
for i in range(T):
n = int(input())
card = deque(map(str, sys.stdin.readline().split()))
result = deque()T = int(input()): 테스트 케이스의 수를 입력받는다.- 각 테스트 케이스마다 n = int(input())으로 카드의 개수를 입력받고,
card = deque(map(str, sys.stdin.readline().split()))로 카드 목록을 입력받아 deque로 변환한다. deque는 양 끝에서의 삽입/제거가 빠르기 때문에 이 문제에 적합하다. result = deque(): 결과를 저장할 덱을 초기화한다.
2. 첫 번째 카드 처리
result.append(card.popleft()): 카드의 첫 번째 요소를 result에 추가한다.
3. 남은 카드들 처리
while card:
if card[0] <= result[0]:
result.appendleft(card.popleft())
else:
result.append(card.popleft())while card:: 남은 카드가 있는 동안 반복한다.if card[0] <= result[0]: 카드의 맨 앞 알파벳이 현재 결과 덱의 맨 앞 알파벳보다 작거나 같은 경우, 사전 순으로 앞서기 위해 result의 맨 앞에 추가한다.else: 그렇지 않다면 result의 맨 뒤에 추가한다.
4. 결과 출력
print(''.join(result)): 최종적으로 생성된 문자열을 출력한다.
왜 그리디로 풀까?
- 매 단계마다 사전 순으로 가장 빠른 선택을 하는 것이 목표이다.
- 즉, 현재 카드를 기존 결과 덱의 가장 왼쪽 또는 가장 오른쪽에 추가하는 선택을 반복적으로 수행하며, 매번 가장 최적의 선택을 하는 그리디 접근 방식이다.
- 이 문제는 카드 순서에 따라 한 번의 잘못된 선택이 최종 문자열을 사전 순으로 늦추기 때문에 매번 최선의 선택을 하는 것이 전체 결과에서 최적을 보장하게 된다.
전체 풀이
import sys
from collections import deque
T = int(input())
for i in range(T):
n = int(input())
card = deque(map(str, sys.stdin.readline().split()))
result = deque()
result.append(card.popleft())
while card:
if card[0] <= result[0]:
result.appendleft(card.popleft())
else:
result.append(card.popleft())
print(''.join(result))
오늘의 회고
🔥 큐를 그리디에 적용하는 생각을 하지 못했다.
