Greedy 알고리즘

문제 1. 모험가 길드

한 마을에 모함가가 N명 있다.

모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했다.

공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.

모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.

동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다.

N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄: 모험가의 수 N
• 둘째 줄: 모험가의 공포도의 값

출력

여행을 떠날 수 있는 그룹 수의 최댓값

해결 방식

1. 공포도를 담고 있는 배열을 오름차순 정렬
2. 현재 모험가 수 count
3. 현재 count된 모험가의 수가 모험가의 공포도와 같거나 클 경우 그룹 구성
   • group 1 추가
   • count는 0으로 초기화

코드

n = int(input())
fear = list(map(int, input().split()))
group = 0
count = 0
fear.sort()

for i in fear:
    count += 1
    if count >= i:
        group += 1
        count = 0

print(group)

문제 2.

각 자리가 숫자로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 X 확은 +연산자를 넣어 결과적으로 만들어 질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

+보다 X를 먼저 계산하는 일반적인 방식과 달리 모든 연산은 왼쪽에서부터 순서대로 이루어집니다.

입력

• 첫째 줄: 여러개의 숫자로 구서오딘 하나의 문자열 S

출력

만들어질 수 있는 가장 큰 수

해결 방식

0 또는 1만 더해주고 나머지는 곱해준다.

코드

s = input()
result = 0

for i in range(len(s)):
    num = int(s[i])
    if num <= 0 or result == 0:
        result += num
    else:
        result *= num

print(result)

문제 3. 문자열 뒤집기

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다.

다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다.

다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다.

뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번만에 모두 같은 숫자로 바꿀 수 있다.

문자열 S가 주어졌을 때 다솜이가 해야 하는 행동의 최소 횟수를 출력하시오.

입력

• 첫째 줄: 0과 1로 이루어진 문자열 S

출력

다솜이가 해야하는 행동의 최소 횟수

해결 방식

0과 1이 변환될 때마다 뒤집어야 하는 횟수가 증가한다.

ex) 00/11/00: 2번 변환 = 1번 뒤집기 0/11/0/1: 3번 변환 = 2번 뒤집기

• 식: (변환되는 횟수 + 1) / 2

코드

s = input()
result = 0

for i in range(len(s)-1):
    if s[i] != s[i+1]:
        result += 1

