# DP

2013개의 포스트

[백준] 2579번 - 계단 오르기 Python

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

약 3시간 전
·
0개의 댓글

[BOJ]1463번 1로 만들기 C++

재귀가 아닌 DP

약 8시간 전
·
0개의 댓글
post-thumbnail

DP - 구간 합 빠르게 계산하기

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

약 20시간 전
·
0개의 댓글
post-thumbnail

BOJ - 9095 (1,2,3 더하기), Python

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

약 22시간 전
·
0개의 댓글

[백준 5721/C++] 사탕 줍기 대회

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

약 22시간 전
·
0개의 댓글
post-thumbnail

백준 2281번: 데스노트 - Swift

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

어제
·
0개의 댓글

백준-양팔저울(feat.Python)

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

어제
·
0개의 댓글

백준- 외판원 순회(feat.Python)

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

어제
·
0개의 댓글

백준 9252 LCS2 파이썬

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

어제
·
0개의 댓글

알고리즘 | Fractional Knapsack Algorithm (그리디)

Fractional Knapsack Algorithm (그리디)

2일 전
·
0개의 댓글

[9184번] 신나는 함수 실행

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

2일 전
·
0개의 댓글

[12865번] 평범한 배낭

백준 12865번 평범한 배낭

2일 전
·
0개의 댓글
post-thumbnail

백준 9461번 - 파도반 수열

백준 9461번 파도반 수열 풀이

3일 전
·
0개의 댓글

백준 2342 Dance Dance Revolution

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

3일 전
·
0개의 댓글
post-thumbnail

[BOJ 9251] LCS(Longest Common Subsequence)

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

4일 전
·
0개의 댓글
post-thumbnail

[BOJ] 12865번 평범한 배낭

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

4일 전
·
0개의 댓글
post-thumbnail

[DP] 다이나믹 프로그래밍이란?

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

4일 전
·
0개의 댓글

[BOJ]11054(python)

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

4일 전
·
0개의 댓글