[이것이코딩테스트다] CH3. 그리디 알고리즘 python (+연습문제, 예시답안)

그리디 알고리즘

• 탐욕 알고리즘이라고도 부름
• "현재 상황에서 지금 당장 좋은 것만 고른다" -> 최적의 해를 보장할 수 없을 때가 많음

ex. 거스름돈 문제 [500, 100, 50, 10] => 가장 큰 화폐단위부터

  Q. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적해를 보장하는 이유? (정당성 분석)

  A. 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기에 작은 단위의 동전을 종합해 다른해가 나올 수 없기 때문

 

• 그리디 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함

 

---

문제1. 곱하기 혹은 더하기

문제: 각 자리 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하라. 단 +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다.

 

예제 결과🙆🏻‍♀️

S='02984', ((((0+2) x 9) x 8) x 4) = 576
* 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되어 2개의 그룹을 만들 수 있다.
* 몇 명의 모험가는 마을에 그대로 남아 있어도 되기에 모든 모험가를 그룹에 넣을 필요는 없다.

 

# 1차 시도
S = '02984'
s_list = [int(s) for s in S]

result = 0
if s_list[0] == 0:
    result = s_list[1]
    n = 2
else:
    result = s_list[0]
    n = 1
for i in range(n, len(s_list)):
    if s_list[i] == 0:
        result += s_list[i]
    else:
        result *= s_list[i]
print(result)

 

1이 있을 경우에도 곱하기보다는 더하기가 효율적이라는 사실 간과

 

# 2차 시도
S = '02984'
s_list = [int(s) for s in S]

result = 0
if s_list[0] == 0 or s_list[0] == 1:
    result = s_list[0] + s_list[1]
    n = 2
else:
    result = s_list[0]
    n = 1
for i in range(n, len(s_list)):
    if s_list[i] == 0 or s_list[0] == 1:
        result += s_list[i]
    else:
        result *= s_list[i]
print(result)

---

예시 답안

S = '02984'
result = int(S[0])
for i in range(1, len(S)):
    num = int(S[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

 

< 나와 다른 부분 > ⭐

1) for 문을 통해 입력받은 문자열을 int형의 리스트로 변환하는 과정을 거치지 않고, + 혹은 x를 하는 for문 안에서 int로 변환

2) 처음 글자를 판단하는 부분을 더욱 간결하게 짰음

 

---

문제2. 모험가 길드

문제: 한 마을에 모험가가 N명이 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다. 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성해라.

 

예제 결과🙆🏻‍♀️
N=5, 공포도: [2 3 1 2 2]
* 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되어 2개의 그룹을 만들 수 있다.
* 몇 명의 모험가는 마을에 그대로 남아 있어도 되기에 모든 모험가를 그룹에 넣을 필요는 없다.

 

 

💡처음 Idea: 큰 수부터 정렬해서(내림차순) 첫 index의 수만큼 '작은 공포도'부터 그룹에 추가

# 1차 시도
scary = [2,3,1,2,2]
scary.sort(reverse=True)

cnt = 0
while scary: # scary가 빌 때까지
    num = scary[0]
    if num > len(scary):
        break
    del scary[0]
    for _ in range(num-1):
        scary.pop()
    print(scary)
    cnt += 1
cnt

 

최대 수의 그룹을 구성해야함.

-> 오름차순으로 정렬하고 낮은 모험가부터 그룹을 만드는 것이 최대 수 가능

 

# 2차 시도
scary = [2,3,1,2,2]

cnt = 0
while scary: # scary가 빌 때까지
    num = scary[0]
    if (num >= len(scary)) or (num >= len(scary) and scary[0] != scary[1]):
        break
    for _ in range(num):
        del scary[0]
    print(scary)
    cnt += 1
cnt

반례 발견!!!🙊

---

 

예시 답안

scary = [5,4,3,3,2,2,2,2,2,2,1,1,1,1,1]
scary.sort()

result = 0
cnt = 0
for i in scary:
    cnt += 1
    if cnt >= i:
        result += 1
        print(cnt)
        cnt = 0

print(result)

출력: 8개

 

참고 자료

https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2