오늘의 학습 키워드

그리디

• ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘

그리디 vs DP

DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면 , 그리디는 각 단계마다 지역 최적해를 찾는 문제로, 문제를 더 작게 줄여나가는 형태다.

이미지 출처

공부한 내용 본인의 언어로 정리하기

프로그래머스 마법의 엘리베이터

• 엘리베이터 버튼은 10^c(c>=0)
• 0층이 가장 아래층
• 버튼 한 번당 마법의 돌 한 개
• 현재 엘리베이터가 있는 층수가 주어졌을 때 필요한 마법의 돌돌의 최솟값

어떤 문제가 있었고, 나는 어떤 시도를 했는지

def solution(storey):
    answer = 0
    while storey > 0:
        rem = storey % 10
        offset = 10 - rem
        storey //= 10
        if (rem > 5 ) or (rem == 5 and storey %10 >= 5) :
            answer += offset
            storey += 1
        else:
            answer += rem
    return answer

• 문제를 어떻게 풀지 감이 오지 않아서, 다른 풀이를 통해 5가 기준점이 된다는 힌트를 얻었다

• 각 자리수를 하나씩 가져와 5를 기준으로 조건문을 적용하였다

• 5보다 작은 경우 - 내려가는 가기

• 5보다 큰 경우 - 올라가기

• 5인 경우, 다음 자리수도 5이상이면 올라가기

? 그러면 5인 경우 다른 자릿수가 5보다 작은경우?
예를 들어 2352인 경우에는, 모든 자릿수가 else 문으로 저리가 되어서 총 12가 된다

다른 사람의 풀이

def solution(storey):
    answer = 0
    x = list(str(storey))
    x = [int(floor) for floor in x]
    x.reverse()

    for i in range(len(x)):
        if x[i] < 5:
            answer += x[i]
        elif x[i] == 5:
            answer += 5
            if i+1 < len(x) and x[i+1] >= 5:
                x[i+1] += 1 
        else: 
            answer += 10 - x[i]
            if i+1 < len(x):
                x[i+1] += 1
            else: answer += 1

    return answer

• 로직을 가장 잘 짠 코드이다
• 우선 list 로 바꾸고, 하나씩 가져올 수 있도록 하였다
• for 반복문으로 적용해 ,5를 기준으로 3가지 케이스를 다 세부적으로 구현하였다
• 또한 반복문마다 len(x) 와 다음 자리수를 비교하는 부분을 넣어 범위를 벗어나지 않도록 한것도 인상적이다

무엇을 새롭게 알았는지

• 키워드가 없으면, 아직 해당 문제가 어떤 알고리즘 문제인지 구별하는 것이 어려운 것 같다

학습할 것은 무엇인지

• 그리디 알고리즘 문제를 더 풀어봐할 것 같다