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 함수를 사용하여 계산해주었다.
남은 셀들은 왼쪽에 있는 셀과 위쪽에 있는 셀 중 큰 값을 더해 채워준다
이는 작은 문제가 먼저 풀려있다는 가정을 이용하는 것이다.

그 결과 깔끔하게 해결👌
실력진단도 했으니까 다음주에는 열심히 문제 풀기
(젭알 ㅎㅎ)
'코딩 > 코드트리' 카테고리의 다른 글
[코드트리 챌린지] 8주차 - 동적계획법(DP)3 (1) | 2023.10.29 |
---|---|
[코드트리 챌린지] 6주차 - 동적계획법(DP)2 (2) | 2023.10.16 |