[BaekJoon/백준] 1931번 [동적계획법 VS 그리디 알고리즘 정리 2차] | 복습 1회 완료

문제를 풀기 전, 동적계획법과 그리디알고리즘에 대해 조금 알아본다. 관심없다면 건너뛰면 된다.

---

동적계획법은 경우의 수를 모두 검토하기 위해 점화식을 통해 구성되는 반면, 그리디 알고리즘은 순간순간의 최적의 선택지를 선택하므로 그렇지 않는다는 차이점이 있는 것 같다.

 

 

그리디 알고리즘을 선택하기 위해선

 

1. 탐욕스러운 선택 조건

탐욕적 선택은 항상 안전하다는 것을 보여야 한다.

즉, 탐욕적 선택으로 전체 문제의 최적해를 반드시 구할 수 있다는 것을 보여야 한다.

 

2. 최적 부분 구조 조건

문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다는 조건.

 

두 조건을 만족해야 한다.

 

 

1번에서 말하는 것은 '각각의 상황마다 최적의 조건을 선택해도 이후의 최적의 선택에 실질적으로 영향을 주지 말아야 한다' 는 조건의 의미 즉, 탐욕스러운 선택 조건은 '탐욕적으로만 선택하더라도 전체 최적해를 구할 수 있다는 조건'이라고 이해하면 된다.

 

동적계획법과는 약간의 다른 느낌이 심어진다는 것을 알 수 있다.

 

동적계획법은 각각의 상황을 모두 고려하여 전체 최적의 조건을 위해 '점화식'을 세워 연산하고 비교하기 때문이다.

 

 

[ 헷갈릴 수 있는 점 정리 ]

 

최적 부분 구조 조건은 '문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다' 는 조건인데,

이를 위해선 각 부분문제가 독립적이여야한다는 의견이 있는데 이는 미지수다. 최적 부분 구조 조건에서도 독립성의 특징을 갖고 있다면, 동적계획법과 그리디 알고리즘의 선택 차이가 없어지기 때문.

 

탐욕스러운 선택 조건은 '탐욕적으로만 선택하더라도 전체 최적해를 구할 수 있다는 조건'인데, 매 순간 최적의 방법만 선택하더라도 전체가 최적의 방법이 될 수 있다는 말이니, '앞의 선택이 뒤의 선택에 영향을 주지 않아야 한다' 라는 등 각 부분문제가 독립적이여야 한다는 의미로 볼 수도 있으나, 활동선택문제만 해도 결국 선택들을 해나가다 보면 선택하지 못하는 경우들이 생기니 각 부분문제가 독립적이라고 말하기도 모호하므로 오히려 이해하는데 역효과가 날 수도 있다.

 

이렇듯 독립적이라는 말은 쉽게 정의할 수 있는 의미가 아니다.. 독립성을 연관지어서 최적부분구조와 탐욕선택조건을 생각하면 머리아프기 쉽상인 것 같다.

탐욕스러운 선택 조건이 '각 부분문제가 독립적이다' 라고 의미하며 설명하기도 하고, 최적 부분 구조 조건을 만족하기 위해선 이미 '각 부분문제가 독립적'인 상황이라는 전제를 말하는 설명들도 있다. 각 부분문제가 독립적이다라는 말은 추상적이다. 활동선택문제나, 경로문제를 통해 그리디알고리즘과 동적계획법문제를 통해 비교해봐도 의미가 뚜렷하지가 않다.

 

탐욕스러운 선택 조건 또는 최적 부분 구조 조건의 특징이 '각 사건이 독립적'이다를 두고 갑론을박 하게되면 오히려 이해하기가 더 어려워진다. 추상적이지 않은 전제들을 갖고 비교하고 따지다 보면 악효과가 날 수도 있으니, 느낌만 갖고 있으면 될 것 같다. 관점에 따라서도 다를 수 있고, 그리고 추상적일 수 있는 것 같다.

 

즉, 

탐욕스러운 선택 조건 -> 매 순간 탐욕적 선택으로 전체 문제의 최적해를 반드시 구할 수 있다는 것

( 동적계획법은 각각의 상황을 모두 고려하여 전체 최적의 조건을 위해 '점화식'을 세워 연산하고 비교 )

 

최적 부분 구조 조건 -> 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다는 조건

 

참고 -

yongjoonseo.github.io/algorithm%20concepts/swea-advanced03/

peung.tistory.com/7

coding-sj.tistory.com/86

rain-bow.tistory.com/entry/DP와-Greedy-Algorithm

 

---

이번 문제는 그리디 알고리즘의 대표 유형인 '활동 선택 문제'다.

 

시간표 짜기, 회의실 시간 분배, 알바 시간 분배 같은 활동 선택 문제 유형이다.

 

이런 활동 선택 유형은 그리디 알고리즘으로 풀어나갈 수 있다.

 

탐욕적인 선택은 '끝나는 시간이 가장 이른 활동'을 매 순간 선택하는 것이다.

 

그 중에서도 이 문제의 조건은, 시작 시간과 끝나는 시간이 같은 경우 (3 3, 4 4 등등)에도 그것을 쳐준다는 것.

그리고 끝나자마자 시작할 수 있다는 것 (1 3, 3 4)

 

