# DP

tunaman95

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째

donggni0712

재귀가 아닌 DP

ikkoun

DP(Dynamic Programming) 기법해결한 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 캐싱 기법을 활용하여 문제의 시간 복잡도를 줄이는 문제 해결 기법.\-> PrefixSum (배열의 맨앞부터 특정 위치까지의 합

su96in43

백준 문제풀이입니다.

wakeupmakeup

처음 문제를 보고 어찌 접근해야 하나 고민이었다. 위에 문제 처럼 먼저 4를 분해해 보면 이렇다. 1 + 1 + 1 + 11 + 1 + 2 1 + 2 + 1 2 + 1 + 12 + 21 + 33 + 1뭔가 규칙성이 보이지 않는가? 이번엔 10으로 다시 한번 해보자. 1

hereokay

조건이 상당히 복잡해보인다. M개 줄, N개의 요소 라고 용어를 정리하고 들어가자.k번째 줄을 선택하면 위아래 줄은 그대로 없어진다. 즉 M개줄 중에서 가장 많이 선택해도 M/2개를 넘을수 없다.N개의 요소중 가장 많이 선택하는 방법은 N이 짝수일때 N/2개, 홀수일때

aurora_97

https://www.acmicpc.net/problem/2281일단 이름을 쓸때, 두가지 선택권이 있다현재 줄에 이어서 쓰기다음 줄에 처음으로 쓰기완전탐색을 하면, n, m 이 둘다 1000이라서 무조건 시간초과가 날꺼고..중복을 줄이기 위해서 dp를 써야한

murjune

https://www.acmicpc.net/problem/2629 저울에 추를 왼쪽으로 올리는 경우, 안 올리는 경우, 오른쪽으로 올리는 경우로 나누고, dfs를 돌린다. 중복되는 경우를 방지하기 위해 2차원 테이블 didx를 사용했다. didx : idx

murjune

https://www.acmicpc.net/problem/2098 외판원 순회는 n의 범위가 10개인지 16개인지에 따라 풀 수 있는 알고리즘이 다르다. 10개인 경우(외판원 순회2)는 완전탐색, 백트래킹 기법으로 비교적 쉽게 풀 수 있으나, 고작 도시가 6개 추가

dasd412

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.첫째 줄과 둘째 줄에 두 문자

wldnd2

Fractional Knapsack Algorithm (그리디)

khyup0629

백준 9184번 신나는 함수 실행위 재귀함수의 성능 문제는 구했던 값을 반복해서 구하는 것에 있습니다.따라서 한 번 구한 값을 저장할 수 있는 공간(dp)을 만들어서 계산의 결과값을 저장합니다.다음에 그 값을 이용해야 할 일이 있을 때, 계산이 아닌 저장된 값을 사용하

sugenius77

.

khyup0629

백준 12865번 평범한 배낭

yyj8771

백준 9461번 파도반 수열 풀이

pass

👀 문제 사이트 : https://www.acmicpc.net/problem/2342이 문제를 처음 풀 때는 greedy로 모든 곳을 탐색하면서 q에 경우의 수를 늘려가면서 해결하려고 하였다.그렇게 풀었을 경우에 예외 처리를 많이 해주어야 되고, step은

hereokay

한글로 번역하면 최장 공통 부분수열이다. 비슷한 개념으로는 최장 공통 문자열(Longest Common Substring)이 있다.후자는 말그대로, 두 문자열중 공통되는 문자열이 연속으로 이어지는 문자열을 말한다.ACAYKP와 CAPCAK의 최장 공통 부분수열은 ACA

hozero

다음과 같이 dp를 정의하고 접근했다.dpi: i번째 물건까지 최대 j무게로 했을 때 최대가치

reyang

연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘동적 계획법이라고도 표현2가지 방식 (탑 다운, 바텀 업)밑으로는 다이나믹 프로그래밍으로 해결할 수 있는 문제들이전 두 항의 합을 현재 항으로 설정하는 특징f (x) + f (x + 1) = f (x

zzarbttoo

백준 11054(가장 긴 바이토닉 부분 수열) python 풀이입니다