Pori_IT

오늘의 학습 키워드:  그래프, 해시

문제: 대충 만든 자판

https://school.programmers.co.kr/learn/courses/30/lessons/160586

풀이

각 버튼이 최소로 눌리는 수를 해시값에 넣어두고 그 값보다 최소가 되는 경우에 값을 변경해주면서 각 버튼의 최소로 눌리는 횟수를 계산합니다.

def solution(keymap, targets):
    answer = []
    dict1={}
    for i in keymap:
        for j in range(len(i)):
            if i[j] not in dict1:
                dict1[i[j]] = j+1
            elif dict1[i[j]] > j+1:
                dict1[i[j]] = j+1

    for i in targets:
        tmp = 0
        for j in i:
            if j not in dict1:
                tmp = -1
                break   
            else:
                tmp+=dict1[j]
        answer.append(tmp)
    return answer

오늘의 학습 키워드:  그리디

문제: 마법의 엘리베이터

https://school.programmers.co.kr/learn/courses/30/lessons/148653

풀이

이번 풀이는 다음을 참고해서 진행했습니다.

https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Programmers-%EB%A7%88%EB%B2%95%EC%9D%98-%EC%97%98%EB%A6%AC%EB%B2%A0%EC%9D%B4%ED%84%B0-Python

각 자리의 값에 따른 돌의 사용 횟수를 계산할 때 다음 값에서 빼야 하는 경우 (16 -> 20 -4)에 대한 구현이 가장 어려웠습니다.

위의 포스팅에 나온 풀이를 보며 조금 편하게 이를 계산하는 방법을 참고했습니다.

전체 코드는 블로그를 참고해 주시고 제가 부족했던 부분만 가져왔습니다.

def solution(storey):
    answer = 0

    while storey:
        remainder = storey % 10
        ...
        storey //= 10

    return answer

이런 식으로 가장 뒷자리(1의 자리)를 소거하면서 진행하는 방법을 사용합니다. (2554 > 255 > 25 > 2)

오늘의 학습 키워드:  DP

문제: 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

풀이

이번에도 DP문제가 나왔습니다.

칸에 도달하는 방법은 두 가지 방법이 있습니다.

1. 한 칸 뛰기

2. 두칸 뛰기

따라서 따져보아야할 가짓수는 한 칸 전의 값, 두 칸 전의 값입니다..

도달 가능한 수의 합은 앞의 두칸의 합과 동일하게 됩니다. (피보나치..?)

코드로 구현해보면 아래와 같습니다.

def solution(n):
    jump = [0 for _ in range(n)]
    
    for i in range(n):
        if i == 0:
            jump[i] = 1
        elif i == 1:
            jump[i] = 2
        else:
            jump[i] = jump[i-1]+jump[i-2]
    
    return jump[-1]%1234567

오늘의 학습 키워드:  DP

문제: 피보나치 수

https://school.programmers.co.kr/learn/courses/30/lessons/12945

풀이

작은 문제로 분할해서 푸는 DP 문제입니다. 기초문제이기에 그렇게 어렵지 않았습니다.

앞의 두 값을 더해서 다음 수를 계산하는 방법입니다. 이를 위해 리스트를 만들고 값들을 저장하면서 풀이를 이어갔습니다.

bottom-up 방식으로 진행했습니다.

def solution(n):
    dp=[0,1]
    n+=1
    while len(dp)<n:
        dp.append(dp[-2]+dp[-1])
    return dp[-1]%1234567