Algorithm/동적계획법8 [프로그래머스 lv 3] N으로 표현 사용 언어 - Python3 문제 - N으로 표현 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 n숫자를 이용해서 number를 만들기 n 숫자를 1개부터 8개(cnt)까지 활용하면서 찾아준다. n을 최소한으로 사용해야하므로 number 값이 나오면 바로 끝낸다. return cnt 구하는 값 저장할 리스트, dp = [] dp 값들로 사칙연산한 값을 저장할 set, partial_dp = set() n을 2번 사용한다 = n + n o.. 2023. 12. 5. [프로그래머스 lv 4] 도둑질 사용 언어 - Python3 문제 - 도둑질 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 DP 규칙 찾기 (정답 맞춘 여부 X) 인접한 집은 못 털기 때문에, 아래의 점화식이 성립한다. dq[i] = max(dq[i-1], money[i] + dq[i-2]) 인접한 집 털거나, 현재 집과 전전집 털기 중 max값으로 업데이트 원의 형태라 1번집과 마지막집은 인접해, 같이 털지 못한다. 1번집을 터는 경우와 안터는 경우로 구분해서 계산한다. 1번집을 털면, 마지막 집은 털지 못하기 때문에 범위가 len(money)-1까지만 계산한다. 1번집을 안털면.. 2023. 6. 7. [프로그래머스 lv 4] 사칙연산 사용 언어 - Python3 문제 - 사칙연산 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 DP 규칙 찾기 (정답 맞춘 여부 X) 사칙연산의 최대값을 구하기 arr를 뒤에서부터 확인하면서 마이너스가 나오기 전까지 sum_value에 값을 더해준다. 숫자인 경우, sum_value에 값을 더한다. sum_value += int(arr[idx]) +부호인 경우, continue 마이너스 부호를 만나면, 현재까지 저장한 값 sum_value에만 마이너스를 붙일지, 앞의 값체 계산한 값에서 마이너스를 붙일지 결정해야 한다. 최대/최소값을 갱신한다. 최솟값.. 2023. 6. 7. [프로그래머스 lv 3] 등굣길 사용 언어 - Python3 문제 - 등굣길 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 DP 규칙 찾기 (정답 맞춘 여부 X) 0. input puddles 2023. 6. 2. [프로그래머스 lv 3] 정수 삼각형 사용 언어 - Python3 문제 - 정수 삼각형 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 DP 규칙 찾기 (정답 맞춘 여부 X) 행, 열을 전부 돌면서 해당 위치의 값과 윗 값을 더해 가장 큰 값으로 해당 위치를 업데이트해준다. 가장 윗 값은 더할 것이 없으므로 무시하고 인덱스 1부터 시작한다. (실제론 2행부터 시작) 1. 삼각형의 가장 왼쪽 열 = 오른쪽 값만 더하기 2. 삼각형의 가장 오른쪽 열 = 왼쪽 값만 더하기 3. 나머지 값 = 양쪽 값 중에 큰 값으로 더하기 삼각형 마지막 행들 중 가장 큰 값을 return 한다. def sol.. 2023. 6. 2. 다이나믹 프로그래밍? 나동빈 이코테 유튜브 강의 정리 https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 다이나믹 프로그래밍 DP = 동적 계획법 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록. 두 가지 조건 만족 시 DP 사용 - 최적 부분 구조 Optimal Substructure 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다. - 중복되는 부분 문제 Overlapping Subproblem 동일한 작은 문제를 반복적으로 해결해야 합니다. 대표 문제. 피보.. 2023. 6. 1. [Python3] 백준 1904번 01타일 사용 언어 - Python3 문제 - 01타일 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 정답 DP 기초 문제 (정답 맞춘 여부 X) 1. dp = [0]*(1000001), n+1 만큼 0으로 이루어진 리스트 dp 생성 2. 예외처리 n이 1,2이면, 답이 정해져있다. 가독성을 위해 인덱싱은 1부터 한다. dp[1] = 1 dp[2] = 2 3. n이 3이상인 경우 dp[i] = i까지의 최대값 dp[i]=(dp[i-2]+d[i-1])%15746 dp[n] = 모든 2진 수열의 개수를 15746으로 나눈 나머지 2023. 4. 6. [Python3] 백준 2579번 계단오르기 사용 언어 - Python3 문제 - 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 정답 DP 기초 문제 (정답 맞춘 여부 X) 1. dp = [0]*(n), 0으로 이루어진 리스트 dp 생성 2. 예외처리 계단이 애초에 두개 이하이면, 첫번째 계단+두번째 계단밖에 정답이 없으므로 sum(s) 3. 계단이 3개이상인 경우부터 dp에 값 입력 dp[i] = i까지의 계단 최대값 dp[0] = s[0] dp[1] = s[0]+s[1] dp[2]부터는 경우의 수가 늘어난다. dp[i]=max(dp[i-3]+s[i.. 2023. 4. 5. 이전 1 다음
