[코드트리 챌린지] 8주차 (10/25-10/30), dp

 

코드트리 챌린지 마지막주를 가파른 상승곡선으로 마무리하게 되어서 너무 기분이 좋다^.^

 

마지막으로 푼 문제가 저저번주에 못 푼 문제 유형이어서 살짝 떨리는 마음으로 풀었는데, 저번에 못 풀었던 원인을 찾은 것 같아서 풀면서도 기분이 좋았다.

 

로직의 순서를 바꿔서 풀면서 일부 테스트케이스에서 틀리게 나오게 됐던 것 같다.

그래서 로직을 다시 바꿔보니 이번 문제가 해결되는 것을 볼 수 있었다.

 

역시 저번주의 후퇴는 두발전진을 위한 발돋움이었나..?호호

 

 

 

 

오늘 평가를 하고 나니 dp에 대한 학습이 필요하다는 코멘트가 나오게 됐다.

dp도 항상 코테에서 필수 문제로 나오는 유형이었는데 이번 기회에 공부할 수 있어서 너무 좋았다.

그래서 바로 호다닥 개념 공부를 시작했다.

네카라 코테는 쉽지 않구나..

DP (Dynamic Programming)

큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법

 

일단, DP는 점화식을 찾아내는 것이 중요하다

 

풀었던 문제

#계단 오르기

이 문제는 dp를 이해하기에 딱 좋은 문제인 것 같아서 고르게 되었다.

n층 높이의 계단을 오르려고 합니다. 한 번에 정확히 2계단 혹은 3계단 단위로만 올라갈 수 있다고 했을 때, n층 높이의 계단에 올라가기 위한 서로 다른 방법의 수를 구하는 프로그램을 작성해보세요. 단, 항상 2계단 혹은 3계단 단위로만 올라갈 수 있기에 n층까지 정확히 1계단이 남은 상황에서는 n층으로 올라갈 수 있는 방법이 전혀 없음에 유의합니다.

해당 번째 층에 도달하기 위해서는

1) 2계단씩 오르거나

2) 3계단씩 오르기

따라서 점화식은 dp[i] = dp[i - 2] + dp[i - 3]

dp[i-2]는 2계단 전, dp[i-3]은 3계단 전으로 생각하면 된다.

이 점화식으로 계산하면 n층까지 올라가는 방법을 알 수 있다.

이 점화식을 이용해서 작성한 코드가 아래 코드이다.

MAX_N = 1000
MOD = 10007

# 변수 선언 및 입력:
n = int(input())
dp = [0] * (MAX_N + 1)

# 초기 조건 설정
dp[0] = 1
dp[1] = 0
dp[2] = 1
dp[3] = 1

# 점화식에 따라 dp값 채우기
# dp[i] = dp[i - 2] + dp[i - 3]
for i in range(4, n + 1):
    dp[i] = (dp[i - 2] + dp[i - 3]) % MOD

print(dp[n])

 

 

챌린지 후기

개발자 준비를 한다면 놓을 수 없는 코테를 코드트리 챌린지로 함께 하면서 너무 좋았다.

그 전에도 공부를 안한 건 아니지만, 뭔가 제대로 하고있는지 뭐부터 공부해야하는지 고민이 많았는데 코드트리는 그런 고민을 하던 나에게 길을 내주고 공부하면 할 수 있다는 자신감을 주었다. 

챌린지 덕분에 좀 더 습관화할 수 있었고, 무작정 하기 싫어했던 코테 문제 풀기를 재밌게 할 수 있게 됐다

챌린지가 끝나고도 앞으로 계속 알고리즘 공부하면서 문제를 꾸준히 풀어야겠다

네카라 코테는 쉽지 않구나..

이 테스트 결과가 말하길 이렇게 공부하면 저때되면 코테 마스터가 되어있겠다고 하니까~ 열심히 꾸준히! 공부해야겠다!