✅ 그리디 알고리즘

그리디 알고리즘

"미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법"

이러한 특징으로 인해, 속도는 매우 빠르다는 장점이 있지만, 항상 최선의 값을 보장받을 수는 없다는 단점 또한 존재한다.

대표적인 문제: 거스름돈

https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188
위 링크에 그리디가 잘 설명되있다.

---

ATM [Baekjoon]

문제

https://www.acmicpc.net/problem/11399

코드

let arr = []
const fs = require('fs');
const stdin = (process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `5
3 1 4 3 2
`
).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();
input();
input().trim().split(' ').map(t => arr.push(Number(t)))

// 오름차순으로 정렬
let sorted = arr.sort((a, b) => a - b)
// 뒤의 값에 앞의 값을 덧씌워준다.
sorted.reduce((acc, cur, i) => sorted[i] = acc + cur)
// sorted 내부에 있는 값들을 모두 합해준다.
const result = sorted.reduce((acc, cur) => acc + cur)
console.log(result)

풀이

1. 입력받은 값들을 오른차순으로 정렬해준다.
   ex) 3 1 4 3 2 => [1,2,3,3,4]

2. 뒤의 값에 앞의 값을 덧씌워준다.
   ex) [1,2,3,3,4] => [1,3,6,9,13]

3. sorted 내부에 있는 값들을 모두 합해준다.
   ex) [1,3,6,9,13] => 32

조이스틱 [Programmers]

문제

https://programmers.co.kr/learn/courses/30/lessons/42860

코드

function solution(name) {
    var answer = 0;
    var alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    // 알파벳 탐색
    function search(word) {
        for (let i = 0; i < alphabet.length; i++) {
            if (alphabet[i] === word) {
                console.log('findf', answer, i, word)
                return answer;
            } else if (alphabet[alphabet.length - 1 - i] === word) {
                console.log('findb', answer, i, word)
                return answer++;
            }
            answer++;
        }
    }
    for (let i = 0; i < name.length; i++) {
        search(name[i]);
    }
    console.log(answer)
    let minMove = name.length - 1;
    for (let i = 1; i < name.length; i++) {
     	// 'A'를 만나면
        if (name[i] === 'A') {
        	// 'A'를 그만 만날때까지 for문을 돌려준다.
          	// j에는 마지막 A의 위치가 저장됨
            for (var j = i + 1; j < name.length; j++) {
                if (name[j] !== 'A') break;
            }
          	// 왼쪽으로 가는 경우
            const left = i - 1;
          	// 오른쪽으로 가는 경우
            const right = name.length - j
            minMove = Math.min(minMove, left > right ? left + right * 2 : left * 2 + right);
            i = j;
        }
    }
    return answer + minMove;
}

풀이

초기 상태

여기에서 name="jaan"이 주어졌을 때,


다음과 같은 과정을 거쳐 j와 n으로 바꿔준다.

만약 아래와 같이 오른쪽으로만 움직였다면,

쓸데없이 변경하지 않아도 되는 A를 지나쳤기 때문에, 조이스틱을 더 많이 움직이게 된다.

여기까지가

1. 오른쪽으로만 직진해서 가는 방법
2. a를 만나면, 왼쪽으로 되돌아 가는 방법

이였다.

여기서 a를 만나면 왼쪽으로 가는 방법은,
a를 지나쳤을때보다, 왼쪽으로 되돌아 갔을 경우에 조이스틱을 더 적게 움직일 때만 사용해야 한다.

또한, 한 가지의 예외가 더 있는데 아래와 같은 경우이다.

우선, 2번에 의해 B->A->C 가 아닌, B->D 방면으로 움직인다.

하지만 여기서 그대로 직진해 A를 3개나 지나치는 방법보다, 다시 되돌아가서 C를 변경시키는 경우가 더 효율적이다.

그대로 직진하는 경우,

되돌아가는 경우,

따라서, 다시 방향을 전환해 되돌아가야한다.

정리

case 1

'->' 방향으로 가다가 'A'를 만나면 반대 방향인 '<-'방향으로 쭉 되돌아간다.

case 2

처음부터 '<-'(즉, 시작부터 맨 끝으로 이동해 시작) 방향으로 가다가 'A'를 만나면 반대 방향인 '->'방향으로 쭉 되돌아간다.

case 3

처음부터 끝까지 일관되게 '->'방향으로만 이동한다.

이해를 위해 또다른 예시를 들어서 설명하겠다.
"ABAAAAABAB"라는 문자를 조이스틱으로 만들기 위해서 우선 index=1 이후부터 A를 찾는다.

case 1

첫 번째로 만난 A는 index=2부터 index=7까지 자리하고 있으므로, i=2, j=7이 된다.

다음 단계로는 left와 right를 구해야 한다.
left는 index=1부터 A(i)까지의 거리,
right는 오른쪽 끝부터 A(j)까지의 거리를 나타낸다.
따라서 오른쪽으로 갔다가 다시 왼쪽으로 쭉 가는 경우에는 left 부분을 2번 지나가게 되므로
left*2+right = 5 라는 연산이 가능하다.

case 2

또 다른 case는 case1을 끝내고 반복분을 돌리고 있을 때, A를 다시 만난다면
다시 left,right를 구해서 연산을 해줘야 한다.
위의 코드는 시작하자마자 맨 뒤로 갔다가 A를 만나면 다시 반대 방향으로 이동한다.
즉 시작하자마자 '<-'방향으로 이동해 A를 만나면 반대 방향인 '->'방향으로 이동한다.

case 2 다시 설명

이번에는 "BBBAAB"를 가지고 다시 case 2를 설명해보겠다.

위의 그림과 같이, 바로 왼쪽으로 갔다가 젤 오른쪽을 B로 수정해주고 다시 왼쪽으로 가는 경우가 case 3이다.
이러한 경우에는, right를 2번 지나가게 되므로 right*2를 해주는 것이다.
따라서 left+right*2 = 4라는 결과가 나온다.

---

case 3

마지막 case는 처음부터 끝까지 방향 전환을 하지 않고 일관되게 오른쪽(->) 방향으로 가는 방법이다.
간단한 예시로는 'BCDEF' 는 A를 만나지 않기에 방향 전환을 할 필요가 없다. 따라서 이런 case는 let minMove = name.length - 1; 부분에서 담당한다.