파이썬_고득점키트_문제풀이(2)

2. 탐욕법 대표 문제 풀이 : 체육복

그리디 분류의 체육복 문제 풀이.
간단한 문제고 쉬운 내용이지만, 재밌는 걸 살펴볼 수 있다.
문제 이해
바로 앞 번호, 바로 뒷 번호 학생에게만 빌려줄 수 있다.
가능한 한 많은 학생이 체육수업을 듣도록.
전체학생 수는 2명 이상 30명 이하
여벌 체육복을 가지고 있는 학생도 체육복을 도난당했을 수 있다.
입출력 예

문제의 해결 - 예제

어떤 생각을 하면서 이 문제를 푸는가?
사람은 통찰력이 있기 때문에, 한눈에 그 해결방안을 찾을 수 있다.
컴퓨터에게 일을 시킬 때는, 단계별로 알고리즘을 구성해야 한다.
이 해법은 이거구나 라고 느끼는 것을, 한눈에 통찰하는 것이 아닌. 단계별로의 흐름을 깊이 생각해봐야 한다.
n = 5
빌려줄 학생들 1,2,3,4,5
빌릴 학생들 1,2,3,4,5
여벌의 체육복 -> 1,3,5
도난 당한 학생들 : 2,4
이 문제를 해결하는 방법 : 1번이 2번에게, 3번이 4번에게, 그 다음 빌려줄 학생이 없으니 답은 1,2,3,4,5 다섯명
똑같은 답이지만, 빌려주는 모양새를 다르게 할 수 있다.
3번이 2번에게, 5번이 4번에게 빌려주어도 5명 전체가 체육수업을 들을 수 있다.
이 생각을 절차적으로 기술해보자.

탐욕법 (Greedy Algorithm)

알고리즘의 각 단게에서 그 순간에 최적이라고 생각되는 것을 선택
탐욕법으로 최적해를 찾을 수 있는 문제
현재의 선택이 마지막 해답의 최적성을 해치지 않을 때
탐욕법 적용 가능성
이런 경우는 어떨까?
2,4,6은 빌려줄 수 있고
1,3,5은 도난당한 학생
2번부터 시작해서 3번에게 빌려주고, 4번이 5번에게 빌려주고, 6번은 체육복을 가지고 있음에도 불구하고 1번에게 빌려줄 수는 없다.
이 경우, 전체 최적의 수를 못한 경우다.
작은 번호부터 큰 번호를 고려하려고 하면,
2번이 1번에게, 4번이 3번에게. 즉 6번은 5번에게 빌려줬어야 한다.
큰 번호부터, 거꾸로 셈해왔다면, 우선적으로 빌려줘야할 방향이 반대가 된다.
비슷한 방법으론 내가 문제를 풀었었다.

탐욕법 적용 가능성 확인

이런 경우는 생길 수 없을까?
빌려줄 학생들을 “정해진 순서”로 살펴야 하고, 이 “정해진 순서”에 따라 우선하여 빌려줄 방향을 정해야 함
- 나보다 앞에 있는 학생들을 먼저 빌려주고, 그 이후 안되는 경우에 뒤의 학생에게 빌려줄 상황을 고려해야 함

문제 해결방법 (1)

예제와 함께 손으로 핸드 시뮬레잇녀.
(착안점) - 학생의 수는 기껏해야 30명!
학생 수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다.
번호 순서대로 “스캔”하면서 빌려줄 관계를 정한다.
예를 들어
학생이 전부 10명, lost =[1,5,8,3,7], reserve[7,5,2,9,6]
처음에는 모든 학생이 체육복을 가지고 왔다고 가정 [1,1,1,1,1,1,1,1,1,1]
그리고 코드 구현을 쉽게 하기 위해서, 매 단계에서 나보다 앞의 번호, 뒤의 번호를 살펴봐야 하니까
앞 뒤로,1번의 앞에, 10번의 뒤에 고려하지 않는 수를 양쪽에 막아둘 수 있다.
- (이런게 내가 부족했던 것.) 마치 스택에서 더미노드처럼 사용하는 것이다.
reserve에 들어있는 내용을 살펴본다.
그 위치 보면서 하나씩 늘려놓는다.
그 다음 lost 배열을 살피면서 -1을 한다.
그럼 왼쪽부터 스캔한다. 0이면 빌려줄 수 없지. 2번 보면 빌려줄 수 있지 ?-> 왼쪽 1번에게 빌려줄 수 있는 규칙 적용
결과적으로 1번 부터 10번까지의 학생 중에 체육복 가지고 있지 못한 학생은 1명 뿐 따라서 9를 산출.

알고리즘의 복잡도

