51일차 [자료구조/알고리즘] Greedy Algorithm

2021. 10. 06 수요일

1. Today's Key Points!🔑

• Algorithm
• Time Complexity, Big-O
• Greedy Algorithm

2. 정리해보자!🧹

알고리즘이란? 알고리즘은 문제를 해결하는 최선의 선택이다.

컴퓨터를 이용해서 문제를 해결할 때에는, 무수히 많은 방법을 시도할 수 있다. 모든 경우의 수를 하나씩 비교해서 그 중 최선을 골라낼 수도 있고, 하나씩 비교하지 않더라도 가장 좋아 보이는 것을 먼저 찾아냈다면 뒤 쪽의 경우의 수를 그냥 무시하는 경우도 있다.

우리는 컴퓨터가 최선을 수로 값을 도출해 낼 수 있도록 코드를 짜주어야 한다.

어떻게?

1. 문제를 이해하자. 대부분의 코딩 테스트에서는 문제의 설명과 입출력예시, 제한사항, 그리고 주의사항 등으로 문제 상황을 제시한다. 주어진 조건을 토대로 문제가 무엇인지를 이해하는 것부터 시작해야 한다.
2. 문제를 어떻게 해결할 수 있을지, 전략을 세우자. 수도코드를 먼저 작성하고, 연습장에 전체적인 그림을 그려가면서 전체적인 흐름을 파악해야 한다.
3. 문제를 코드로 옮겨보자. 앞서 세운 전략을 코드로 옮겨서 해결한 뒤, 구현한 코드를 최적화시키는 것을 시도해보자.

이렇게 알고리즘 문제 해결을 위한 해답을 찾는 것이 가장 중요하다. 그런데 그에 못지않게 효율적인 방법으로 문제를 해결했는지도 중요하다. 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같은 말이다.

시간복잡도? 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는지를 고민하는 것이 시간복잡도를 고민한다는 말이다. 그리고 이 시간 복잡도는 주로 Big-O 표기법을 사용해 나타낸다.

시간 복잡도 그래프

O(1)

constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 다시 말해서 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다.

O(n)

linear complexity라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다. 예를 들어서 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있다. 보통 하나의 반복문(for)이 O(n)의 시간 복잡도를 가진다. 2n, 5n, 10n으로 시간 복잡도가 증가한다 하더라도 입력값이 커지면 커질수록 계수의 영향력이 점점 퇴색되기 때문에 그냥 O(n)으로 표기한다.

O(log n)

logarithmic complexity라고 하며, Big-O 표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다. 이진 탐색같은 로직이 O(log n)의 시간복잡도를 가진다. 

O(n^2)

quadratic complexity라고 하며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다. 보통 다중 반복문이 O(n^2)의 시간복잡도를 가진다.

O(2^n)

exponential complexity라고 하며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다. 연산을 할 때 마다 계속 2배로 증가하는 것을 말한다. 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고민해 보는 것이 좋다. 대표적인 예로 재귀로 구현하는 피보나치 수열이 있다.

Greedy Algorithm

당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법.

1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

이에 대한 예시는 아래의 코플릿 복기를 통해 보여주고자 한다.

3. Coplit과제 복기!🧐

👉🏻짐나르기(Greedy)

- 문제 : 짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

- 풀이 : 가장 최소한의 박스 갯수를 사용해야하는데, 그렇게 해주려면 가장 무거운 것 부터 박스에 넣어주면 될 것이다. 근데 이때 가장 가벼운것을 무거운 짐을 옮길때 같이 넣어서 옮길 수 있다면 최소한의 박스를 사용할 것이라고 판단했다.

그래서 stuff를 정렬해주면 가장 가벼운것이 가장 왼쪽, 가장 무거운 것이 오른쪽으로 갈것이고, 가장 오른쪽 짐은 일단 담고, 가장 왼쪽 짐을 담을 때 limit에 걸리면 다시 stuff에 담고, 그것이 아니라면 같이 넣어주고 카운트를 세서 최소한의 박스 갯수를 리턴한다는 방식으로 코드를 작성해주었다.

function movingStuff(stuff, limit) {
  let box = [], count = 0
  let sorted = stuff.sort((a, b) => a - b);

  while(sorted.length){
    box.push(sorted.pop());
    let now = sorted.shift();  
    if(now + box[0] > limit){
      sorted.unshift(now);
      box = [];
    }
    else {
      box = [];
    }
    count++;
  }
  return count;
}

//입출력 예시
let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3

let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4

👉🏻편의점 알바(Greedy)

- 문제 : 현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원이 있습니다. 동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

- 풀이 : 이것도 위의 문제와 비슷하게 가장 비싼 동전을 먼저 사용하고 그 다음 동전, 그 다음 동전을 사용하는 방식으로 풀면 되겠다고 생각했다.

만약, 4782원의 거스름 돈을 걸러주어야 한다면, 500원짜리 9개, 100원짜리 2개, 50원짜리 1개, 10원짜리 3개, 1원짜리 2개를 거슬러주면 동전 갯수를 최소로 사용한 17개의 동전을 거슬러 줄 수 있을 것이다.

그래서 동전의 타입을 내림차순의 배열로 만들어서 반복문을 돌렸을 때 가장 금액이 큰 동전부터 사용할 수 있도록 해주었다. 그리고 가장 큰 동전으로 거스르고 남은 금액을 가지고 앞의 내용을 반복해주는 코드를 작성해주었다.

function partTimeJob(k) {
  let count = 0;
  let arr = [500, 100, 50, 10, 5, 1]
  for(let i = 0; i < arr.length; i++){
    count += Math.floor(k / arr[i]);
    k = k % arr[i];
  }
  return count;
}

👉🏻보드게임

- 문제 : N * N의 크기를 가진 보드판 위에서 게임을 하려고 합니다. 보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하세요.

단, 시작은 board[0][0]에서 시작. 보드판에서 벗어나면 OUT처리

- 풀이 : 문제 그대로 코드를 구현해주면 되는 문제였다. 대신 문제에 걸려있는 조건을 잘 처리해주어야 한다.

결과값, 행, 열 값을 초기값으로 0을 할당해주고, operation을 배열로 담아서 이 배열을 반복문을 돌려 결과값에 해당하는 보드를 밟을 때 마다 더해주는 코드를 짜주고, 보드 밖으로 넘어가면 OUT처리해주는 조건을 작성해주면 된다.

function boardGame(board, operation) {
  let result = 0;
  let row = 0, col = 0;
  let arr = operation.split('');
  for(let i = 0; i < arr.length; i++){
    if(arr[i] === 'U') row--; //위로 이동
    if(arr[i] === 'D') row++; //아래로 이동
    if(arr[i] === 'L') col--; //왼쪽으로 이동
    if(arr[i] === 'R') col++; //오른쪽으로 이동
    //보드판에서 벗어나는 조건
    if(row < 0 || col < 0 || row >= board.length || col >= board.length){
      return 'OUT'
    }
    result += board[row][col];
  }
  return result;
};