알고리즘 7강 :: 욕심쟁이, 동전거스름돈, 배낭문제, 신장트리

알고리즘 7강을 보며 배운내용

 

 

동적 프로그래밍을 6강으로 정리하고

Greedy(욕심쟁이) 알고리즘을 7강, 8강에 걸쳐 배운다

 

7강에서는 욕심쟁이 알고리즘에 대한

개념과 원리, 특징을 알아보고 예를 살펴본다

 

 

정리

그리디(욕심쟁이) 방법은 동적 프로그래밍 방법보다

조금 더 간단하게 다가왔다

 

최소를 구할 땐 최소의 값을 택하고

최대를 구할 땐 최대의 값을 택하는

직관적인 방법으로 보인다

 

이것 역시 유명한 알고리즘을 풀어보고

변형으로 넘어가면 꽤 이해가 되지 않을까 싶다

 

 

욕심쟁이 방법

전후 선택과 상관없이 해당 단계에서

가장 최선이라고 여겨지는 해를 선택해서 전체적인 최적해를 구한다

탐욕적 방법, 그리디(Greedy) 라고도 불린다

 

 

동적 프로그래밍 vs 욕심쟁이

공통

최적화 문제에 주로 사용

최적성의 원리가 만족해야 사용한다

 

다른점

• 동적 프로그램
  소문제의 여러 최적해로 다음 문제에 대해 최적해 결정
  => 항상 전체적인 최적해 구한다
  
  
• 욕심쟁이
  각 단계에서 하나의 최적해만 고려
  전체적인 최적해 구하지 못할 수 있다
  => 욕심쟁이 방법으로 해를 구할 수 없는 문제도 많다

BUT 만약 구하면 무지 쉽게 구해져서 사용한다

 

 

동전 거스름돈 문제

동전의 거스름돈을 최소로 만들어서 돌려주는 문제

액면가 높은 동전부터 욕심부려서 최대한 사용

 

⌛ 시간 복잡도

O(n)

동전배열 정렬을 해야된다면

O(nlogn)

 

🤖 코드

// 동전 거스름돈 JavaScript
function coinChange(전체금액, 동전배열, 거스름돈배열) {
  for(let i = 0; i < n; i++) {
    거스름돈배열[i] = Math.floor(전체금액/동전배열[i])
    전체금액 = 전체금액 - 동전배열[i] * 거스름돈배열[i]
  }
}

 

What if?
동전 액면가가 랜덤으로 주어지면?
예를들어 120원짜리 동전이 주어지면
욕심쟁이 방법 불가 X
동적 프로그램 가능 O

 

 

배낭 문제

이 문제는 준비물이 있다

• 최대 용량 M인 배낭
• n개의 물체
• 각 물체는 무게 w와 배낭에 넣었을 때 이익 p가 있다

 

 

이럴 때

배낭에 들어있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법

최대이익 구하는 문제

 

이 방법은 밑의 가정이 없으면 욕심쟁이 사용 불가능

가정 => 물체를 쪼개서 넣을 수 있다!

 

방법

물체의 무게가 적으면서 이익이 큰 물체부터 '욕심내서' 넣기!

단위 무게당 이익 가장 큰 물체부터 넣는다

 

계산을 해보면

초콜렛 1개, 바나나 1개, 핫도그 0.5개가 들어간다

 

⌛ 시간 복잡도

O(n)

정렬 고려하면

O(nlogn)

 

🤖 코드

// 배낭무게 JavaScript
function knapsack(이익배열, 물체배열, 물체갯수, 배낭용량, 물체비율 ){
  for(let i = 0; i < n; i++){
    물체비율[i] = 0;
  }
  
  let 배낭용량copy = 배낭용량
  for(let i = 0; i < 물체갯수; i++){
    if(물체배열[i] <= 배낭용량copy){
      물체비율[i] = 1
      배낭용량copy -= 물체배열[i]
    } else {
      물체비율[i] = 배낭용량copy / 물체배열[i]
      break;
    }
  }
}

역시 가짜코드 옮긴거라 틀린 결과가 나올 수 있습니다. 틀리면 알려주세요

 

What if?
물체 쪼갤 수 없는 형태의 배낭 문제는
욕심쟁이 방법 불가 X
아주 어려운 문제(근사 알고리즘으로 풀 수도)

 

 

신장 트리(Spanning Tree)

가중 무방향 그래프를

모든 정점을 포함하는 연결된 트리를 만든 것

방향도 없고, 사이클도 없다

 

최소 (비용) 신장 트리(Minimum Spanning Tree)

위의 여러 신장 트리 중에서

간선의 가중치 함이 가장 작은 트리를 구하는 것!

 

2가지 알고리즘

• 크루스칼(Kruskal)
• 프림(Prim)

 

기본적으로 둘 다 이런 느낌의 알고리즘

 

최선의 간선이란

사이클 만들지 않고, 최소의 가중치를 갖는 간선

 

 

크루스칼 알고리즘

꽤 간단한 방법이네~

그려보면 더 와닿을 듯 싶다

 

방법

1. 간선 하나도 없는 상태로 시작
2. 가중치 가장 작은 간선부터
3. 만약 사이클 안만들면 추가
4. 사이클 만들면 버림

 

프림 알고리즘

 

방법

1. 임의의 한 정점에서 시작
2. 연결된 정점에서 가중치가 가장 작은 것을 연결
3. 선택된 정점을 하나씩 늘려가면서
4. 선택되지 않은 정점이 빌 때까지 반복

 

 

greed by Henley Design #unsplash