마이의 개발 블로그

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 동적 계획법(Dynamic Programming, DP) 문제이다. 처음에 DFS로 테스트 케이스를 풀어내긴 했는데 인풋 최대값이 100,000이다보니 실제 채점에서는 전부 통과되지 않아 DP로 바꾸어 풀게되었다. DP는 '기억하며 풀기'로 보통 바꾸어 말하는데 반복되는 문제에 대한 최적의 결과를 단계별로 메모리에 저장하고 이를 활용하여 다음 단계의 결과를 구하는 방식으로 사용한다. 여기서는 땅따먹기의 각 단계별로 직전단계까지의 최대값을 저장(또는 land에 바로 더해주기)하는 방식으로 DP를 구현했다. - ..