[파이썬 코테 대비 동아리]개념을 공부하자_"그리디"편

그리디

그리디 ?

: Greedy ( 탐욕 ) . 닉값하는 알고리즘이다

다른 건 다 모르겠고 현재 동작하는 곳 에서 최선의 선택을 하는 기법이다.

최적해를 구하는 데에 사용되는 근사적인 방법이다.

그리디를 적용하기 위한 2가지 조건

: 1. 탐욕적 선택 조건 / 2. 최적 부분 구조 조건 / 3. 상위 값 하위 값 배수 조건 < 이 세 가지를 만족 해야한다.

탐욕적 선택 속성이란, 앞의 선택이 이후의 선택에 영향을 주지 않는다는 조건이며 , 그리디한 선택이 항상 최적해를 보장해야 한다는 것이다.

최적 부분 구조 조건은, 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다는 것이다. 한마디로 그리디 알고리즘으로 풀어낸 해는 모든 경우의 수에서 최적이어야 한다.

또한 주어진 상위 값이 하위 값이 하위 값의 배수여야 한다.

그리디 알고리즘을 사용하는 이유 ?

: 빠르다.

그리디 알고리즘이 최적해를 찾지 못하는 경우 동적 프로그래밍(DP)로 해결할 수 있는데 이는 그리디 알고리즘보다 훨씬 느리므로, 그리디가 가능하다면 그리디를 쓰는 게 낫다.

근사치를 짐작 가능하다.

만약 이득을 못 봐도 어느 정도 근사치를 구할 수 있는데, 이처럼 근사치를 구하는 알고리즘을 근사 알고리즘이라고 한다.

결론은 그리디로 풀리면 동적 프로그래밍보다 훨씬 이득이며, 아니어도 근사치 짐작이 가능하다.

코딩 테스트에서는 항상 최적해 성립 조건 2가지를 만족하는 문제만 나온다 한단다.

그리디 알고리즘을 활용할 수 있는 예시 문제

1. [ 구명보트 ]

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

people limit return

[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

def solution(people, limit):
    people.sort()
    answer = 0

    left = 0
    right = len(people)-1
    while left <= right:

        if people[left] + people[right] <= limit:
            left += 1
            right -= 1
        else:
            right -= 1

        answer += 1

    return answer

1. [큰 수 만들기]

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number k return

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

나...중에......ㅋ.

1. [섬 연결하기]

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n costs return

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

나...중에.....

1. 단속카[메라]

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routes return

[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

2

입출력 예 설명

• 5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
• 15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.