[묘공단]파이썬 스터디 13주차

그리디

그리디 알고리즘은 문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택은 번복하지 않습니다.

: 그리디 알고리즘은 지역 최적해를 추구한다.

 

그리디 알고리즘이 최적해를 보장하려면?

특정한 상황

1) 최적 부분 구조 : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치.

2) 그리디 선택 속성 : 선택 과정이 다른 과정에 영향을 주지 않음.

 

• 최소 신장 트리

대표적인 트리 형태의 자료구조.

 

신장트리란?

모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수 보다 적은 그래프.

 

최소 신장 트리란?

MST. 신장 트리 중 간선의 가중치 합이 최소면 최소 신장 트리.

 

• 프림 알고리즘 vs 크루스칼 알고리즘

	프림	크루스칼
알고리즘의 목적	최소 신장 트리	최소 신장 트리
시간 복잡도(정점 V, 간선 E)	O(E*logV) (인접 리스트 활용 시 O(N^2))	O(E*logV)
탐색 방법	임의 정점에서 최소 인접 가중치를 가지는 정점을 찾아 확장하는 방식	최소 가중치를 가지는 간선부터 하나씩 추가하는 방식

 

• 배낭 문제

목표 : 최대한 배낭에 높은 가치의 짐을 넣는다.

 

짐을 쪼갤 수 있는 부분 배낭 문제

: 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 알고리즘.

짐을 쪼갤 수 없는 0/1 배낭 문제

: 지금 선택한 짐이 다음 짐 선택에 영향을 준다. 그래서 최적의 해를 구하려면 동적 계획법으로 접근해야함.

	부분 배낭 문제	0/1 배낭 문제
알고리즘 목적	배낭 속 짐 들의 가치의 합이 최대가 되도록 함	배낭 속 짐 들의 가치의 합이 최대가 되도록 함
문제 특징	짐을 쪼갤 수 있음	짐을 쪼갤 수 없음
시간 복잡도(짐의 개수 N, 가치 W)	O(N*logN)	O(N*W)
그리디 적용 가능 여부	O	X

 

문제풀이

• 예산

def solution(d, budget):
    d.sort() 
    count = 0

    for amount in d: 
        # 남은 예산이 해당 부서의 신청 금액보다 크거나 같으면 지원 가능
        if budget >= amount:
            budget -= amount
            count += 1
        else:
            break

    return count

• 구명 보트

def solution(people, limit):
    people.sort()  
    boat_count = 0
    light = 0
    heavy = len(people) - 1  

    while light <= heavy:
        # 가장 가벼운 사람과 무거운 사람이 함께 탈 수 있으면 함께 태움
        if people[light] + people[heavy] <= limit:
            light += 1
        heavy -= 1
        boat_count += 1  # 보트 개수 증가

    return boat_count