개발자로 살아남기

그리디(Greedy) 알고리즘 (탐욕 알고리즘)

참고 사이트 :

1. https://www.geeksforgeeks.org/greedy-algorithms/

2. https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디 알고리즘

• 매 순간마다 최적의 값을 찾음
• 매 순간의 최적값을 모두 더한것이 전체의 최적값이길 바람
• 결과값이 항상 최적값이라고 보장할 수 없음
• 탐욕스러운 선택 조건, 최적 부분 구조 조건이 만족해야만 최적해를 구할 수 있음
  탐욕스러운 선택 조건 : 앞서 선택한 것이 이후의 선택에 영향을 미치지 않음
  최적 부분 구조 조건 : 문제에 대한 최적해가 부분 문제에 대해서도 최적해가 됨
• 조건이 만족하지 않으면 최적해를 구할 수 없지만, 근사 알고리즘으로 사용가능하며(근사값) 계산속도가 빨라 실용적으로 사용 가능
• 그리디가 적용된 알고리즘 종류
  1) 크루스칼 알고리즘
  2) 프림 알고리즘
  3) 다익스트라 알고리즘
  4) 허프만 코딩 등...

예시) 활동 선택 문제

시작 및 종료 시간이 주어지며, 한 사람이 한 번에 하나의 활동만 수행할 수 있다고 가정했을 때 한 사람이 할 수 있는 최대 활동의 개수 구하기 시작시간 : [1, 3, 5, 7, 9, 13] 종료시간 : [4, 5, 7, 9, 12, 15] 최대 활동 개수 : 5개 [1~4, 5~7, 7~9, 9~12, 13~15]

활동 선택 문제 풀이

package Greedy;

public class ActivitySelectionProblem {
    public static void main(String[] args) {
        int[] start = {1, 3, 5, 7, 9, 13};
        int[] finish = {4, 5, 7, 9, 12, 15};
        // 활동 개수
        int n = start.length;
        int i=0;
        int count=0;

        // 다음 활동 시작 시간이 이전 활동의 끝나는 시간보다 클 경우를 구해야 하므로 j=1
        for(int j=1; j<n; j++){
            if (start[j] >= finish[i]){
                System.out.println(String.format("%d~%d", start[i], finish[i]));
                i = j;
                count++;
            }
        }
        // 마지막 시간은 반복문에서 제외됨
        if (start[i] >= finish[i-1]){
            System.out.println(String.format("%d~%d", start[i], finish[i]));
            count+=1;
        }

        System.out.println("최대 활동 개수 : " + count);
    }
}

작성예정...

오른쪽으로 가는것을 기준으로 잡고 풀었다. 좌, 우 이동만 가지고 얘기하자면, 현재 위치를 기준으로 왼쪽/오른쪽 거리를 계산했을 때, 한 번이라도 왼쪽 거리가 짧을 경우 name의 끝에서부터 빼면서 계산했다. 다른 사람의 풀이를 보면 엄청 쉽게 구현하던데 신기하다...

탐욕법은 매 순간마다 최적의 값을 찾는다. 탐욕법은 탐욕스러운 선택 조건과 최적 부분 구조 조건을 가지는 특징이 있는데, 탐욕스러운 선택 조건은 앞에서 내가 선택한 것이 이후의 선택에 어떠한 영향을 미치지 않는다는 조건이고 최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 최적해여야 한다는 특징이 있다. 

이 문제에서는 인덱스 0 위치에서 왼쪽으로 갈 경우 문자열의 끝에 갈 수 있지만 문자열의 끝에서 오른쪽으로 갈 경우 인덱스 0위치로 갈 수 없다. 그래서 아래와 같은 결과가 나오게 된다.

ABAAAABAAAAAAAAAAAAB => 최적해 (13) / 실제 계산한 해 (19)

탐욕법 자체가 이미 지나온 길을 되돌아갈 수 없다고 하면 탐욕법이 맞는거 같기도하고.. 아리송하다.

public int solution(String name) {
    int answer = 0;
    int notA_Count = 0;
    int curCount = 0;
    int lastIndex = 0;
    char curChar = 'A';
    boolean leftSmallerThanRight = false;

    // A가 아닌 개수 및 A가 아닌 마지막 인덱스 구하기
    for(int i=0; i<name.length(); i++){
        if (name.charAt(i) != 'A'){
            lastIndex = i;
            notA_Count++;
        }
    }

    // 오른쪽으로 갈 수 있는 최대 구하기
    // 인덱스 0을 기준으로 왼쪽으로 갔을 때 몇번째 값이 A가 아닌지 확인 (0의 위치에서 왼쪽으로 갈 경우 거리값이 +1이 되어야 함)
    int leftCount = name.length() - lastIndex;
    int rightCount = 0;
    int curPos = 0;
    int upDownCount = 0;
    for(int i=0; i<name.length(); i++){
        curChar = name.charAt(i);
        if (curChar == 'A'){
            continue;
        }

        // i 위치에서 현재 위치를 빼면 오른쪽으로 몇 번 가야 A가 아닌 문자가 나오는지 알 수 있음
        rightCount = i - curPos;

        // A가 아닌 문자를 만나기 위해 오른쪽으로 간 횟수와 왼쪽으로 간 횟수를 비교
        // 왼쪽으로 간 횟수가 더 적을 경우 빠져나와 맨 오른쪽에서 왼쪽으로 진행하기 위해 빠져나옴
        if (rightCount > leftCount + curPos){
            leftSmallerThanRight = true;
            break;
        }
        else{
            answer += rightCount;
        }

        // 알파벳 구하기
        upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
        answer += upDownCount;

        // 현재 위치를 i번째로 옮김
        curPos = i;
        rightCount = 0;
        curCount++;
    }

    // 현재 위치에서 왼쪽으로 가는게 더 빠른 경우가 있을 때
    // 현재 위치부터 왼쪽으로 구해야 하니까 leftCount는 curPos 값으로 변경
    leftCount = curPos;
    if (leftSmallerThanRight){
        for(int i=name.length() - 1; i>=0; i--){
            if (notA_Count == curCount){
                break;
            }

            curChar = name.charAt(i);
            // A면 한 칸 이동
            if (curChar == 'A'){
                leftCount++;
                continue;
            }
            leftCount++;

            upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
            answer += upDownCount;
            answer += leftCount;
            leftCount = 0;
            curCount++;
        }
    }

    return answer;
}