DP (4) 썸네일형 리스트형 213. House Robber II https://leetcode.com/problems/house-robber-ii/I. 문제 개요DP를 활용하여 도둑질로 얻을 수 있는 최댓값을 구하는 문제이다. II. 알고리즘 설계만약 첫번째 집을 털면 2번째, 마지막 집은 털 수 없다. 왜냐하면 집들은 원형으로 놓여있기에, 첫번째 집을 털면 2번째와 마지막 집에 경보가 들어오기 때문이다. 따라서, 첫번째 집을 터는 경우와 털지 않는 경우 2가지로 나눠서 생각해야 한다. 1. 첫번째 집부터 터는 경우V(시작)XO...OX V: 시작점O: 털 수 있는 집X: 못 터는 집 dp에 사용할 list를 만들고, 1번째와 2번째 원소는 nums[0]으로 변경한다. 그다음 2번째 집부터 터는 경우와, 털지 않았을 때의 금액 중, 더 큰 값을 list에 집어넣는다 .. 등굣길 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr I. 문제 개요DP를 활용하여, 유효한 경로의 갯수를 찾아내는 문제이다. II. 알고리즘 설계00000010000000000000 0 : 패딩0 : 웅덩이 dp 탐색에 사용할 2D-list는 위와 같이 초기화 할 수 있다. 윗쪽과 왼쪽에 0으로된 padding을 추가함으로써, 탐색할 때 경계를 넘어갈 경우에도 에러를 예방할 수 있다. 각 칸에 도달하는 경우의 수는 (현재 칸의 윗칸에 도달하는 경우의 .. 정수 삼각형 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr I. 문제 개요 삼각형에 들어있는 숫자 중, 지나온 숫자들의 최대 합을 구하는 문제이다. II. 알고리즘 설계 및 풀이 1. DP 점화식 설계 0행: 7 1행: 3 8 2행: 8 1 0 주어진 삼각형을 위와 같이 직각 삼각형으로 보자. 2행의 "8"은 1행의 "3"에서밖에 접근할 수 없다. 2행의 "1"은 1행의 "3", "8" 두 군데에서 접근할 수 있다. 2행의 "0"은 1행의 "8"에서만 접.. N으로 표현 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr I. 문제 개요 검증해야 하는 경우의 수가 과도하기에, 단순히 모든 경우의 수를 다 탐색하기에는 무리가 따른다. DP(Dynamic Programming)를 활용하여 살펴본 경우의 수를 저장하면, 모든 경우를 일일히 계산하는 수고를 덜 수 있다. II. 알고리즘 설계 및 풀이 1. 변수 초기화 ans = -1 dp = [set() for _ in range(9)] dp는 N을 사용한 횟수별로 나울.. 이전 1 다음
