Swift) 탐욕법 (Greedy Algorithm) + 프로그래머스 체육복 풀이

 

 

 

안녕하세요 :) 소들입니다!

으으.. 알고리즘 이론 공부도 점점 끝이 보여 가네요!!!

물론 이론만 끝이지 실제 문제풀이 해봐야 하는 게 20배는 더 많지만..ㅎ

 

요즘 Swift 포스팅을 못해서 마음 한 켠이 찝찝한데..

다음 주 부턴 Swift & iOS 포스팅이 더 많이 올라올 것 같아요 😇

알고리즘 포스팅은 재밌지만 조회수가 많이 안 나온다^^;;

 

이번엔 이름도 무시무시한 탐욕법에 대해 공부해볼 거예요!

그리디 알고리즘이라고 하는데, 딱히 막 트리, DP 같이 정해진 알고리즘은 아니라...

이번엔 프로그래머스에서 탐욕법 Lv.1에 해당하는 쉬운 체육복이란 문제로 이해해보려고 합니다 :)

(제가 푼 게 정답은 아니겠지만..!?)

 

그럼 간단하게 공부해볼게요!!!!

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 탐욕법(Greedy Algorithm)이란?

 

매 순간 최적의 해라고 생각되는 것을 선택해 나가는 방식으로, 최종적인 해답에 도달한다

이때, 탐욕 선택 조건은 앞으 선택이 이후에 선택에 영향을 주면 안 되며,

문제에 대한 최적해가 부분 문제에 대해서도 최적해여야만 최적해를 구할 수 있다

 

탐욕 법의 정의는 위와 같은데.... 이름이 탐욕 알고리즘이잖음..? 욕심쟁이란 말임

미래의 나는 생각 안 하고, 그냥 당장 내 눈 앞에 있는 최고를 취하는 것임ㅎ

따라서 만약 다음과 같은 트리가 있을 때

 

 

 

 

 Leaf 노드까지 가는데 가장 큰 값을 구해야 한다면,

탐욕 알고리즘이란 뭐다? 매 순간 최적의 해를 선택한다!!!! 

지금 당장 1의 눈 앞에 있는 10과 20을 비교해서

 

 

 

 

더 큰 값인 20이 최적해이므로 선택하는 것임

이제 또 20의 눈 앞에 있는 1과 12를 비교해서

 

 

 

 

더 큰 값인 12이 최적해이므로 선택하는 것임:)

만약 DP로 구현 했다면, 모든 노드에 대해 나눠서 탐색을 진행 했어야 했을 거니까

이럴 경우엔 탐욕 알고리즘을 사용하는 것이 DP를 사용하는 것보다 훨 효율적임!!!

 

근데 이렇게 부분 최적해를 구한 것이

전체 최적해가 되는 경우에만 탐욕 알고리즘을 사용할 수 있음!!!

 

그럼 아닌 경우에 사용하면 어떻게 될까?

 

 

 

 

2. 탐욕 알고리즘의 한계

 

탐욕 알고리즘의 한계는 반드시 최적의 해를 구할 수 있는 것이 아니란 것임

최적의 해에 가까운 값을 구하는 방법 중 하나라 근사치 추정에 활용될 수 있음

 

만약 다음과 같은 트리가 있을 때 탐욕 알고리즘을 적용 한다면

 

 

 

 

이런 경우엔 부분 최적해로 구한 탐욕법의 최적해가 전체 최적해가 아니기 때문에

(1->15->30 으로 가는 게 전체 최적해)

탐욕 알고리즘은 바이바이....! 이런 한계가 있음 :)

 

 

 

 

3. 프로그래머스 탐욕법 :: 체육복 문제 풀이

 

음... 그리디 알고리즘을 공부하고나서 너무 간단한 거 같은데 감은 잘 안와서..

프로그래머스에서 가장 쉽다는 Lv.1의 탐욕법 문제를 풀어보았음..!

(알고리즘 이론 공부 후엔 쉬운 문제부터 풀어서 자신감을 얻자 :))

 

programmers.co.kr/learn/courses/30/lessons/42862

 

 

 

3-1. 문제 설명

 

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

 

 

 

3-2. 제한 사항

 

- 전체 학생의 수는 2명 이상 30명 이하입니다.

- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.

- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.

- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.

- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

 

 

여러분.. 문제는 정말 꼼꼼히 읽는 버릇이 필요한 거 같아요.. =_=

저 아무 생각 없이 흘려 읽었다가 마지막 제한 사항 안 읽어서 왜 틀린 거지;;하면서 5분인가 헤맴;;

여기서 여벌 체육복을 가져온 학생이 체육복을 도난당했을 경우를 꼭 생각 합시다 :)

 

 

 

3-3. 문제 풀이

 

처음에 이게 왜 그리디 문제인가....했는데 Lv.1인 만큼 정말 간단하게 생각하면 풀 수 있는 것 같음..

그리디 자체가 어떤 특정한 알고리즘이 아닌 만큼,

아무 생각 없이 푸는 것이 그리디가 되는 경우랄까..? 👀 쨌든

 

여벌 체육복이 있는 학생(reserve)은 무조건 내 앞 번호 학생(reserve - 1)에게 빌려준다!

만약 내 앞 번호 학생이 체육복이 있으면(lost에 없으면), 내 뒷 번호 학생(reserve + 1)에게 빌려준다!

내 뒷 번호 학생(reserve + 1)도 체육복이 있으면 안 빌려주면 된다!

 

이렇게 간단하게 최적해를 생각해보는 것임 ㅎㅎ

무조건 앞놈부터 빌려주고~ 없으면 뒷놈주고~!!

 

그리고 제한 사항에서 lost, reserve는 각각 중복되는 학생이 없으니 Set으로 선언하고,

 여벌 체육복을 가져온 학생이 체육복을 또 도난당했을 경우, 남에게 빌려주지 못한다고 했으니,

 lost와 reserve을 각각 substracting(차집합)으로 빼주면 되는 것임!!

 

 

따라서 코드는

 

 

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var lostSet = Set(lost).subtracting(reserve)
    let reserveSet = Set(reserve).subtracting(lost)
    
    for reserve in reserveSet {
        if lostSet.contains(reserve - 1) {      // 내 앞 번호 학생이 체육복이 없는지 확인
            lostSet.remove(reserve - 1)
            continue
        }
        if lostSet.contains(reserve + 1) {      // 내 뒷 번호 학생이 체육복이 없는지 확인
            lostSet.remove(reserve + 1)
        }
    }
    return (n - lostSet.count)
}

 

 

이렇게 간단하게 짤 수 있음 :) 제 코드가 정답은 아닙니다!

 

 

 

 

 

 

 

 

 

 

 

.

.

.

정말 간단한 탐욕 포스팅 끝!

혹시 피드백, 이해 안 가시는 점은 언제든 댓글 남겨주세요~~