출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 31, p 375 이전에 풀이한 등굣길 문제와 유사하게 다이나믹 프로그래밍(DP)을 사용해 풀이했습니다. 입력으로 받은 금광에서 1열의 값은 그대로 두고, 2열부터 마지막 열까지 다음을 반복합니다. 첫 행의 경우 현재 위치를 왼쪽, 왼쪽 아래에서부터 접근해올 수 있습니다. 왼쪽 위는 금광이 존재하지 않습니다. 마지막 행의 경우 현재 위치를 왼쪽, 왼쪽 위에서부터 접근해올 수 있습니다. 왼쪽 아래는 금광이 존재하지 않습니다. 중간 행의 경우 현재 위치를 왼쪽, 왼쪽 위, 왼쪽 아래 모두에서 접근해올 수 있습니다. 접근해올 수 있는 모든 값들 중 최댓값을 현재 금광에서 얻을 수 있는 값과 더해줍니다. 마지막으로 마지막 열의 모든 값들 중 최댓값을..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr town이라는 딕셔너리를 정의하고, key에는 각 위치의 좌표, value에는 각 위치에 도달하기까지 가능한 모든 경우의 수를 저장했습니다. 오른쪽과 아래쪽으로만 움직일 수 있기 때문에 현재 위치의 왼쪽과 위쪽의 값을 더해 현재 위치의 값을 갱신했습니다. 이때 왼쪽이나 위쪽에 길이 없어 index Error가 날 수 있는 곳은 길이 없는 곳은 제외하고..

programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 💡 Dynamic Programming으로 풀이했습니다. 먼저 주어진 land과 같은 shape의 dp라는 리스트를 생성합니다. 이때 모든 값은 0으로 초기화합니다. dp의 두 번째 줄부터, 각 위치에 도달할 때까지의 최댓값을 dp에 저장합니다. 이때 연속해서 같은 열은 방문할 수 없게 해줍니다. cf. dp의 첫 번째 줄에선 아직까지 더해온 값이 없어 그..

programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 💡 Dynamic Programming으로 풀이했습니다. 먼저 주어진 triangle과 같은 shape의 dp라는 리스트를 생성합니다. 이때 모든 값은 0으로 초기화합니다. dp의 두 번째 줄부터, 각 위치에 도달할 때까지의 최댓값을 dp에 저장합니다. cf. dp의 첫 번째 줄에선 아직까지 더해온 값이 없어 그대로 0이므로 고려하지 않아도 됩니다. dp의 마지막 줄에 다다를 때까지 이를 반복하고, 마지막 줄에 도달하면 while문을 종료합니다. 여기..