이 두 조건을 생각하여 문제를 풀어야 한다.

 

 

우선 끝나는 시간이 가장 이른 활동을 선택해야 하므로, 활동에 대한 배열을 끝나는 시간 기준으로 오름차순으로 정렬한다.

예를들어 아래와 같은 데이터가 있을 때

8 8
7 8
1 3
4 5

이를 끝나는 시간 기준으로 오름차순 정렬하면

1 3
4 5
8 8
7 8

이 된다. 

 

이렇게 되면 1 3 -> 4 5 -> 8 8을 선택할 수 있게 되는데, 이게 이 문제에서 최적의 답이 아니다.

최적의 답은 1 3 -> 4 5 -> 7 8 -> 8 8이다. (시작과 끝나는시간이 동일해도 쳐주기 때문에)

 

그렇기때문에, 끝나는 시간이 같다면 시작 시간을 다시 오름차순으로 정렬해줘야 한다.

 

그렇게 되면

1 3
4 5
7 8
8 8

이렇게 깔끔하게 만들어질 수 있다.

 

자, 그럼 이제 정렬을 구현해야 한다. 벡터를 이용하는 방식도 있겠지만, 나는 배열을 사용했다.

 

이전 2565번(전깃줄 문제)과 비슷하게 이차원배열을 정렬하는 방식을 구현해야 한다.

 

2512번과 동일하게 단순 삽입 정렬로 수행하려했으나, 단순삽입정렬의 특징상 시간복잡도가 O(n^2)인 바람에 문제의 시간에 충족되지 못한다.

 

그래서 O(log n)의 시간복잡도를 갖는 퀵소트를 사용했다.

 

 

이렇게 정렬을 완료한 데이터를 이용해서, 배열의 처음부터 돌면서 last_end 라는 '가장 최근의 종료 시간' 변수를 업데이트해나가면서, 시간을 선택할 수 있는지 여부를 따진다. 선택할 시간은의 시작시간과 끝나는시간은 last_end보다 크거나 작아야 할 것이다.

#include <stdio.h>
#include <stdlib.h>

int N;
int con[100000][2]; // [0] = 시작 시간, [1] = 끝 시간

int last_end = 0;

int count = 0;

int compar(int *a, int *b) {
    
    if(*(a + 1) < *(b + 1))
        return -1;
    else if(*(a + 1) > *(b + 1))
        return 1;
    else {
        
        if(*a < *b)
            return -1;
        else if(*a > *b)
            return 1;
        else
            return 0;
    }
    
}
int main() {
    
    int i;
    scanf("%d", &N);
    
    for(i = 0; i < N; i++ ) {
        scanf("%d %d", &con[i][0], &con[i][1]);
    }
    
    qsort(&con[0][0], N, sizeof(con[0]), compar);
    
    for(i = 0; i < N; i++) {
        if(last_end <= con[i][1] && last_end <= con[i][0]) {
            last_end = con[i][1];
            count++;
        }
    }
    printf("%d", count);
}

활동 선택 문제 참고

blog.naver.com/qpghnv/221597913108

 

 

---

2021.02.26 복습

다시풀어보았다.

#include <stdio.h>
#include <stdlib.h>

int N;
int L[100000][2];

int last; // 가장 최근 종료 시간
int count;

int compar(int *a, int *b) {
    
    // 끝나는 시간을 기준으롤 오름차순 정렬
    if(*(a+1) < *(b+1))
        return -1;
    else if(*(a+1) > *(b+1))
        return 1;
    
    // 끝나는 시간이 같다면, 시작 시간을 기준으로 오름차순으로 정렬
    else {
        if(*a < *b)
            return -1;
        else if(*a > *b)
            return 1;
        else
            return 0;
    }
}

int main() {
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++)
        scanf("%d %d", &L[i][0], &L[i][1]);
        
    qsort(L, N, sizeof(L[0]), compar);
    
    
    for(int i = 0; i < N; i++) {
        
        // 가장 최근 종료 시간보다 시작 시간이 더 크거나 같으면, 가장 최근 종료 시간을 업데이트
        if(L[i][0] >= last) {
            last = L[i][1];
            count++;
        }
    }
    
    printf("%d", count);
}




/*
 
 회의실 배정
 
 1 4
 3 5
 0 6
 5 7
 3 8
 5 9
 6 10
 8 11
 8 12
 2 13
 12 14

 끝나는 시간으로 오름차순 정렬하되, 끝나는 시간이 같을 경우 시작 시간으로 오름차순 정렬
 
 1 4
 3 5
 0 6
 5 7
 3 8
 5 9
 6 10
 8 11
 8 12
 2 13
 12 14

 가장 최근 종료 시간 = last
 
 last <= 시작시간 일 경우(시간안겹침), last =  종료시간 으로 업데이트 & count 1 증가
 
 -------------
 풀이 예시
 
 
 7 7
 1 7
 7 8
 
 ->
 
 1 7
 7 7
 7 8
 
 last(=0) >= 1 이므로 last = 7, count = 1
 last(=7) >= 7 이므로 last = 7, count = 2
 last(=7) >= 7 이므로 last = 8, count = 3
 
 
 */

처음에 풀었던 것 보다 더 간단하게 푼 것 같다. (조건식을 하나로 해결)