나동빈님의 책과 유튜브 강의인 '이것이 코딩 테스트다'를 바탕으로 스스로 공부한 내용을 정리한 글입니다.
참고한 영상의 링크는 아래와 같습니다.
이것이 코딩테스트다 - 그리디 & 구현
그리디 알고리즘
그리디 알고리즘은 현재 time-step에서 가장 좋은 선택지를 선택해 문제를 해결하는 알고리즘이다. 현재 time-step에서 가장 좋은 선택지를 선택하기 때문에 현재 time-step의 선택이 미래에 어떤 영향을 미칠지에 대해서는 고려하지 않는다.
그리디 알고리즘의 정당성
- 그리디 알고리즘을 이용해 해법이 구해졌을 때 그 해법이 왜 최적의 해법으로 귀결되는가 검토하는 과정이 필요하다.
예제 1
어떠한 수 N이 1이 될때까지 다음의 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.
- N에서 1을 뺍니다.
- N을 K로 나눕니다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요.
정답코드
n, k = map(int, input().split())
count = 0
while True:
target = (n // k) * k
count += (n - target)
n = target
if n < k:
break
count += 1
n //= k
count += (n - 1)
print(count)이 코드의 장점은 2가지가 있다. (하나는 개인적인 생각)
- 한번 실행될때마다 빼기 연산과 나누기 연산을 한번에 실행시키기 때문에 시간복잡도가 log복잡도로 줄어든다.
- 위와 마찬가지로 빼기 연산을 한번의 연산에 처리했기 때문에 마지막에 count+= (n-1)로 통일성 있게 N=1을 만들어줄 수 있다.
(통일성 있게 모든 하위 연산을 큰 하나의 연산 안에서 처리하도록 logic을 짜는 연산을 하는게 중요한 작업으로 보임)
예제 2
각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나식 모든 숫자를 확인하며 숫자 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 구하시오.
정답코드
data = input()
result = int(data[0])
for i in range(1, len(data)):
num = int(data[i])
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)이 코드에서 내가 간과한 부분은 다음과 같다.
- 그리디 알고리즘의 핵심은 현재 상황에서 가장 좋은 선택지를 고르는 것이다. 따라서, num이 1이하인 수이면 항상 result에 *=를 하는게 최적의 선택이도록 알고리즘을 설계해야 한다.
예제 3
한 마을에 모험가가 N명이 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포도를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. (조건1) 공포도가 X인 모험가는 반드시 X명이상으로 구성한 모험가 그룹에 참여해야하며 (조건2) 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.
N = input()
scare_list = list(map(int, input().split()))
scare_list.sort()
result = 0
count = 0
for i in scare_list:
count += 1
if count >= i:
result += 1
count = 0
print(result)이 문제를 접하면서 간과했던 점은 다음과 같다.
- 그룹수를 최대화하려면 공포도가 낮은 모험가부터 그룹을 지어서 보내야 최대한 많은 그룹을 만들 수 있다. > 공포도가 낮은 순으로 그룹을 만드는게 가장 최적의 선택이다.
- 그룹인원수를 count하면 그 count 이상이 되는 공포도 X가 포함되는 모험가를 그 그룹에 포함시켜서 모험에 보낼 수 있도록 코드를 작성해야 한다.
