[백준/python] Greedy 유형 모음집 및 접근 컨셉

[알고리즘/python] DP 유형 - 배낭(Knapsack) 문제

 

앞서 Fraction Knapsack 문제는 그리디 알고리즘으로 풀 수 있음을 언급했습니다. 어떤 조건 하에 그리디 탐색을 적용할 수 있을지 알아보겠습니다.

 

---

정의 및 조건

 

- 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

- 지역적으로 최적이면서 전역적으로 최적인 문제들에 적용 가능

- 혹여 사용하지 못하더라도 근사 알고리즘으로 사용 가능, 최적해에 도달하는 속도가 빠르기 때문

 

[적용 가능한 문제 조건]

1. 탐욕스러운 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않음

2. 최적 부분 구조 조건 : 부분 문제에 대한 최적 문제 해결방법을 토대로 최종 최적해를 구할 수 있다. => 매트로이드 구조라고 칭함.

 

- 최적해가 보장되는 예

1. 최소 신장 트리 (최소 길이 간선..?)

2. 회의실 배정 문제 (종료시간이 이른 순일 경우)

3. 동전 바꾸기 (배수가 아닐경우) ex. 500, 400 etc

4. Fraction Knapsack 유형

 

최적해가 보장되지 않는 예

1. 이진 트리의 최적합 경로 찾기 (Q. 만약 완전이진트리라면??)

2. 동전 바꾸기 (큰 액수의 동전이 한단계 작은 액수의 동전 배수일 경우) ex. 500, 100, 50

3. 1-0 Knapsack 유형

 

[매트로이드] (TODO 개념 추가 필요)

매트로이드 구조 -> Greedy

Greedy -x-> 매트로이드 구조

 

[응용]

- 허프만 코드 : 최적 프리픽스-프리 코드를 만드는 그리디 알고리즘, 가변 길이 코드 단어를 토대로 데이터 압축

 

[참고자료 1]

[참고자료 2] Introduction to Algorithms 15장

 

 

 

구현으로 알아보기

 

- 어떤 것을 욕심낼지 찾아야함. 정렬 등의 전처리가 필요할 수도

- 반례가 존재한다면, 그리디 알고리즘을 사용치 못함

 

fraction knapsack 유형

무게당 가치가 높은 순으로 선택

 

코드트리 #회의실 준비 백준 #1931 회의실

- 회의 끝 시간으로 오름차순 정렬 후, 곂치지 않는 순으로 선택 - 주의) 필요시 시작시간도 sub 오름차순 정렬 필요함

 

#2457 공주님의 정원

- 회의실 준비와 비슷하지만, 기간이 곂칠 수 있음이 차이점 - 시간초과 원인 분석 필요: 우선순위큐를 썼는데 정답풀이들은 순회 및 스택으로 해결함

 

백준 #1781 컵라면

- #1931 회의실 문제와 유사하지만, 작업당 연산이 1인 점을 유의하자 - 우선순위 큐 유형 믹스

 

백준 #11047 동전0

- 가장 가치가 높은 동전을 우선 선택 - 가정) 큰 액수의 동전이 한단계 작은 액수의 동전 배수일 경우

 

백준 #1946 신입사원

- 성적 순위로 오름차순 후 - 하나라도 성적이 좋은 사람을 선택

 

#2217 로프

- Greedy는 전처리가 중요함 - ropes가 내림차순일때, (idx +1) 이 값은 자기보다 크거나 같은 요소의 개수

 

#11501 주식

- 기준값 업데이트와 순회를 함께함으로써 시간 복잡도를 줄일 수 있다. - 사담) 이 문제를 못 풀면 내가 주식 정보를 미리 예견해도 돈 못걸겠다는 생각이 들었다 ㅋㅋ

 

#1744 수 묶기

- 조건별 Greey 가능한지 연습하기 좋음 - 양수끼리 곱, 1은 더하는게 좋음, 음수끼리 양수화 가능, 조커 0으로 음수 제거 가능 (디테일한 분기 필요)