여벌을 가져온 학생 처리 : reserve의 길이에 비례
체육복을 잃어버린 학생 처리 : lost의 길이에 비례
체육복 빌려주기 처리 : 전체 학생 수 (n)에 비례
전체 O(n) linear time 알고리즘.

문제 해결방법(2)

앞의 방법의 걱정과 미심쩍음.
만약 전체 학생 수가 매우 크다면 ?
- 예를 들어 한 학급에 천만명이라고 치면
- 하지만 문제의 성질상 O(n) 낮은 복잡도 알고리즘은 어려울 듯?
그런데 여벌의 체육복을 가져온 학생은 매우 적다면 ?
배열을 몇칸 마련? -> 천만칸.
- 꽤나 많은 기억공간을 필요로 함.
- 실제 실행시간은 ? 천만명이 다 나보다 한칸 왼쪽번호를 가진 학생, 한칸 오른쪽 번호를 학생을 살펴봐야하는 문제 발생
여벌의 체육복을 가져온 학생들의 번호(reserve)를 정렬하고
이것을 하나 하나 순서대로 살펴보면서, 여벌 체육복 가져온 학생들만 살펴보면서 빌려줄 수 있는 다른 학생을 찾아서 처리한다.
여벌의 체육복 가져온 학생들을 정렬해야 하기 때문에 -> 이 알고리즘은 O(klogk)일 것이다.
학생 전체의 수 n이나, 학생 여벌의 수 k나 거기서 거기라면, 방금 전의 방법이 더 좋을 것.
하지만 n은 매우 크고, 여벌의 체육복을 가지고온 학생들이 매우 적다면. 이 방법을 택하는 게 좋을 것이다.
빌려줄 수 있는 다른 학생을 찾아서 처리해야 하는데, 체육복을 도난 당해서 한 벌도 가지고 못한 학생을 찾는 것을. 해시를 적용해서 상수시간에 처리할 수 있다.
더 케이스를 나눈다면, 여벌의 체육복을 가지고 온 학생이 많고, 체육복을 도난당한 학생이 적다면. 도난 당한 학생을 정렬해서. 비슷한 식으로 구현할 수 있을 것이다. (이제 구현할 예제와 완전 대칭일 것)

해결방법(2) 예시

reserved에 들어있는 7,5,2,9,6을 오름차순으로 정렬 2,5,6,7,9
체육복을 잃어버린 학생들을 들어있다 라는 것만 알 수 있는 해시테이블을 이용한 구조를 생성
5번과 7번이 잃어버린 학생에도 껴있고, 여벌을 가져온 학생에도 껴있다.
이런 애들은 빼내야 한다
그러고 나서 여벌의 체육복을 가져와서 빌려줄 수 있는 학생들은 2, 6, 9
2번을 가져오고, 1번이 빌려와야 하는 상황인지 -> 그런데 해시에 있기에 꺼내온다.
다음 6번은 5번을 찾는다. 해시에 있지 않아 -> 6번 지나간다. 7번도 마찬가지
다음은 9번을 찾는다. 9번 앞 8번은 해시에 있다 -> 꺼내서 빌려준다.
빌려주기 절차 끝.
이 동작이 방법 1의 동작과 완전히 동일한 동작을 한다.
답은 전체학생 수에서 - 3번, 즉 못 빌린 학생 1명을 뺀다.
알고리즘의 복잡도
여벌의 체육복을 가져온 학생들의 번호를 (reserve)를 정렬 :
- 그 여벌의 체육복을 가져온 학생들의 길이가 k라면 O(klogk)
체육복을 빌려줄 수 있는 학생을 찾아서 처리하는 것. -> O(k) * O(1)
각 단계에서 중요한 점은 빌려줄 수 있는 학생, 내 앞의 번호 혹은 내 뒤의 번호 학생이, 체육복을 빌려야 하는디 아닌지 상수시간에 구현이 가능하다는 점. -> 해시 테이블을 내부적으로 이용하기 때문
전체적으로 알고리즘의 복잡도는 O(K logk)
방법 1이나 방법 2를 택할 때, n이나 k나 비슷한 수준이라면, n이 더 낮은 복잡도를 택해야 하지만,
지금과 같은 방법 2를 적용하는 것이 유리해지는 경우는 n은 매우 크지만 ,k가 그보다 훨씬 작을 때. (klog k )가 n보다 유리한 경우에.

체육복 문제 구현

방법 1 구현

def solution(n, lost, reserve):
    u = [1]*(n+2)  # 앞, 뒤 더미수
    for i in reserve:  # 여벌 증가
        u[i] += 1
    for i in lost:  # 도난 당한 학생수
        u[i] -= 1  # 도난 감소
    for i in range(1, n+1):
        if u[i - 1] == 0 and u[i] == 2:
            u[i - 1: i + 1] = [1, 1]
        elif u[i] == 2 and u[i+1] == 0:
            u[i:i+2] == [1, 1]
        # 만약 더미수를 넣어주지 않았다면, 코드가 길어진다. (바운더리 체크를 해야하는 문제 발생)
    return len([x for x in u[1:-1] if x > 0])

