[이것이 취업을 위한 코딩테스트다 with 파이썬] Ch.11 그리디 문제

📌 한 장으로 보는 알고리즘

그리디

 - 현재 상황에서 가장 좋아 보이는 것만 선택하는 알고리즘

 - 정확한 답을 도출하지 못하여도 그럴싸한 답을 도출하는 데에 도움 됨

 - '최적의 해' 찾는 문제가 출제 → 그리디 알고리즘의 정당성 고민하면서 문제 해결 방안 떠올리기

 

그리디 알고리즘 종류

• (9장) 다익스트라 최단 경로 알고리즘
• (10장) 크루스칼 알고리즘

그리디 알고리즘 특징

 → 큰 수로 가장 많이 나누어 보기!

4,6번 다시 풀기

---

📌1) 모험가 길드

✔️문제 유형

그리디

 

✔️문제

 - 모험가 N명

 - 모험가 길드에서 N명의 모험가를 대상으로 '공포도' 측정, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력 떨어짐

 - 모험가 그룹 구성 : 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행 가능

 - 최대 몇 개의 모험가 그룹을 만들 수 있는가?

 

✔️입력 조건

• 첫째 줄에 모험가의 수 N이 주어집니다. (1 <= N <= 100000)
• 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.

✔️출력 조건

여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.

 

✔️입력 예시

5

2 3 1 2 2 

 

✔️출력 예시

2

 

✔️내 문제 풀이

 - 기본 아이디어 : 최대값 정렬 후에 개수에서 최대값 빼기 / 이후 다음 큰 수로 비교

n = int(input())
scare = list(map(int, input().split()))   # n의 개수만큼 입력
scare.sort(reverse = True)

# 리스트 내 숫자 개수 - 가장 큰 수
remain = len(scare) - scare[0]
count = 1

# 남은 수 중 가장 큰 수에서 똑같이 진행
for i in range(1,remain):
 if remain > scare[i]:
   remain -= scare[i]
   count += 1
 elif remain == scare[1]:
   count += 1
 else:
   count = count 

print(count)

 

✔️책 문제 풀이

 - 기본 아이디어

• 공포도를 기준으로 오름차순 정렬
• 공포도 가장 낮은 모험가부터 하나씩 확인, 그룹에 포함될 모험가의 수 계산
  →   현재 그룹에 포함된 모험가의 수 >= 현재 확인하고 있는 공포도 그룹 결성

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for i in data:
  count += 1	# 현재 그룹에 해당 모험가 포함시키기
  if count >= i:	# 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
    result += 1		# 총 그룹의 수 증가시키기
    count = 0	# 현재 그룹에 포함된 모험가의 수 초기화

print(result)	# 총 그룹의 수 출력

 

✔️내 문제풀이와 책 문제풀이 비교

 - 내 문제풀이는 내림차순으로 진행해서 해당 개수를 빼는 형태, 책 문제풀이는 오름차순으로 진행해서 총 그룹과 현재 그룹 모험가 수 채워가는 형태

 - 내 문제풀이가 맞는 답인지 아직 확신 못함

---

📌2) 곱하기 혹은 더하기

✔️문제 유형

그리디

 

✔️문제 

 - 각 자리가 숫자(0-9)로만 이루어진 문자열 S가 주어짐

 - 왼쪽 -> 오른쪽으로 하나씩 모든 숫자를 확인하며, 숫자 사이에 'X'혹은 '+'연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수 구하기

 - 조건) +보다 X를 먼저 계산하는 일반적인 방식과 달리, 모든 연산은 왼쪽 -> 오른쪽 순서대로 진행

 

✔️입력조건

첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다.(1 <= S의 길이 <= 20)

 

✔️출력 조건

첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.

 

✔️입력 예시 

02984

 

✔️출력 예시

576

 

✔️나의 문제 풀이

 - 기본 아이디어 : 문자열 입력 숫자로 바꿔서 리스트에 넣기 / +,* 값 서로 비교해서 큰 값을 결과값으로 출력

s = input()
num = []
result = 0
sum = 0
muti = 0

# 문자열 숫자로 바꿔서 문자로 넣기
for i in s:
  num.append(int(i))

for num1 in num:
  if result == 0:    # 가장 먼저 숫자 들어갈 때 or result 값이 0일 때
    result = num1
  else:
    sum = result + num1
    muti = result * num1
    result= max(sum,muti)
    
print(result)

- 아이디어 : 0,1인 경우 더하기, 이외는 곱하기

s = input()
ans = int(s[0])

for i in range(1,len(s)):
    if int(s[i]) == 0 or int(s[i]) == 1 or ans == 1 or ans == 0:
        ans += int(s[i])
    else:
        ans *= int(s[i])

print(ans)

 

✔️책의 문제 풀이

 - 기본 아이디어 : 숫자가 '0','1'일 경우에 집중 / '0' or '1'일 경우에 더하기, 이외의 숫자일 경우 곱하기

data = input()

# 첫번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
  # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
  num = int(data[i])
  if num <= 1 or result <= 1:
    result += num
  else:
    result *= num

