# 다이나믹프로그래밍

50개의 포스트
post-thumbnail

[프로그래머스/파이썬] 다이나믹프로그래밍 등굣길

https://programmers.co.kr/learn/courses/30/lessons/42898다이나믹프로그래밍 def solution(m, n, puddles): from collections import deque dx=1,0 dy=0,1 k

2021년 2월 17일
·
0개의 댓글
post-thumbnail

[프로그래머스/파이썬] 동적계획법 정수 삼각형

https://programmers.co.kr/learn/courses/30/lessons/43105다이나믹프로그래밍백준 1932 정수 삼각형과 동일한 문제이다.규칙을 찾으면 쉽게 접근이 가능하다.

2021년 2월 15일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV2] 가장 큰 정사각형 찾기

먼저 이 문제를 효율성에 맞춰서 풀기 위해서는 Dynamic Promgamming(동적 프로그래밍) 알고리즘을 사용해야한다동적 프로그래밍 알고리즘 이란, 큰 케이스를 작은 케이스로 나눠서 작은 케이스들을 계속해서 검사하는 Top - Down 방법과작은 케이스 부터 검사

2021년 2월 7일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 2193 이친수

https://www.acmicpc.net/problem/2193다이나믹프로그래밍n에 따른 이친수를 나열하다보면 규칙이 피보나치 함수와 동일하다는 것을 알 수 있다.

2021년 2월 5일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 11055 가장 큰 증가 부분 수열

https://www.acmicpc.net/problem/11055다이나믹 프로그래밍기본적인 구조는 가장 긴 부분 수열을 구하는 것과 비슷하다.di는 arrayi번까지의 증가 부분 수열의 합이다.예를 들어, 2,1,2과 같은 경우는 2,1,3이 나와야 한다.2

2021년 2월 5일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 11054 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054다이나믹프로그래밍원래의 수열에서 증가하는 수열 길이는 1,2,2,1,3,3,4,5,2,1,감소하는 수열 길이는 1,5,2,1,4,3,3,3,2,1이다.예시의 경우, 1,2,3,4,5 / 5,2,

2021년 2월 5일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 9251 LCS

https://www.acmicpc.net/problem/9251다이나믹 프로그래밍백준 11053 문제와 유사한 문제이다.너무 어렵다.. 차근차근 예시를 살펴보자.A C 0A CA 1A CAP 1A CAPC 1...AC C 1AC CA 1AC CAP 1AC C

2021년 2월 4일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 2156 포도주 시식

https://www.acmicpc.net/problem/2156다이나믹프로그래밍백준 2579 계단오르기 문제와 상당히 유사하다.차이점은 계단오르기는 마지막 계단을 꼭 밟고 끝나지만, 이 문제는 마지막 잔을 마시지 않을 수도 있다는 것이다.di는 i번째 포도주

2021년 2월 4일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053다이나믹프로그래밍d0은 수열 A의 첫 번째 원소까지로 만든 부분수열 중 최대 길이를 저장한다.ex)i=2if 10<a2, if 20<a21, 2, 1, 1, 1, 11, 2, 1, 3

2021년 2월 4일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 1932 정수 삼각형

https://www.acmicpc.net/problem/1932다이나믹프로그래밍하나씩 적어가면서 규칙을 찾았다.ex)d0=7d1=3+7, d1=8+7d2=8+d1, d2=1+max(d1,d1),d2=0+d1d3=2+d2, d3=7+max(d2,d2),d3=4

2021년 2월 4일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 2579 계단 오르기

https://www.acmicpc.net/problem/2579다이나믹프로그래밍ex)d0=10d1=10+20=30d2=max(15+10, 15+20)=35d3=max(stairs3+d1, stairs3+stairs2+d0)=max(25+d1, 25+15+d0

2021년 2월 4일
·
0개의 댓글

[백준/파이썬] 1149 RGB거리

https://www.acmicpc.net/problem/1149 알고리즘 분류 다이나믹 프로그래밍 문제풀이 처음에 0번 집에서 최소값을 가지는 색깔을 선택해서 풀었는데 다음과 같은 반례 때문에 실패했다. ex) 2 100 1 100 999 1 999 -> 10

2021년 2월 3일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 11726 2*n 타일링

https://www.acmicpc.net/problem/11726다이나믹프로그래밍세로의 크기는 2로 고정되어있기때문에 n이 늘어날수록 채우는 방법의 수가 어떻게 바뀌어가는지 살펴보면 된다.ex)1X2타일은 =, 2X1타일은 ㅣn=1 ㅣ -> 1개n=2 ㅣㅣ,

2021년 2월 3일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 1003 피보나치 함수

https://www.acmicpc.net/problem/1003다이나믹 프로그래밍기본적인 다이나믹 프로그래밍 알고리즘 문제로 0, 1이 출력되는 횟수를 계속해서 누적해 더해나가면 된다.

2021년 2월 3일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 9095 1,2,3 더하기

https://www.acmicpc.net/problem/9095다이나믹프로그래밍di는 i를 만들기 위한 방법의 수d1=1 -> 1d2=1+1, 2 -> 2d3=1+1+1, 2+1, 3 -> 3d4=1+d3의 원소들, 2+d2의 원소들, 3+d1의 원소들...

2021년 2월 3일
·
0개의 댓글
post-thumbnail

[백준/파이썬] 1463 1로 만들기

https://www.acmicpc.net/problem/1463다이나믹프로그래밍

2021년 2월 3일
·
0개의 댓글
post-thumbnail

[백준 1003] 피보나치 함수_Python

https://www.acmicpc.net/problem/1003

2021년 2월 3일
·
0개의 댓글
post-thumbnail

[동빈나/파이썬] 다이나믹 프로그래밍 개념 & 기초 문제 풀이

최적 부분 구조큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결중복되는 부분 문제동일한 작은 문제를 반복적으로 해결메모이제이션(탑다운) O(N)한 번 계산한 결과를 메모리 공간에 메모바텀업바텀업방식바텀업 방식 ex) 0, 1001, 1, 1

2021년 2월 2일
·
0개의 댓글
post-thumbnail

[PART2] 8-3(DP): 바닥 공사 ❗

난이도🖤🖤🖤🤍🤍🤍 | 풀이시간 20분 | 제한시간 1초 | 메모리제한 128MB솔루션이 쉽게 떠오르지 않아서 해설을 먼저 참고하고 혼자 코드를 짰다.혼자 정리해 본 아이디어는 이렇다.🔴 백준 11727 문제와 유사하다결과값이 굉장히 커질 수 있기 때문에 값

2021년 2월 1일
·
0개의 댓글