03. 그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

이코테 문제 풀이

3-1. 거스름돈

---

n = int(input())
money = [500, 100, 50, 10]
cnt=0

for c in money:
    cnt+=n//c #몫 - 동전갯수
    n%=c
print(cnt)

내림차순 정렬로 문제를 풀었으나 반례로 10원짜리만 모두 거슬러 줄 수 있도록 한다면 고려해보기.

3-2. 큰 수의 법칙

---

문제자체는 어렵지 않은데... 구현에서 막혀버림 롸.
내림차순 하여 가장 큰값 1,2만 3번씩 곱해주면 되는데 어떤 기준으로 바꿀것인지 이중 while문을 시도해봄=>안됨

while True로 둠으로써 무한반복을 하여 3번씩 가장 큰 수 더하고 다음 큰수 한번 더하는 로직 기억하기...

• 방법1

def solution(num, m, k):
    answer=0
    num.sort(reverse=True)

    while True:
        for i in range(k):
            if m==0:
                break
            answer += num[0]
            m-=1
        if m == 0:
            break
        answer += num[1]
        m-=1
    return answer

print(solution([2,4,5,4,6],8, 3))

• 방법2

n,m, k = map(int, input().split())
num = list(map(int, input().split()))
num.sort(reverse=True)

cnt = m//(k+1)*k
cnt += m%(k+1)
answer = 0
answer += cnt * num[0]
answer += (m-cnt)*num[1]
print(answer)

반복되는 수열을 활용해서 계산 하는 방법

3-3. 숫자 카드 게임

---

max, min 비교할때 보통 2147000000같은 큰수나 작은수를 두는데 이번 문제에서 위의 2147000000값으로 초기화 했다가 어떻게 하지 고민했다
결과적으로 max값을 구하기 때문에 -21470000으로 초기화 시켰어야함

def solution(num):
    answer=-2147000000
    for i in num:
        min_num = min(i)
        answer = max(answer, min_num)
    return answer

print(solution([[7,3,1,8],[3,3,3,4]]))

3-4. 1이 될때까지

책보다 코드를 짧게 짰는데 테케가 더 많았으면 하는 아쉬움이 있다

def solution(n, k):
    answer=0
    while n != 1:
        if n % k == 0:
            n = n // k
            answer += 1
        else:
            n = n - 1
            answer += 1

    return answer
print(solution(25, 5))

추가문제

---

버스

• 내코드
  시간복잡도: NlogN

def solution(weight, limit):
    weight.sort()
    answer=0
    bus=0
    for x in weight:
        bus += x 
        if bus<limit:
            answer+=1 
        else:
            return answer
    return answer

print(solution([300, 100, 230, 120, 90, 150, 60], 700))
print(solution([50, 90, 70, 120, 300, 200, 150, 180, 190], 1000))
print(solution([70, 90, 100, 80, 60, 75, 73, 85, 120, 110, 200], 800))
print(solution([50, 90, 100, 130, 140, 120, 130, 120, 150, 160, 140, 170], 1000))
print(solution([100, 110, 50, 50, 60, 70, 50, 55, 57], 350))

값이 자꾸 +1인채로 나와서 고민을 했음 먼저 더하고 조건 여부를 따져서 값을 증가시키니 정답이 나왔다.

• 정답코드

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

    for x in weight:
        if bus+x > limit: #1. 먼저 가능한지 여부 확인 
            break
        bus+=x #2. 값을 더함
        answer+=1

    return answer

가능한지 여부를 먼저 파악 후 실행을 함 (내코드와 정반대)
불필요한 코드가 없음. 해당 방식을 생각하도록 하자

최대 사과의 개수

• 내코드

def solution(box, limit):
    answer = 0
    box.sort( key=lambda b:-b[1]) #value[1]를 내림차순 정렬
    cnt=0

    for idx, value in box:
        if cnt+idx > limit:
            limit -= cnt 
            answer += limit * value
            break
            
        cnt +=idx
        answer += idx*value
    return answer
    