print(result)

 

✔️문제 풀이 비교

 - 나의 문제 풀이는 리스트를 사용하여 다룸, 리스트 넣는 과정에서 for문 한 번 더 사용

 - 책의 문제 풀이는 '두 수 중에 하나라도 0 또는 1일 경우 더하기 수행'이라는 아이디어 사용

---

📌3) 문자열 뒤집기

✔️문제 유형

그리디, 문자

 

✔️문제

1439번: 뒤집기

 

✔️나의 문제풀이

 - 기본 아이디어 : 현재 위치에 있는 값의 개수 세고, 0과 1중 작은 값 리턴

• cnt_1, cnt_0은 반복되는 1 또는 0의 개
• 바뀌는 지점을 알 수 있게 이전 값을 before로 지정

s = input()
cnt_1, cnt_0 = 0,0

before = s[0]
if before == '0':
    cnt_0 += 1
else:
    cnt_1 += 1

for i in range(1,len(s)):
    if before == s[i]:
        before = s[i]
        continue
    else:
        if before == '0' and s[i] == '1':
            cnt_1 += 1
            before = s[i]
        elif before == '1' and s[i] == '0':
            cnt_0 += 1
            before = s[i]

print(min(cnt_1,cnt_0))

 

✔️다른 사람의 문제풀이

 - 기본 아이디어 : 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수 가지는 경우 계산

• 0에서 1 변경, 1에서 0 변경하는 경우 확인하는 방식 이용

data = input()
count0 = 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))

---

📌4) 만들 수 없는 금액

✔️문제 유형

그리디, 정렬 

 

✔️문제

 - N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램

 

✔️입력 조건 

• 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다.( 1<= N <= 1000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1000000 이하의 자연수입니다.

✔️출력 조건

첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

 

✔️입력 예시

5

3 2 1 1 9

 

✔️출력 예시

8

 

✔️책의 문제풀이

- 해결 아이디어

• 화폐 단위를 기준으로 오름차순 정렬, 1부터 특정 금액 만들 수 있는지 확인

n = int(input())
data = list(map(int,input().split()))
data.sort()

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x

# 만들 수 없는 금액 출력
print(target)

• 풀이과정 이해 시 참고

[Greedy] 이코테 “만들 수 없는 금액” Python 풀이

---

📌5) 볼링공 고르기 

✔️문제 유형

그리디

 

✔️문제

 - A,B 두 사람이 볼링을 치고 있으며 서로 무게가 다른 볼링공 고름.

 - N개의 볼링공, 공의 번호는 1번부터 순서대로 부여

 - 볼링공의 무게는 1~M까지의 자연수 형태. 같은 무게의 공이 여러 개 있어도 서로 다른 공으로 간주

 

✔️입력 조건 

• 첫째 줄에는 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.
  (1 <= N <= 1000, 1 <= M <= 10)
• 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.
  (1 <= K <= M)

✔️출력 조건

첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력합니다.

 

✔️입력 예시

5 3

1 3 2 3 2

 

✔️출력 예시

8

 

✔️나의 문제풀이

- 2개의 볼링공 조합(total)에서 원래 무게에서 중복된 무게 뺀 값(ball_duplicate)

n,m = map(int,input().split())
ball_weight = list(map(int,input().split()))

total = sum([i for i in range(1,n)])
ball_duplicate = n - len(set(ball_weight))

print(total - ball_duplicate)

 

✔️다른 사람의 문제풀이

  - 무게마다 볼링공이 몇 개 있는지 계산

  - A를 기준으로 '낮은 무게 ~ 높은 무게'로 확인

n,m = map(int,input().split())
data = list(map(int,input().split()))

# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11

for x in data:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0

# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m+1):
    n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i] * n # B가 선택하는 경우의 수와 곱하기

print(result)

---

📌6) 무지의 먹방 라이브

✔️문제 유형

그리디

 

✔️문제

프로그래머스

 

✔️나의 문제풀이

 - 28.1점

def solution(food_times, k):
    i = 0
    
    if sum(food_times) <= k:
        return -1
    
    while k > 0:
        if food_times[i % len(food_times)] > 0:
            food_times[i % len(food_times)] -= 1
            i += 1
            k -= 1
        elif food_times[i % len(food_times)] == 0:
            i += 1
        
    return (i % len(food_times)) + 1

 

✔️책의 문제풀이

 - 핵심 아이디어 : 시간 기준으로 정렬 → 시간이 적게 걸리는 음식부터 제거(우선순위 큐 이용)

• 시간이 가장 적게 걸리는 음식 기준으로 다 빼기

import heapq

def solution(food_times, k):
    answer = 0
    
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1
    
    # 시간이 작은 음식부터 빼야하므로 우선순위 큐 사용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q,(food_times[i], i+1))
        
    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수
    
    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정
        
    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key = lambda x:x[1]) # 음식의 번호 기준으로 정렬

    return result[(k - sum_value) % length][1]

 

✔️리뷰

  - 그리디는 DP랑 다름 → 효과적으로 풀 수 있는 방법(ex. 정렬 후 계산) 고민하기