탐욕법 알고리즘 개요

탐욕법 알고리즘을 활용하는 문제. 탐욕법(Greedy Algorithm)은 동적 프로그래밍(또는 동적 계획법, Dynmaic Programming) 사용 시 지나치게 많은 일을 한다는 것에서 고안된 알고리즘이라고 한다. 두 방법은 서로 차이점이 존재하며, 보완하는 방식으로 활용이 된다고 한다.

동적 계획법은 전체 문제를 여러 개의 하위 문제로 쪼개어 풀고, 하위 문제의 해결 방법을 결합해 최종 문제를 해결한다. 피보나치의 수열이 대표적인 예이다. 이런 프로그래밍 방식은 효율을 위해 함수 결과 값을 저장하며 최종 결과물을 찾는다. 나름 계산 횟수를 줄여나가므로, 최장 공통 부분 수열, 부분집합의 합, 배낭 문제 등의 알고리즘 문제를 풀 수 있다.

탐욕법의 대표적인 예제는 활동 선택 문제 (Activity Selection Problem)가 있다. 한 번에 하나의 활동만 할 수 있는 강의실에서 제안된 활동 중 가장 많은 활동을 처리할 수 있도록 시간표를 짜는 문제이다. 가장 먼저 끝나는 활동을 택하면, 결과적으로 최대한 많은 활동을 시간표에 넣을 수 있다.

탐욕법은 문제 해결 과정에서 그 순간 순간 최적의 선택이라는, 즉 가장 좋아보이는 선택을 취하며 최종 해답에 도달한다. 즉, 앞으로의 선택이나 최종 결과를 고려하지 않는다. 그러므로 탐욕법으로 도출된 해가 반드시 최적의 해라는 보장은 없다. 대신 계산 속도가 빠르다는 장점이 있다.

문제

위 문제는 전체 학생 수 n, 체육복을 도난 당한 학생들의 번호가 담긴 배열 lost, 여벌 체육복이 있는 학생들의 번호가 담긴 배열 reserve가 주어진다. 체육복이 있어야 체육 수업을 듣는다 했을 떄 체육 수업을 들을 수 있는 최대 학생 수를 구해야 한다. 최대한 많은 학생들이 1벌 이상의 체육복을 갖도록 분배 해야 한다.

코드

풀이

우선 각 학생들이 모두 1벌의 체육복을 갖는다고 가정하고, 도난 당한 학생은 -1벌, 여벌이 있는 경우는 +1벌로 조정해주기로 한다. ES6에 추가된 문법인 fill() 메서드를 활용한다. Array(n).fill(1)는 n개의 원소를 가지는 배열에 fill()의 인자로 들어온 1이라는 숫자를 각 원소로 해준다. indexOf()를 통해 배열 내 해당 학생 번호가 존재하면, 학생들의 체육복 개수가 담긴 배열인 students의 원소를 조정한다.

두 번째 for문은 for of를 사용한다. 비구조화 할당(destructuring assignment)를 사용한다. Array.prototype.entries()는 배열의 각 인덱스에 대해 Key/Value 쌍의 새로운 Array Iterator 객체를 반환한다. let [index, curr] of students.entries()로 students 배열의 인덱스와 value(note: curr라고 네이밍한 것처럼, 이름은 무관하다. index, value 순이다.)를 변수에 선언한다.

만일 현재 값(curr)이 0일 때, 다음 번 학생의 체육복 개수가 2벌 이상일 때, students의 해당 학생들의 체육복 개수를 조정해준다. 마찬가지로 현재 값과 이전 값을 비교해주는 로직을 한 번 사용한다.

이후 Array.filter 함수를 통해 students 배열의 원소가 1이상인 경우의 길이를 구해 반환한다.

티스토리

[Programmers] JavaScript, 탐욕법, 체육복 문제 (Destructuring Assignment/fill)

[Programmers] JavaScript, 탐욕법, 체육복 문제 (Destructuring Assignment/fill)

탐욕법 알고리즘 개요

문제

코드

풀이

참고