그리디 (Greedy)
그리디 알고리즘은 현재 상황에서 최적이라고 생각되는 선택을 반복하여 최종적인 해답을 도출하는 알고리즘이다.
즉, "지금 당장 좋은 것만 선택하면 최종적으로도 최적의 해가 될 것" 이라는 전략을 따른다.
일반적으로 정렬이나 우선순위 큐(힙), 스택, 해쉬맵과 함께 적절히 사용된다.
적용 가능 조건 :
- 탐욕적 선택 속성 : 현재의 선택이 이후의 선택에 영향을 주지 않고, 항상 최적의 해를 만들 수 있어야 한다.
- 최적 부분 구조 : 부분 문제의 최적해가 전체 문제의 최적해를 구성해야 한다.
사실 정리하면서도 잘 와닿지 않는 특징들이었기에 문제를 풀어보면서 이해하고 정리해보려 한다.
_"문제를 풀어나가는 단계에 있어서 이 단계에서 현재 가장 좋은게 무엇인가를 선택하면 된다."
"보통의 그리디 문제는 모두 정렬이다. 정렬 후 차례차례 선택해 나가면 된다."
(이전에 듣던 강의에서 말씀해주신 내용이다.)
그리디 문제 1
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한 번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
핵심 전략 : 종료 시각을 기준으로 정렬하여, 종료 시각이 가장 빠른 회의부터 시작해 순차적으로 배정한다.
n = 5
timetable = [[1, 4], [2, 3], [3, 5], [4, 6], [5, 7]]
def solution(n, timetable):
cnt = 0
endTime = 0
timetable.sort(key=lambda x : (x[1], x[0]))
for times in timetable:
start, finish = times
if start >= endTime:
cnt += 1
endTime = finish
return cnt이 그리디 문제는 정렬 + 탐색만 사용해서 풀었다.
사실 이 문제는 복습하기 위해 다시 보았으며 이전에는 그리디 알고리즘을 처음 접하면서 깊게 생각하지 않고 넘어갔다. 다시 문제를 풀어보면서 종료 시간이 가장 빠른 회의를 첫번째로 시작하는 것이 이 단계의 최적해이며, 전체의 최적해라는 것을 이해했다. 그렇지만 이와 같은 그리디 문제를 보게 된다면 현 단계에서의 최적해를 찾기 위해서 논리적인 정의를 찾아낸다는 것이 쉽지는 않을 것 같다.
문제 속에서 그리디로 풀어야 하는 단서 찾는 법
- 현재 선택이 이후 선택에 영향을 주지 않는가?
- 현재 최선의 선택이 전체 최적해를 만들 수 있는가?
- 정렬하면 규칙성이 보이는가?
그리디 문제 2
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
핵심 전략 : 'A'와 바꾸길 원하는 알파벳과의 최소거리를 계산한다. 커서 이동의 최소 횟수를 계산한다.
def solution(name):
move_count = 0 # 알파벳 이동 횟수
length = len(name)
min_move = length - 1 # 커서 이동 횟수 (일단 끝까지 가는 경우로 초기화)
for i, char in enumerate(name):
move_count += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
# 연속된 'A'가 있을 경우 우회 가능
next_idx = i + 1
while next_idx < length and name[next_idx] == 'A':
next_idx += 1
min_move = min(min_move, 2 * i + length - next_idx, i + 2 * (length - next_idx))
return move_count + min_move먼저 알파벳 이동 횟수는 ord() 함수를 이용해서 알파벳 순으로의 이동 횟수와 거꾸로의 이동 횟수 중 더 최소 횟수로 정의했고,
커서 이동 횟수는 경우의 수를 3가지로 나누었다.
1. 오른쪽으로 쭈우욱 이동하는 경우 (일반적인 방식)
2. 오른쪽으로 가다 왼쪽으로(거꾸로) 가는 경우 (앞쪽에서 연속된 "A"가 있어 우로 이동하다가 거꾸로 좌로 이동)
3. 왼쪽으로(거꾸로) 가다 오른쪽으로 가는 경우 (끝쪽에서 연속된 "A"가 있어 좌로 거꾸로 먼저 이동하다가 우로 이동)
아래 그림은 2번째 경우("JBAAAONPML")와 3번째 경우("JBOCDEAAAN")이다.
