그리디 알고리즘이란?
매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.
예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자. 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.
1.거스름돈 계산기 (73,320원 시나리오)
만약, 내가 이마트에서 73,320원치의 장을 보고 100,000원을 지불했다고 가정해보자.
거스름돈을 받을 수 있는 최적의 경우의 수는 10,000원x2장, 1,000원x6장, 100원x6개, 10원x8개 이다. 이를 코드로 구현하면 어떻게 표현 해 줄 수 있을까?
var payCost = 100000 // 지불금액 설정
var productPrice = 73320 // 제품가격 설정
let change = payCost - productPrice // 잔돈 계산 상수 설정
let rest10000 = change / 10000 // change값에 10,000원을 나눈 몫을 구한다.
let rest5000 = (change % 10000) / 5000 // change값에 10,000원을 나눈 나머지를 5000원으로 나눈 몫을 구한다.
let rest1000 = ((change % 10000) % 5000) / 1000 // change값에 10000원을 나눈 나머지에 5000을 나눈 나머지 그곳에 1000을 나눈 몫을 구한다.
let rest500 = (((change % 10000) % 5000) % 1000) / 500 // 위내용과 동일한 메커니즘
let rest100 = ((((change % 10000) % 5000) % 1000) % 500) / 100
let rest50 = (((((change % 10000) % 5000) % 1000) % 500) % 100) / 50
let rest10 = ((((((change % 10000) % 5000) % 1000) % 500) % 100) % 50) / 10
print("""
잔돈봇 :
10,000원 x \(rest10000)장
5,000원 x \(rest5000)장
1,000원 x \(rest1000)장
500원 x \(rest500)개
100원 x \(rest100)개
50원 x \(rest50)개
10원 x \(rest10)개
를 거슬러 줄게요!
""")
/*
결과:
잔돈봇 :
10,000원 x 2장
5,000원 x 1장
1,000원 x 1장
500원 x 1개
100원 x 1개
50원 x 1개
10원 x 3개
를 거슬러 줄게요!
라는 메시지가 출력된다!
*/2.넷플릭스 러닝타임 계산기 (1일10시간24분 케이스)
요즘 재밌게 보고있는 우리들의블루스의 러닝타임은 얼마나 될까?
(1화 55분, 2화 71분, 3화 75분, 4화 60분, 5화 61분, 6화 65분, 7화 68분, 8화 66분, 9화 65분, 10화 59분, 11화 65분, 12화 59분, 13화 59분, 14화 73분, 15화 71분, 16화 60분)으로 총 '1032분'이다. 이를 시간으로 표현하면 17.2시간으로 표현할 수 있다.
(아니, 추가로 갑자기 드라마가 40화분으로 드라마가 늘어나서 2064분이 되었다고 가정해보자, 이는 34.4시간으로 표현 할 수 있고, '1일 10시간 24분'으로 표현 할 수 있다. 이렇게 표현해보자.)
var netflixWooridleRuntime = 2064 // 런타임 변수 설정 (단위:분)
let days = netflixWooridleRuntime / 1440 // 런타임 변수(분)을 1440(1일 분)으로 나눈 몫을 계산한다. (일수추출)
let hours = (netflixWooridleRuntime % 1440) / 60 // 런타임 변수(분)을 1440(1일 분)으로 나눈 나머지를 60으로 나눈 몫을 계산한다. (시간추출)
let minutes = (netflixWooridleRuntime % 1440) % 60 // 런타임 변수(분)을 1440(1일 분)으로 나눈 나머지에다가 60으로 나눈 나머지를 계산한다. (분추출)
print("""
러닝타임봇 :
우리들의블루스의 총 러닝타임은
\(days)일 \(hours)시간 \(minutes)분 입니다!
""")
/*
결과 :
러닝타임봇 :
우리들의블루스의 총 러닝타임은
1일 10시간 24분 입니다!
라는 결과가 나타난다.
*/
굿 또들어서 정리해보자
