2022. 02. 08 모각코 6번째 모임

지난주 화요일 설연휴로 한주 쉬고 이번주에 마지막 모임을 가졌다. 13단계는 수정예정이라 아무문제도 없었고 14단계는 저번주동안 풀었기에 오늘은 15단계 동적 계획법 1의 5문제를 풀고자 한다.

 

동적계획법이란 처음 진행되는 연산은 기록하고 이미 진행했던 연산이라면 기록되어있는 것을 가져와 사용하는 방식이다. 피보나치수열이 대표적이라고 할 수 있다. 피보나치수열을 재귀로도 사용할 수 있지만 재귀에서 생기는 중복되는 연산이 동적계획법으로 보완할 수 있다는 점이 장점이다.

 

1463번의 메모이제이션이라는 단어는 한번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복계산을 줄이는 것을 말하는데 동적계획법의 핵심이 되는 기술이라고 한다.

 

오늘은 1463을 리뷰하며 활동을 마무리하고자 한다.

 

이 문제는 예를 들어 x가 10인 경우 10, 9, 3, 1의 과정을 거쳐 1이 되고 9인 경우 9, 3, 1, 3인경우 3, 1 이런식이다. 즉 10을 구할때 9의 결과를 가져와 사용할 수 있다는 것이다. 이렇게 이전의 결과값을 저장해서 사용하는 동적계획법을 사용하여 풀게 된다.

 

우선 2와 3으로 나누어 떨어지지 않는다면 1을 빼고 dp[i]에 1을 추가 해준다. 그 후 2와 3으로 나누어 떨어질 경우는 그저 1을 빼는 것이 아니라 나눠서 나오는 값을 사용하여야 하므로 min값을 dp[i]에 저장해주면 된다. 이런 방식으로 dp[n]을 구하여 출력해주었다.

 

 

오늘은 마지막 모각코날이라 조원들과 지금까지의 활동들에 대해서 이야기를 나누었다. 학교수업만하고 아직까지도 코딩습관이 제대로 잡혀져있지않은 나였기에 이번 모각코 활동은 굉장히 의미있는 시간이었다. 매주 정해진 날짜, 정해진 시간동안 목표한 양의 코드를 작성하며 코딩습관을 기를 수 있었다. 앞으로도 매주 한단계씩 문제를 풀고 해당 알고리즘을 공부하며 이 습관을 지켜나갈 수 있도록 노력할 것이다.