본문 바로가기

코딩/코드트리

[코드트리 챌린지] 2주차 - 동적계획법(DP)

2주차 실력진단 결과😍

 

 

처음보다 코드트리로 경로문제, 완전탐색 문제를 공부하고 난 후에 굉장히 많이 뛴 것을 확인🎵

 

이번주 실력진단에서 막힌 부분은 DP, 동적계획법부분이다.

처음 알고리즘을 공부할때 DP 개념이 막연해서 문제를 완전 탐색으로 주로 풀었는데

당연하게도 시간 초과, 메모리 초과 문제를 피할 수 없었다😥

 

 

https://www.codetree.ai/landing/level-test/5814/result/4?&utm_source=clipboard&utm_medium=text 

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

 

이 문제는 격자 안에서 한 칸씩 전진하는 DP 유형의 문제이다.

Sol 1

완전 탐색으로 풀 경우 특정 칸에 도달할 때 숫자의 합이 경로마다 다르게 나타난다.

하지만 DP로 생각하면 특정 칸에 도달할 때 나올 수 있는 최대 숫자를 미리 알고 있다고 생각한다 

" 작은 문제가 먼저 풀려있다는 가정"

이를 통해 불필요한 탐색을 막을 수 있고, 시간과 메모리를 단축시킬 수 있다.

 

Sol 2

초기에 확실하게 채워줄 수 있는 부분, 초기 조건을 채우고 점화식을 생각해본다.

 

이를 토대로 생각해낸 답안은 다음과 같다.

 

 

 

n = int(input())
grid = []
for _ in range(n) :
    grid.append(list(map(int, input().split())))

def initialize() :
    for j in range(1, n) :
        grid[0][j] += grid[0][j-1]
        grid[j][0] += grid[j-1][0]

initialize()

for i in range(1, n) :
    for j in range(1, n):
        grid[i][j] += max(grid[i-1][j], grid[i][j-1])

print(grid[n-1][n-1])

 

 

1열과 1행은 무조건 한 방향으로 계속 갔을 때 도달하는 경우 밖에 없으므로 초기조건에 해당한다.

이를 initialize 함수를 사용하여 계산해주었다.

 

남은 셀들은 왼쪽에 있는 셀과 위쪽에 있는 셀 중 큰 값을 더해 채워준다

이는 작은 문제가 먼저 풀려있다는 가정을 이용하는 것이다.

 

 

 

 

 

 

그 결과 깔끔하게 해결👌

 

실력진단도 했으니까 다음주에는 열심히 문제 풀기

(젭알 ㅎㅎ)