Untitled

Fold the Video

Loading...

12강 그리디 알고리즘 개요-0
12강 그리디 알고리즘 개요-1

그리디라는 영단어 자체가 탐욕적인이라는 뜻을 가지고 있음

나중에 배우게 될 크루스카와 알고리즘이나 다엑스트라 저장경로와 같이 잘 알려진 알고리즘을 제외하고 일반적으로 그리디알고리즘이 출제가 되면 해당 문제를 풀기위한 최소한의 아이디어를 적절히 떠올릴수 있어야 문제가 풀리도록 출제되는 경우가 많습니다

다시말해 그리디 알고리즘은 탐욕적으로 현재상황에서 지금 당장 좋은 것만 고르는 방법을 의미 하는 것이며 이러한 방법을 이용했을때 문제에서 요구하는 최적의 해를 구할 수 있는지 검토하는 과정이 필요합니다

12강 그리디 알고리즘 개요-5

다음과 같이 하나의 그래프 중에서도 트리가 이러한 형태로 구성되어 있다고 가정을 해볼게요 이렇게 루트 노드 5부터 출발을 해서 다른 노드로 반복적으로 이동하려고 하는데요 이때 거쳐가는 노드 값의 합을 최대로 만들고 싶습니다 우리는 이 그래프에서

어떤식으로 이동하는게 최적의해를 보장하는지 알수 있음

12강 그리디 알고리즘 개요-8
12강 그리디 알고리즘 개요-9
12강 그리디 알고리즘 개요-10
12강 그리디 알고리즘 개요-11
12강 그리디 알고리즘 개요-12

거처 가는

이때 우리는 굉장히 간단하게 프로그램을 작성하는 방법으로 단순이 매 상황에서 즉 현재 위치에서 가장 큰 값만 선택하는 방법을 반복한다면 어떻게 될까요 예를 들어서 이렇게 시작 노드인 루트 노드에서 출발한다고 했을때

인접한 노드는 7 10 8 임

12강 그리디 알고리즘 개요-17

이후에 이 10에서 이동할수 있는 4와3중에서 더 큰값을 가지는 4로 이동할수있겠죠 다만 이 경우에는 5 10 4 를 더해서 총 19만큼 합을 얻을수 있으며

최적의 해인 21보다는 낮은 값임을 알수 있음

그리디 알고리즘은 이처럼 단순히 매 상황에서 가장 큰 값만 고르는 방식이라고 말할 수 있습니다.

12강 그리디 알고리즘 개요-21
12강 그리디 알고리즘 개요-22
12강 그리디 알고리즘 개요-23

많은데요

12강 그리디 알고리즘 개요-25

문제를 만드는 경우가 많기 때문에 만약에 그리디 문제가 출제가 된다면 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 단순히 그리디 알고리즘을 이용해도 도 이처럼 최적의 해를 얻을 수 있다는 것을 추론할 수 있어야 문제가 풀리도록 출제하는 경우가 많습니다

12강 그리디 알고리즘 개요-27

얻은 해가

12강 그리디 알고리즘 개요-29

그리디 알고리즘 문제로 거스름돈 문제를 함께 풀어 볼게요

12강 그리디 알고리즘 개요-31

거슬러줘야 할 돈은 항상 10의 배수라서 거슬러 주지 못하는 경우는 없음

12강 그리디 알고리즘 개요-33

이 거스름돈 문제는 그리디 알고리즘을 설명 하기 위해 자주 등장 하는 문제로 로써 문제해결 아이디어는 다음과 같음

12강 그리디 알고리즘 개요-35

자 먼저 점원이 무한이 많은 동전을 가지고 있다고 가정합니다 원래대로 라면 이 점원이 500원 100원 50원 10원 짜리 동전을 무수히 많이 가지고 있는 것처럼 그림을 그려야 하지만 일단 이해를 돕고자 이렇게 거슬러 줘야 하는 동전의 갯수 만큼 시각적으로 표현했습니다.

12강 그리디 알고리즘 개요-37
12강 그리디 알고리즘 개요-38
12강 그리디 알고리즘 개요-39
12강 그리디 알고리즘 개요-40

주고 남은 10원 짜리로 거슬러 주면 됩니다

12강 그리디 알고리즘 개요-43

12강 그리디 알고리즘 개요-45
12강 그리디 알고리즘 개요-46
12강 그리디 알고리즘 개요-47

이기 때문입니다 다시 말해서 작은 단위의 동전들을 조합해 다른 해가 나올수 없기 때문입니다

