그리디 ) 현재의 최적의 선택을 미래의 최적의 선택으로

작성일 In Views: Disqus:

▪︎ 그리디 알고리즘

그리디 알고리즘은 미래를 고려하지 않고, 오직 현재 시점에 가장 좋은 선택을 하는 알고리즘입니다. 현재의 선택이 미래에 어떤 영향을 미칠지는 고려하지 않고, 무조건 현재 가장 빠른 선택, 가장 가치있는 선택을 내리게됩니다. 현실에서는 모든 경우를 고려하면 리소스가 너무 크고, 당장의 최적의 결과만을 쫓는다 하더라도 미래에 (최적의 결과는 아니지만) 어느 정도 보장된 결과를 내고 싶을 때 사용되는 알고리즘입니다.

그러나 코딩테스트에서 우리는 모든 케이스에 적용되는, 항상 최적의 결과가 되는 답을 찾아내야 합니다. 따라서 현재의 최적의 답이 미래의 최적의 답이 되는 상태에서만 적용할 수 있습니다.

▫︎ 그리디 알고리즘을 적용할 수 있는 경우

  1. 현재의 선택이 미래의 선택에 영향을 주지 않는다. (탐욕스러운 선택 조건)
  2. 부분의 최적해가 모이면 전체의 최적해가 된다.

image.png

500원, 100원, 10원 짜리 동전들을 위 그림과 같이 가지고 있다고 할 때, 동전을 가장 적게 사용하면서 2120원을 만드는 방법을 고민해봅시다.

그리디 알고리즘에 따라 동전을 선택한다면 가장 큰 액수의 동전을 선택하는 것이 현재 상황에서 가장 적은 개수로 2120원에 가까워지는 방법입니다. 이 때 (1) 지금 내가 500원을 선택한 것 때문에 미래에 100원 대신 10원을 선택해야만 경우나 10원 대신 100원을 선택해야만 하는 경우는 없습니다. 또한 (2) 각 동전을 선택하는 시점에서, 남은 액수를 넘지 않는 동전 중 가장 큰 액수의 동전을 선택하면 가장 적은 동전의 수로 2120원을 맞출 수 있습니다.

대부분의 코딩테스트 경우에서 그리디 알고리즘의 적용은 주어진 데이터를 “각 판단의 시점마다 동일한 동작으로 최적해를 찾을 수 있도록 설정”하고 “예외 조건을 찾아 처리”해주는 형태로 코드를 작성하게 됩니다. 따라서 대부분의 케이스에서 그리디 문제의 핵심은 데이터의 정렬로 볼 수 있습니다. 주어진 데이터를 정렬할 수 있는 여러 방법들을 우선적으로 고려해봅니다.

▪︎ Example of Apply 1

image.png

위 문제는 겹치지 않고 진행할 수 있는 최대 회의 수를 출력하는 문제입니다. 직관적으로 볼 때 가장 많은 회의를 진행하기 위해서는 가장 빨리 끝나는 회의를 먼저 처리하면 남은 시간이 많아지기 때문에 정답에 가까울 것 같습니다.

  1. 데이터 설정) 입력받은 배열 데이터들의 인덱스 1 을 기준으로 오름차순 정렬합니다. 이 때 인덱스 1의 값이 같은 경우 인덱스 0의 값이 더 작은 (빨리 시작하는) 데이터를 우선합니다.
  2. 예외 조건 처리) 정렬한 데이터를 순차적으로 순회하며 카운팅하되, 아직 이전 회의가 진행중이라면 카운팅하지 않습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const fs = require("fs");

const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
const arr = input.slice(1).map((el) => el.split(" ").map(Number));

arr.sort((a, b) => {
  if (a[1] === b[1]) return a[0] - b[0];
  else return a[1] - b[1];
});

let prev = 0;
let answer = 0;

arr.forEach(([start, end]) => {
  if (prev <= start) {
    answer++;
    prev = end;
  }
});

console.log(answer);

▪︎ Example of Apply 2

image.png

image.png

이번 문제는 모든 회의가 가능하도록 하는 강의실의 개수를 출력하는 문제입니다. 현재 진행중인 강의의 개수를 추적하고, 지금까지 동시에 진행된 강의가 가장 많을 때마다 정답을 업데이트해주면 풀 수 있을 것 같습니다. 강의의 개수를 추적하는 방법은 강의가 시작되고 끝나는 시간에 값을 부여하여 시간마다 그 값을 더해주면 됩니다. 그렇게 타임 테이블을 만들고 오름차순 정렬하여 데이터를 순회하면 정답을 도출할 수 있습니다.

타임테이블을 배열로하여 인덱스를 시간으로 추상화하는 방법은 Si, Ti의 최대값이 10^9 이므로 메모리 초과가 뜰 것 같습니다. 따라서 입력받은 데이터들에 저장된 시간들을 O(1)의 시간 복잡도로 조작가능한 Map 함수에서 key : value 형태로 관리하겠습니다. 각 시간에 시작하는 회의가 있을 때 +1, 끝나는 회의가 있을 때 -1을 하면서 시간단위로 강의실 개수를 추적합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const fs = require("fs");

const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
const arr = input.slice(1).map((el) => el.split(" ").map(Number));
const timeTable = new Map();

// 타임테이블 생성
for (let i = 0; i < arr.length; i++) {
  timeTable.set(arr[i][0], timeTable.get(arr[i][0]) ? timeTable.get(arr[i][0]) + 1 : 1);
  timeTable.set(arr[i][1], timeTable.get(arr[i][1]) ? timeTable.get(arr[i][1]) - 1 : -1);
}

// 타임테이블 정렬
const answerArr = Array.from(timeTable).sort((a, b) => a[0] - b[0]);
let answer = 0;
let lectures = 0;

// 타임테이블 순회
answerArr.forEach((el) => {
  lectures += el[1];
  if (lectures > answer) answer = lectures;
});

console.log(answer);