99클럽 코테 스터디 7일차 TIL +탐욕법 Greedy

오늘의 공부 키워드

• 탐욕법(greedy)에 대한 개념
• 프로그래머스 체육복 문제 풀이

탐욕법(greedy)

탐욕법(Greedy Algorithm)은 최적해를 구하는 알고리즘 설계 기법 중 하나로, 각 단계에서 현재 상황에서 가장 좋다고 생각되는 선택을 하는 방법입니다. 이 방법은 전체 문제를 해결하기 위한 전역 최적해(global optimal solution)가 아닌, 각 단계에서의 지역 최적해(local optimal solution)를 선택함으로써 문제를 해결하려고 합니다.

 

탐욕법의 기본 아이디어

탐욕법은 다음과 같은 방식으로 작동합니다:

1. 현재 상태에서 최선의 선택을 한다: 현재 상황에서 가장 좋다고 생각되는 선택을 합니다.
2. 선택을 확정하고, 이를 기반으로 다음 상태로 이동한다: 현재 선택이 전체 문제에 어떻게 영향을 미칠지에 대해 신경 쓰지 않고, 다음 단계로 이동합니다.
3. 이 과정을 반복한다: 최종적으로 문제를 해결할 때까지 반복합니다.

탐욕법의 특징

• 단순함: 각 단계에서 최선의 선택을 하므로 구현이 간단합니다.
• 빠름: 각 단계에서의 선택이 한 번에 이루어지므로 일반적으로 시간 복잡도가 낮습니다.
• 최적해 보장 여부: 탐욕법이 항상 최적해를 보장하지는 않습니다. 문제의 특성에 따라 전역 최적해를 보장할 수도 있고, 그렇지 않을 수도 있습니다. 탐욕법이 최적해를 보장하려면 특정 조건(예: 탐욕적 선택 속성, 최적 부분 구조)이 만족되어야 합니다.

탐욕법의 적용 예시

탐욕법은 여러 문제에서 효과적으로 사용됩니다. 대표적인 예시로는 다음이 있습니다:

1. 거스름돈 문제:
   • 거스름돈을 줄 때 동전의 수를 최소화하기 위해 가장 큰 단위의 동전부터 거슬러 주는 방법입니다.
2. 최소 신장 트리(MST, Minimum Spanning Tree):
   • 그래프에서 모든 정점을 연결하는 최소 비용의 트리를 찾기 위해 사용하는 Kruskal 알고리즘이나 Prim 알고리즘이 탐욕법을 사용합니다.
3. 활동 선택 문제(Activity Selection Problem):
   • 주어진 활동들의 시작 시간과 종료 시간 중에서 가장 많은 활동을 선택하는 문제에서 각 단계마다 가장 빨리 끝나는 활동을 선택하는 방법입니다.

 

체육복

문제 해석

1. 학생들의 번호는 체격 순으로 매겨져 있습니다.
2. 도난당한 학생(lost)은 체육복이 없어서 수업을 들을 수 없습니다.
3. 여벌의 체육복을 가진 학생(reserve)은 도난당한 학생들에게 체육복을 빌려줄 수 있습니다.
4. 여벌의 체육복을 가진 학생도 도난당한 경우, 본인의 체육복이 하나 남기 때문에 다른 학생에게 빌려줄 수 없습니다.
5. 한 학생은 자신의 바로 앞번호나 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

접근 방법

1. 여벌의 체육복을 가진 학생이 도난당한 경우 처리:
   • 여벌의 체육복을 가진 학생(reserve) 목록과 도난당한 학생(lost) 목록에서 공통으로 포함된 학생을 찾아 처리합니다. 이들은 체육복이 하나 남기 때문에 빌려줄 수 없습니다.
2. 도난당한 학생들에게 체육복 빌려주기:
   • 도난당한 학생을 순회하면서 앞번호 학생(reserve - 1)이나 뒷번호 학생(reserve + 1)에게 빌릴 수 있는지 확인하고 빌려줍니다.
3. 최종적으로 체육수업을 들을 수 있는 학생 수 계산:
   • 도난당한 학생(lost) 중 체육복을 빌린 학생을 제외하고 나머지 학생 수를 전체 학생 수(n)에서 빼면 체육수업을 들을 수 있는 학생 수가 됩니다.

 

코드 설명

 

def solution(n, lost, reserve):
    # 여벌 체육복을 가진 학생이 도난당한 경우 처리
    reserve_set = set(reserve) - set(lost)
    lost_set = set(lost) - set(reserve)

    # 체육복을 빌려주기
    for r in sorted(reserve_set):
        if r - 1 in lost_set:
            lost_set.remove(r - 1)
        elif r + 1 in lost_set:
            lost_set.remove(r + 1)

    # 체육수업을 들을 수 있는 학생 수
    return n - len(lost_set)

# 테스트 예제
print(solution(5, [2, 4], [1, 3, 5]))  # 5
print(solution(5, [2, 4], [3]))        # 4
print(solution(3, [3], [1]))           # 2

 

설명

1. reserve_set = set(reserve) - set(lost)와 lost_set = set(lost) - set(reserve):
   • 여벌 체육복을 가진 학생 중에서 도난당하지 않은 학생과 도난당했지만 여벌 체육복이 없는 학생을 구분합니다.
2. for r in sorted(reserve_set):
   • 여벌 체육복을 가진 학생들을 순회하면서 앞번호 학생이나 뒷번호 학생에게 체육복을 빌려줍니다.
3. lost_set.remove(r - 1) 또는 lost_set.remove(r + 1):
   • 체육복을 빌려준 학생을 도난당한 학생 목록에서 제거합니다.
4. n - len(lost_set):
   • 전체 학생 수에서 체육복이 없는 학생 수를 뺀 값을 반환하여 체육수업을 들을 수 있는 학생 수를 계산합니다.

 

오늘의 회고

 

• 탐욕법(Greedy)에 대해 알수 있어서 좋았다.
• 좀더 끈질기게 고민하고 문제를 풀어야 하는데 쉽게 포기하는게 아닌가 하고 반성하게 된다.
• 코드 리뷰라고 하더라도 문제를 이해하는게 정말 중요함을 느낀다.
• 코딩테스트 문제만 풀지말고 기록도 남겨야 함을 느낀다.
• 알고리즘에 대한 공부를 더 해야할것을 느낀다.