print(solution([[2, 20], [2, 10], [3, 15], [2, 30]], 5))
print(solution([[1, 50], [2, 20], [3, 30], [2, 31], [5, 25]], 10))
print(solution([[3, 40], [5, 20], [5, 70], [1, 80], [5, 30], [3, 35]], 15))
print(solution([[2, 70], [5, 100], [3, 90], [1, 95]], 8))
print(solution([[80, 20], [50, 10], [70, 15], [70, 30], [80, 70], [90, 88], [70, 75]], 500))

이번엔 반대로 남은 값을 어떻게 포함시켜 더할것이냐가 관건이었는데 위의 문제 코드를 응용해서 남은 limit값 만큼 value를 더하도록 했음

• 책코드

def solution(box, limit):
    answer = 0
    box.sort( key=lambda b:-b[1]) 
    
    for x in box:
        cnt = min(limit, x[0]) #if조건문 대신, 최솟값을 넣음으로서 limit보다 작은값만 계산하도록 만듬 
        limit -= cnt
        answer += cnt * x[1]
        
        if limit == 0:  #종료 조건
            break
    return answer

if cnt+idx > limit 조건문 부분을 최솟값으로 분류 함으로서 코드가 더 간결하고 효율적임
이경우 나는 while문을 생각해서 줄여나가는데 min을 사용한 방식도 기억해두자.

선긋기

아이디어를 생각하지 못함, 앞부분 설명을 봐도 구현부분을 감잡지 못했음

start(시작점), end(끝점), i(현재점), m(구하고자 하는 값)
1. 시작점이 작은 순서부터 정렬 (오름차순 정렬)
2. 시작점에서 가장 큰값의 끝점을 찾기
3. 해당 끝점을 '시작점'으로 변경후 또 가장 큰 값의 끝점을 찾기
	= 겹쳐있는 선
    = 끝점 이하의 선
    = 변경된 '시작점' 이하의 선

def solution(m, nums):
    answer = 0
    n = len(nums)
    nums.sort(key=lambda v:v[0])
    start=end=i=0

    while i<n:
        while i<n and nums[i][0]<=start:
            end = max(end, nums[i][1]) #기존의 선 vs 새로운 선
            i +=1 #현재값 증가
        answer +=1 #while 끝난 후 선긋기 종료임으로 1증가

        if end ==m: #종료 조건
            return answer
        start = end
    return answer


print(solution(12, [[5, 10], [1, 8], [0, 2], [0, 3], [2, 5], [2, 6], [10, 12], [7, 12]]))
print(solution(15, [[1, 10], [0, 8], [0, 7], [0, 10], [12, 5], [0, 12], [8, 15], [5, 14]]))
print(solution(20, [[3, 7], [5, 8], [15, 20], [0, 5], [7, 14], [3, 10], [0, 8], [13, 18], [5, 9]]))
print(solution(30, [[5, 7], [3, 9], [2, 7], [0, 1], [0, 2], [0, 3], [19, 30], [8, 15], [7, 12], [13, 20]]))
print(solution(25, [[10, 15], [15, 20], [5, 15], [3, 16], [0, 5], [0, 3], [12, 25]]))

카드점수

문제이해를 제대로 못했음 양끝에서 한번씩 비교하여 최댓값을 구하는 줄 알았는데
접근을 양끝에서 할수있고 여기서 최댓값을 구하는 방식이었다.

• 방식1

def solution(nums, k):
    answer= 0
    n= len(nums) #7
    for i in range(k+1): #0-7 1
        sumN=0
        """
        좌, 우로 각각의 for문을 생성
        - 좌: 앞 ~ 현재위치(i)까지 합
        - 우: [전체횟수(n) - 주어진횟수(k) + 현재위치(i)] ~ 끝위치까지
        """
        for j in range(i): # 1
            sumN += nums[j]
        for j in range(n-k+i, n): # 7-4+1 (4-6)
            sumN += nums[j]
        print(sumN)

    return answer