# 동적계획법

16개의 포스트
post-thumbnail

[백준] 1149번 RGB 거리

R로 칠한 경우G로 칠한 경우B로 칠한 경우★ 3가지 경우를 모두 고려하여 계산하는 것이 중요했음 ★

7일 전
·
0개의 댓글

[백준] 9461번 파도반 수열

n의 값이 커지면 int형의 범위를 벗어날 수 있어 반환값과 memo의 자료형을 long으로 해줘야 한다.

2020년 7월 6일
·
0개의 댓글

[쉽게 배우는 알고리즘] 동적 프로그래밍

동적 프로그래밍은 큰 문제의 해답에 작은 문제에 해답이 포함되어 있고, 이를 재귀 호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 뜻합니다.이처럼 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조를 최적 부분 구

2020년 7월 3일
·
0개의 댓글

[알고리즘 문제 해결 전략] 동적 계획법

어떤 부분 문제는 2개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 것이 아니라 한 번만 계산하고 그 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있음이미 계산한 값을 저장해두는 메모리의 장소를 캐시(cache)라고 부름함수의

2020년 6월 30일
·
0개의 댓글
post-thumbnail

[문제]땅따먹기

DP를 활용한다. DP는 또 뭘까?

2020년 6월 29일
·
0개의 댓글

[알고리즘] 재귀 용법, 동적 계획법, 분할 정복

재귀 용법 (recursive call, 재귀 호출) 함수 안에서 동일한 함수를 호출하는 형태 재귀 호출은 스택의 전형적인 예 함수는 내부적으로 스택처럼 관리된다 동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer)

2020년 6월 21일
·
0개의 댓글

프로그래머스 - 스티커 모으기(2)

https://programmers.co.kr/learn/courses/30/lessons/12971접근레벨4 답게 어려웠습니다.처음에 생각한 방식은 여러가지 있었습니다.DFS구간합DFS의 경우 최대 깊이가 5만(최대길이 10만 / 2) 씩이나 되는 말도안되는

2020년 5월 22일
·
0개의 댓글
post-thumbnail

[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)

동적 계획법(Dynamic Programming) - 컴퓨터 공학 스터디 W1 자료구조와 알고리즘 내용에 앞서 학교에서 컴퓨터 공학 이론 스터디를 진행하고 있습니다. 매주 발표하는 내용을 시리즈로 업로드할 예정입니다. 공부 목적으로 작성되는 글이니 부족한 부분, 참고

2020년 4월 21일
·
0개의 댓글

프로그래머스 서울에서 경산까지(java)

https://programmers.co.kr/learn/courses/30/lessons/42899 주어진 시간안에 최대의 모금액을 모을 수 있는 경우를 찾아야하는 문제이다. 각각의 이동에서는 자전거와 도보로 갈 수 있는 두가지 방법이있다. public int s

2020년 4월 10일
·
0개의 댓글
post-thumbnail

[Algorithms] Dynamic Programming, 동적 계획법

What is it 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해 보다 큰 크기의 부분 문제를 해결. 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장. 해당 결과값을 이용해 상위 문제를 풀

2020년 3월 3일
·
0개의 댓글

[BOJ 2169] 로봇 조종하기 (Java)

BOJ 2169 로봇 조종하기최악의 경우에 N, M이 1000이 될 수 있기 때문에 주어진 제약조건에서 탐색 알고리즘을 통한 완전 탐색은 불가능하다. 따라서 각 칸에 도착하는 최댓값을 갱신해나가는 다이나믹프로그래밍을 사용해야한다.각 칸에 도착할 수 있는 경우를 잘 구분

2020년 2월 19일
·
0개의 댓글

[BOJ 1937] 욕심쟁이 판다 (Java)

BOJ 1937 욕심쟁이 판다다이나믹프로그래밍 유형도 재미가 하다보니 있는 것 같다. 주어진 데이터 기반으로 각 지역에서 이동할 수 있는 최댓값으로 DP 테이블을 갱신해나가는 문제, 이 블로그에 굉장히 잘 설명되어있다.한 번 갱신한 지역은 다시 갱신하지 않아도 되기 때

2020년 2월 18일
·
0개의 댓글

[BOJ 1915] 가장 큰 정사각형 (Java)

BOJ 1915 가장 큰 정사각형다차원 다이나믹프로그래밍으로 풀이가 가능한 문제였다.dp\[i]\[j]는 현재 \[i]\[j]칸을 정사각형의 가장 오른쪽 아래로 했을 때 만들 수 있는 가장 큰 정사각형의 한 변의 길이다.dp\[i]\[j]는 dp\[i - 1]\[j],

2020년 2월 18일
·
0개의 댓글

[BOJ 11051] 이항 계수 2 (Java)

BOJ 11051 이항 계수 2이항계수 nCk는 파스칼의 법칙에 의해서 nCk = n-1Ck-1 + n-1Ck 이다. 이러한 파스칼의 법칙에 따라 삼각형으로 배열한 파스칼의 삼각형을 이용하는 문제다.위의 점화식을 바탕으로 동적계획법을 수행하여 파스칼의 삼각형을 만든다.

2020년 2월 16일
·
0개의 댓글

동적 계획법(Dynamic Programming) - 최적 부분 구조

최적 부분 구조란 > 앞서 살펴 보았던 동적 계획법 문제는 어떠한 값을 계산하거나, 경로가 존재하는 지에 대한 문제에 사용되었던 방식이다. 최적화 문제는 그러한 계산값이나 경로 중 어떤 것이 최적인지를 계산하는 문제인데, 이 때 설계하는 재귀 함수의 파라미터로 가장 필수적인 값만 넘겨주는 부분 문제의 구조가 최적 부분 구조이다. 이 때 불필요한 값까지 넘...

2019년 6월 28일
·
0개의 댓글
post-thumbnail

알고스팟 TRIPATHCNT 삼각형 위의 최대 경로 수 세기

문제 사진과 같은 숫자 삼각형이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려갑니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 제일 아래 칸에서 얻을 수 있는 최대값의 경로 개수를 구하시오. (최대값은 여러개일 수 있습니다.) C(C <= 50) 테스트 케이스의 수 , n(2 <...

2019년 2월 7일
·
0개의 댓글