print((result+1)//2)

문제 4. 만들 수 없는 금액

동네 편의점 주인인 동빈이는 N개의 동전을 가지고 있다.

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

입력

• 첫째 줄: 동전의 개수 N
• 둘째 줄 ~ 각 동전의 화폐 단위

출력

만들 수 없는 양의 정수 금액 중 최솟값

해결 방식

1. 동전을 오름차순 정렬

2. 1부터 만들 수 있는지 확인한다.

3. 작은 금액의 동전부터 확인한다.

   • 현재 확인하는 동전을 통해 target금액을 만들 수 있는지 확인한다.
   • 만들 수 있는 경우 target을 증가시킨다

예시

화폐 배열: [3, 2, 1, 1, 9]

1. 오름차순 정렬: [1, 1, 2, 3, 9], target = 1

2. 첫 번째 coin(1) 확인
   • 1을 만들 수 있음 → target 증가
   • target = 2
3. 두 번째 동전(2) 확인, target = 2
   • 이전 단계에 1원을 만들 수 있었기 때문에 여기에 현재 coin값을 더해 2까지 만들 수 있다 → target 증가
   • target = 3
4. 세 번째 동전(2) 확인
   • 이전 단계에 1, 2를 만들 수 있었다.
   • 따라서 3, 4 조합 가능 → target 증가
   • target = 5
5. 네 번째 동전(3) 확인
   • 이전 단계에서 1~4까지 만들수 있었다
   • 이전 단계에 더해 4~7까지 조합할 수 있다 → target 증가
   • target = 8
6. 다섯 번째 동전(9) 확인
   • 이전 단계에서 1~7까지 조합할 수 있었다.
   • coin의 가치가 target보다 높아 8을 만들 수 없다.
   • target = 8에서 종료

∴ target = 8

코드

n = int(input())
coins = list(map(int, input().split()))

coins.sort()

target = 1
for coin in coins:
    print(target)
    if coin > target:
        break
    else: 
        target += coin

print(target)   

문제 5. 볼링공 고르기

A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려 한다.

볼링공은 총 N개가 있고 각 볼링공마다 무게가 적혀있으며 번호는 1번부터 순서대로 부여된다.

또한 같은 무게의 공이 여러개 있을 수 있지만 서로 다른 공으로 간주한다.

볼링공의 무게는 1부터 M까지 자연수로 존재한다.

N개의 공 무게가 각각 주어질 때 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄: 볼링공의 개수 N, 공의 최대 무게 M
• 둘째 줄: 각 볼링공의 무게

출력

두 사람이 볼링공을 고르는 경우의 수

해결 방식

1. 각 무게의 볼링공이 몇 개인지 알아낸다.
   • weight 배열에 해당 인덱스 무게의 공이 몇 개 있는지 저장
   • 예를 들어 무게가 2인공 2개가 있다면 배열의 3번째 데이터에 2 저장
2. A가 볼링공을 선택하면 해당 무게의 볼링공을 제외한 다른 무게의 볼링공을 선택하도록 한다.

예시

[1, 3, 2, 3, 2]

• weight = [0, 1, 2, 2]

1. A가 무게가 1인 공 선택
   • 무게가 1인 공은 1개
   • B는 나머지 4개 공을 모두 선택할 수 있음
   • 4가지 경우 존재
2. A가 무게 2인 공 선택
   • 무게가 1인 공은 이미 고려했으므로 제외
   • A가 무게가 2인 공을 선택하는 경우 2가지
   • B가 다른 무게의 공을 선택하는 경우 2가지
   • 2 * 2 = 4가지 경우
3. A가 무게 3인 공 선택
   • 이미 무게가 1, 2인 공들과 조합이 끝났다..
   • 종료

∴ 경우의 수 = 8

코드

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

weight = [0 for _ in range(m+1)]

for i in k:
    weight[i] += 1

result = 0
for i in range(1, m):
    n -= weight[i]
    result += weight[i]*n

print(result)

문제6. 무지의 먹방 라이브

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어졌고 고민 끝에 카카오 TV 라이브 방송을 하기로 마음먹었습니다.

그냥 먹방을 하면 차별성이 없기 때문에 무지는 다음과 같은 방식을 생각했다.

회전판에 먹여야할 N개의 음식이 있고 음식에는 1부터 순서대로 번호가 붙어있다.

각 음식을 섭취하는데 일정한 시간이 소요되며 다음과 같은 방식으로 음식을 섭취한다.

1. 무지는 1번 음식부터 먹으며 회전판 번호는 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
2. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
3. 무지는 음식 하느를 1초동한 섭취한 후 남은 음식은 그대로 두고 다음 음식을 먹는다.
4. 회전판이 다음 음식을 무지 앞으로 가져오는데는 시간이 소요되지 않는다.

무지가 먹방을 시작한 지 K초 후 네트워크 장애로 방송이 중단되었다!

무지는 네트워크 정상화 후 다시 방송을 이어갈 때 몇번 음식부터 섭취해야 하는지 알고자 한다.

각 음식을 모두 먹는데 필요한 시간이 담겨져 있는 배열 food_times, 네트워크 장애가 발생한 시간 K초가 주어질 때 몇 번 음식부터 다시 섭최하면 되는지 작성하시오.

제한사항

• food_times는 각 음식을 먹는데 필요한 시간을 저장한 배열
• K: 방송의 중단된 시간
• 만약 더 섭취해야 할 음식이 없다면 1 반환

출력

해결 방식

코드

def solution(food_times, k):
    answer = 0
    foods = []
    prev = 0
    for i in range(len(food_times)):
        foods.append((food_times[i], i)) # (남은 양, index)
    foods.sort(key=lambda x:x[0])
    for food, i in foods:
        if prev == food:
            foods.remove((food, i))
            continue
        if k < food * len(foods):
            break
        k -= food * len(foods)
        foods.remove((food, i))
        prev = food
    if(len(foods) == 0):
        return -1
    
    idx = k % len(foods) 
    if idx == 0:
        idx = len(foods) - 1
        
    foods.sort(key=lambda x:x[1])
    print(foods, foods[idx][1])
    answer = foods[idx][1] + 1
    return answer