개발자가 되고 싶은 준개발자

풀이 작은 문제의 계산 결과를 재사용하여 큰 문제의 결과를 구할 수 있으므로 동적 프로그래밍을 이용하여 풀 수 있다. 특정 날짜에서 받을 수 있는 비용의 최댓값은 그 이전 날짜 중에서 받을 수 있는 비용의 최댓값에 현재 날짜의 비용을 더한 값이 될 수 있다. 단 주의해야 할 점은 '상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.'라는 제약사항을 고려해야 한다. 따라서 특정 날짜에서 받을 수 있는 비용의 최댓값을 구하기 위해서는 이전 날짜 중에서 최댓값을 더하되, 이전 날짜의 상담이 특정 날짜에는 종료되어 있어야 한다. 코드 import sys # 입력 읽기 n = int(sys.stdin.readline()) t, p, dp = [0 for _ in range(n)..

문제 문자열이 주어지면 이를 키를 이용하여 해독하는 방법의 수를 리턴하는 문제이다. 해독하기 위한 키는 다음과 같다. 'A' -> 1 'B' -> 2 ... 'Z' -> 26 예) "12"는 "AB"나 "L"로 해독될 수 있다. (2가지 방법) "123"은 "ABC"나 "LC"나 "AW"로 해독될 수 있다. (3가지 방법) 풀이 이번 코드는 길이는 짧으나 직관적이지는 않은 것 같다. (더 좋은 방법이 떠오르면 추후에 수정해야 겠다!) 주어진 문자열을 순회하면서 1) 해당 인덱스(i)의 숫자가 1~9의 숫자인지 확인한다. 맞다면 i까지의 방법 개수는 i-1까지의 방법 개수와 같다. (이 문장이 이해가 가지 않는다면 예로 "89"를 생각해 보자. i가 1인 상황을 가정한다. "9"는 1~9의 숫자이므로 1번..

문제 왼쪽 상단 코너에서 오른쪽 하단 코너까지 각 칸에 적힌 수의 합이 최소인 경로를 구해라. 풀이 이 문제를 푸는 데 중요한 포인트는 특정 칸까지의 최소인 경로는 하나만 구하면 된다는 점이다. 그 경로가 어떤 경로인지는 중요하지 않고, 수의 합이 최소라는 점만 중요하다. 따라서 최소의 합을 내는 경로를 구했다면 그 최소의 합만 저장하고, 경로는 저장할 필요가 없다. 따라서 이 문제는 동적 프로그래밍으로 풀기에 적합하다. 각 칸까지의 경로의 최소 합을 저장하고, 다음 칸의 값을 구할 때 이전 값들을 사용하면 된다. 즉, dp[i][j] = min(dp[i-1][j], dp[i][j-1])+ grid[i][j]. (물론, 예외처리는 해주어야 한다.) 코드 class Solution(object): def ..