12강 그리디 알고리즘 개요-50

따르면 500원 짜리 1

100원짜리 3개를 건내주어 총 4개라는 답이 나오게 되는데요 사실 최적의 해는 400원 짜리 2개를 거슬러 주는 2개가 답이라고 할수 있겠죠

다시말해 큰단위가 작은 단위의 배수가 아니라면 이와 같은 알고리즘을 이용해서 최적의 해를 보장 할수가 없는 겁니다 지금 500원 짜리가 이 400원 짜리의 배수가 아니죠 그렇기 때문에 이러한 문제가 발생하는 것 입니다

그리디 알고리즘 문제에서는 이처럼 문제풀이를 위한 최소한의 아이디어를 떠올리고 이제 이것이 정당한지 검토할수 있어야합니다

12강 그리디 알고리즘 개요-56
12강 그리디 알고리즘 개요-57

고민을 하다가

12강 그리디 알고리즘 개요-59

큰 단위

했을 때에도

12강 그리디 알고리즘 개요-63
12강 그리디 알고리즘 개요-64
12강 그리디 알고리즘 개요-65

할수 있습니다

12강 그리디 알고리즘 개요-67

파이썬으로 해결할때는 다음과 같이 코드를 작성할수 있습니다 먼저 이렇게 거슬러 줘야할 돈 n이 있다고 했을때 이제 큰단위 화폐부터 작은 단위화폐를 이렇게 리스트에 담아 줍니다 이제 각각의 동전을 확인하면서 이 count즉 결과 값에다가 이 n을 코인으로 나눈 몫을 담습니다 즉 현재 남아있는 돈을 현재의 동전으로 최대한 많이 거슬러 줄수 있도록 하는 거고

12강 그리디 알고리즘 개요-69
12강 그리디 알고리즘 개요-70

이 n을 코인으로 나눈

다시말해 처음의 n이 1260원 일때 500원으로 거슬러주게 되면 두번만큼 거슬러 줄 수 있게 되거 거슬러준 다음에 260원이 남는 겁니다 다시 마찬가지로 260을 이번엔 100원 짜리로 나누어 주면 되는 거겠죠 그래서 100원 짜리로 2개 나눠 줄 수 있고 마찮가지로

260을 나눈 나머지인 60이 남게 되겠죠 이제 이러한 과정을 반복하게 되면 전체 몇개의 동전으로 거슬러 줄 수 있는지를 계산할수 있습니다.

12강 그리디 알고리즘 개요-76

12강 그리디 알고리즘 개요-78

k라고 할때 소스코드의 시간복잡도는 O(k) 입니다 즉 화폐의 종류 만큼만 반복을 수행하면 답을 도출 할수가 있다는 거죠

12강 그리디 알고리즘 개요-80

반복문은 반복이 수행됩니다

12강 그리디 알고리즘 개요-82

그렇기 때문에 이알고리즘의 시간 복잡도는 금액자체와는 무관하며 동전의 총 종류에만 영향을 받는다는점이 특징입니다

12강 그리디 알고리즘 개요-84

있지만 기본적으로 c++과 java 소스 코드 또한 깃허브에서 제공을 하고있음

12강 그리디 알고리즘 개요-86

c++ 코드부터 확인해보겠음

12강 그리디 알고리즘 개요-88

이 cnt 결과 값은 0으로 초기화 기본적으로 c++에서는 이렇게 전역변수로 초기화 된 값은 자동으로 영이란 값을 가지고 있음

12강 그리디 알고리즘 개요-90

이제이어서 반복문을 확인할수 있음

12강 그리디 알고리즘 개요-93
12강 그리디 알고리즘 개요-94

이러한 과정을 화폐단위

12강 그리디 알고리즘 개요-96
12강 그리디 알고리즘 개요-97

자바소스코드 또한 확인할수 있는데요

기본적으로 c++의 코드와 동일한 로직을 가지고 있는걸 확인할수 있습니다

12강 그리디 알고리즘 개요-100
12강 그리디 알고리즘 개요-101

많습니다

12강 그리디 알고리즘 개요-103

생각정리

그리디문제는 여러개를 거칠때 최고값, 가장 적은 개수의 거스름돈 등

이와 같은 문제를 풀때 사용하는데 그때 입력 값들 (ex 화폐종류)중 큰수가

작은수들의 배수일때 사용하는게 가장 좋음

12강 그리디 알고리즘 개요-112

Last Updated:

Summarize & share videos seamlessly

Loading...