목록2024/08/07 (2)
on my way
땅따먹기 게임 문제 풀이문제 설명땅따먹기 게임은 N행 4열로 이루어진 배열 형태의 땅을 가지고 진행됩니다. 게임의 규칙은 다음과 같습니다:각 행의 4개 숫자 중 하나를 선택하여 점수를 획득합니다.한 행씩 내려오며 점수를 얻어야 합니다.같은 열을 연속으로 선택할 수 없습니다.예를 들어, 다음과 같은 배열이 주어졌을 때:1 2 3 55 6 7 84 3 2 1첫 번째 행에서 네 번째 칸(5)을 선택하고, 두 번째 행에서 두 번째 칸(6)을 선택하며, 세 번째 행에서 첫 번째 칸(4)을 선택하는 방식으로 진행됩니다. 이 때, 얻을 수 있는 점수의 최대값을 구하는 문제입니다.제한사항행의 개수 N: 100,000 이하의 자연수열의 개수는 4개점수: 100 이하의 자연수문제 접근 방식DP 방식 구현DP 테이블 초기화..
Python 코딩테스트 08: 다이나믹 프로그래밍(DP)다이나믹 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누어 푸는 방법론입니다.이 방법론은 작은 문제들의 해답을 이용해 큰 문제의 해답을 찾는 과정에서 효율적인 메모리 사용과 계산 속도 향상을 목표로 합니다. DP는 주로 두 가지 속성을 가지는 문제에 적합합니다:최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)입니다.다이나믹 프로그래밍의 기본 원리최적 부분 구조 (Optimal Substructure)문제를 작은 하위 문제들로 나누고, 이 하위 문제들의 해답을 이용하여 원래 문제의 해답을 도출할 수 있는 속성입니다.예를 들어, 피보나치 수열의 ..