그리디 알고리즘, 백준 11047 java, node.js

알고리즘 전공 과목에서 과제로 백준 11047번을 원하는 두 가지의 언어를 활용해서 풀어보라고 미션을 줘서 공부한 것을 기록해두려고 한다.
Java와 node.js 활용해 문제 풀이

백준 11047번 문제는 그리디 알고리즘을 활용하는 문제이다.

그리디 알고리즘 === Greedy Algorithm 이란?
greedy, 탐욕 알고리즘
중요한 키워드는 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다는 것이다.
그 당시는 최적일지 몰라도 최종적으로 답이 최적이 아닐 수 있다.
그리디 해법은 정당성 분석이 중요하다.

 

그림으로 보면서 이해를 해보자

여행을 서울 -> 부산으로 떠나려 한다.
위의 그림에서 경로와 각 경로에 따른 소요 시간을 확인하고,
나의 입장에서 최대한 빠르게 서울에서 부산까지 가고 싶을 때 어떤 선택을 하게 될까?

서울 -> 대전
경로가 3가지 있는데 이 중 가장 짧은 소요시간인 80분을 선택할 것이다.

대전 -> 부산
경로가 3가지 있는데 이 중 가장 짧은 소요시간인 150분을 선택할 것이다.

총 230분이 걸린다.
이렇게 각 단계별로 최선의 선택지를 선택하는 것이 바로 그리디 알고리즘이다.
굉장히 쉽다.

주의할 점
이 알고리즘은 좋아 보이지만 여러분이 명심해야 할 부분은 그리디 알고리즘은 항사아 최적의 답, 해를 도출해내는 것이 아니라는 점이다.
만약, 위 지도에서 새로 도로가 건설되어서 다음과 같은 루트가 새로 생겼다고 가정해보자, 그럼 이야기가 달라진다.

그리디 알고리즘대로 풀어보자.
그렇다면 각 순간 최선의 선택을 해야하기 때문에 서울 -> 대전 : 80분 선택
대전 -> 부산 : 150분 선택
위처럼 하게 될 것이다.

하지만, 서울 -> 원주 -> 부산으로 가는 길이 220분으로 그리디 알고리즘대로 푼 230분보다 빨리 도착이 가능하다.

이렇게 그리디 알고리즘은 '최적해에 근사하는 방법'일 뿐 항상 최적해를 만족하는 것은 아니다.

 

1. 이전의 탐욕 선택이 이후의 선택에 영향을 주지 않는다, 독립적이다.
2. 전체 최적해가 부분 문제에 대해서도 최적해를 만족한다는 것이다.

첫 번째 이미지를 다시 보고 오길 바란다.
서울에서 부산으로 이어지는 경로는 서울 - 대전 - 부산 경로 뿐이다. 즉, 서울 - 대전, 대전 - 부산 경로는 각각 독립적이기 때문에 서울 - 대전 경로에서 어떤 것을 선택하느냐에 따라서 대전 - 부산 경로의 선택에 영향을 미치지 않는다.
첫 번째 조건을 만족한다.
또한 각 도시별 경로는 독립적이기 때문에 결과적으로 서울-대전의 최적해는 곧 전체 최적해의 부분 문제가 되고, 대전-부산의 최적해 또한 마찬가지다. 즉, 각 부분 문제의 최적해는 전체 문제의 최적해이자, 반대로 말하면 전체 최적해가 부분 문제에 대해서도 최적해를 만족한다는 것이다.

두 번째 이미지를 보고 오길 바란다.
두 번째 이미지는 최적해를 만족하지 못한다. 그 이유는 무엇일까?
일단 서울에서 부산을 가는 도중 두 가지 도시로 나뉜다. 서울 - 대전을 잇는 경로와 서울 - 원주를 잇는 경로로 나뉘게 된다. 그렇게 되면, 이후 선택지는 대전 - 부산 또는 원주 - 부산 경로로 나뉘게 되는데, 이는 처음 선택했던 경로에 따라 결정할 수 있는 경로에 영향을 미치기 때문에 독립적이지 않게 된다. 결과적으로, 독립적이지 않다는 것은 전체 최적해에 대해 부분 문제 또한 독립적이지 않아 항상 최적해를 만족하지 않는다까지 이어질 수 있는 것이다.

장점
장점은 뚜렷하다.
동적계획법과 달리 최적해를 100% 보장해주진 못하지만 각 순간별 최적 선택을 하기 때문에 근사 해를 구하는 속도가 매우 빠르다는 것이다. 그래서 동적계획법과 달리 그리디 알고리즘은 서로 상호보완하여 같이 쓰이기도 한다.
예를 들어 위의 두 번째 지도 이미지보다 더욱 많은 경로가 있을 때 일정 구간을 분기점으로 두고 그 안에서는 동적계획법을 통해 가장 빠른 루트를 구하여 가는 방식이 있다.

그렇다면 대표적인 문제들은 무엇인가?
대표적으로 거스름 돈 문제, 활동 선택, 신장 트리 문제들을 통해 그리디 알고리즘을 공부할 수 있다.

---

다시 문제로 돌아와서, 동전 0 문제 알고리즘을 풀이해보자.

위 문제를 보면 각 동전들은 서로 배수 관계에 있다는 것을 볼 수 있다. 
5는 1의 배수이고, 10은 5의 배수이고, 이렇게 모든 동전들은 서로 배수관계에 놓여 있다. 
이렇게 배수관계에 놓여있을 경우 풀리는 대표적인 문제가 거스름돈 문제, 동전 문제 같은 것들이다.
(실제로 화폐를 제작할 때에도 대부분 이런 식으로 배수관계가 되도록 한다고 한다.)

그럼 그리디 알고리즘을 어떻게 적용할 수 있는가?
아까 말했던 것처럼 최적해를 찾아나가면 된다.
K원을 만들 때 최소한의 개수를 이용해야 하므로 당연하게도 가장 큰 가치를 지닌 동전부터 선택해야 한다.

즉, N개의 동전 중 가장 큰 가치를 지닌 동전부터 탐색하여 동전의 가치가 K보다 클 경우는 넘어가고, 아닐 경우는 최대 구성 가능한 개수를 더해주면 된다. 

그리디 알고리즘의 장점 중 하나는 동적계획법보다 코드가 간결해진다는 것이다.
만약 동적계획법으로 풀었다면 결과는 같았더라도 중첩탐색이 이루어지기 때문에 결과적으로 시간이 더욱 오래걸렸을 것이다.

코드 java
1. Scanner

Scanner 활용

코드 node.js

nodejs 백준

---

출처 : https://st-lab.tistory.com/143

[백준] 11047번 : 동전 0 - JAVA [자바]

출처 : https://parkparkpark.tistory.com/92

[백준 11047번] 동전 0 - 자바스크립트(nodejs)