3,4 걸쳐있는 loop -> resever의 길이에 비례. 많아 봐야 n (30명 이하라고 제약)
5,6 걸쳐있는 loop -> 체육복을 도난 당한 학생의 수도 많아봐야 n
7행부터 11행까지에 걸쳐있는 순환문은 정확히 n회 반복한다.
마지막 list comprehension -> 이 한 문장의 복잡도 또한 n에 비례한다.
따라서 전체 알고리즘은 O(n)
코드가 정말 깔끔하다. 내가 과거에 풀었던 코드와 비교해보자.
내 코드

def solution(n, lost, reserve):
    num = [1]*n
    for idx in range(n):
        for i in lost:  # lost에서 하나 꺼내
            if(idx+1 == i):
                num[idx] -= 1
        for i in reserve:  # reserve에서 하나식 꺼내
            if(idx+1 == i):
                num[idx] += 1

    for i in range(1, n):
        if(num[i] == 2 and num[i-1] == 0):
            num[i-1] += 1
            num[i] -= 1
        elif(num[i] == 0 and num[i-1] == 2):
            num[i-1] -= 1
            num[i] += 1

    for i in range(n):
        if (num[i] == 2):
            num[i] = 1
    return sum(num)

더미노드를 둠으로써, 내가 사용했던 조건문을 제거해 줄 수 있었고
파이썬의 값을 교환할 수 있게 지원해주는 연산을 용해서 값 또한 한줄로 처리해줄 수 있었으며
마지막 더미노드를 제외하고 값을 계산해주는 것을 list comprehension을 사용함으로써 더 간단하게 구현이 가능했다.
방법 2
set은 해쉬테이블을 이용해서 구현되어 있기 때문에 key를 접근하는데 드는 시간이 상수시간이다.
그런데, 사전과 다른 점은 dictionary는 키에 대해서 value가 mapping되어 있지만, set은 value는 없고 어떤 원소가 이 집합에 속해 있는지 아닌지만을 상관하는 자료구조다.
s = set(lost) & set(reserve) &는 집합에서 이 두 집합의 교집합을 뜻한다.
이후 l = set(lost)-s를 해준다.
s에는 체육복을 도난 당한 학생인데, reserve에도 들어있어서, 체육복이 하나 남았으니까. 빌릴 필요가 없는 학생이 담겨있다. 그걸 set(lost)에서 빼줘서 l에 담으면 체육복을 빌려줘야만 하는 학생들만이 담긴다.
r = set(reserve) - s 여기서 r은 여벌의 체육복을 가져왔는데, 도난은 당하지 않은 즉 빌려줄 수 있는 학생들만 담긴다.
빌려줄 수 있는 학생들을 정렬해야 한다.

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    for x in sorted(r):  # sorted: r에 들어가 있는 집합을 정렬한 리스트를 반환
        if x - 1 in l:
            l.remove(x-1) # remove는 리스트에서 매개변수로 들어온 값을 통해서 삭제
        elif x + 1 in l:
            l.remove(x+1)
    return n-len(l)
print(solution(5, [2, 4], [1, 3, 5]))

set을 이용해서, 체육복을 빌려줄 수 있는, 빌려야 하는 학생들을 담아서 정렬.
하나 앞선 번호의 학생이 빌려야 하면 빌려준 걸로 치고,
그렇지 않고 나서 하나 뒤의 번호를 학생이 l에 있다면, 그 뒤 학생을 지워주는.
이 조건의 순서는 매우 중요. 번호의 오름차순으로 정렬했기 때문에, 이 경우 탐욕법을 적용하려면,
먼저 나보다 하나 작은 학생을 먼저 살펴보고, 그 학생에게 빌려줄 수 없는 경우에 대해서 그 이후에 체크해야 한다.
sorted(r)에 의해서 r의 길이가 k라면 (klog k)가 든다.
사실 주어진 리스트에서 set을 만드는데, 연산이 필요하다.
set을 구성하는 배열의 길이에 비례한다.

참고자료 [프로그래머스]https://programmers.co.kr/learn/courses/9877

2. 탐욕법 대표 문제 풀이 : 체육복

입출력 예

문제의 해결 - 예제

탐욕법 (Greedy Algorithm)

탐욕법 적용 가능성 확인

문제 해결방법 (1)

알고리즘의 복잡도

문제 해결방법(2)

해결방법(2) 예시

체육복 문제 구현