# DP

1066개의 포스트
post-thumbnail

BOJ 12865: 평범한 배낭(0-1 Knapsack Problem)

BOJ 12865: 평범한 배낭 ✔ 문제해결전략 - 0-1 Knapsack Algorithm + Dynamic Programming ✔ 해결과정 - 가방에 담을 수 있는 물건의 무게에 제한이 있을 때, 가방에 담긴 물

14분 전
·
0개의 댓글
post-thumbnail

BOJ 1912 연속합

요즘 너무 이론적인 것과 형식에 치우쳤는지 DP 하면 그냥 일단 필요한 것들을 쳐놓고 시작했다.문제집을 만들어놓고 푼 것과 LIS에 너무 집착한 것도 한 몫을 한것같다.이런 행동이 시야를 좁혔고, 엄청 간단한 문제임에도 구현을 바로 하지 못하고 헤매었다.직관적으로 코드

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

백준 11660번: 구간 합 구하기 5

구간 합 구하기 5

어제
·
0개의 댓글

백준 1932번: 정수 삼각형

정수 삼각형 백준 1932번: 정수 삼각형 아이디어 같은 크기의 배열을 만들어서 합을 기록한다. 이 때 본인과 더해질 수 있는 숫자는 왼쪽 위, 오른쪽 위 두 가지 경우 뿐이므로 둘 중 합이 더 커지는 경우를 기록한다. 맨 왼쪽, 맨 오른쪽은 선택의 여지가 없으므로

2일 전
·
0개의 댓글

백준 13398 연속합 2 (re)

하나를 빼고 연속합을 모두 구하기엔 시간 초과 각 인덱스마다 그 수로 시작하는 연속합과 그 수로 끝나는 연속합을

3일 전
·
0개의 댓글

백준 2133 타일 채우기

dp -> 작은 문제들이 많은 경우가 있다이 문제는 n이 짝수일 때 마다(2 제외) 가운데 걸쳐있는 경우가 2가지씩 생겨서 이것을 모두 포함해주어야 한다.

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

[Python] 백준 / 퇴사 / 14501번 / 브루트포스

문제퇴사 문제 링크상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의

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

백준 11660 파이썬

백준 11660

4일 전
·
0개의 댓글

백준 14501 퇴사

재귀함수를 통해 구하고 + sum 대신 메모이제이션을 추가하여 dp로 푼다

5일 전
·
0개의 댓글

백준 11054 가장 긴 바이토닉 부분 수열

앞에서부터 증가하는 가장 긴 수열 2. 뒤에서부터 증가하는 가장 긴 수열두가지 배열을 만들어서 브루트포스로 각 인덱스를 기준으로 두 값의 합이 가장 큰거 구함(인덱스까지 증가 + 감소 = 바이토닉)처음에는 인덱스 기준 앞은 증가하는, 뒤는 감소하는 가장 긴 수열을 인덱

5일 전
·
0개의 댓글

백준 11722 가장 긴 감소하는 부분 수열 (re)

ai 보다 작은 인덱스의 숫자들 순회하며 1.

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

1463 : 1로 만들기

그냥 이프문,,,반복문,,, 해서 3으로 먼저나누고,, 그 다음은 2로나누고,, 안되면 1빼고 이렇게 반복해서 문제를 풀 수 있으리라 생각했는데 10에서 예외가 발생한다.한번 확인해보자내가 생각한 방식 : 10->5->4->2->1 : 4번 문제가 생각한 방식 : 10

6일 전
·
0개의 댓글

백준 1932 정수 삼각형

dp + 이차원 리스트

6일 전
·
0개의 댓글

백준 2156 포도주 시식

dp + 이차원리스트 : 예외처리(ex. n = 1 등등) 조심포도주를 시식하는 3가지 경우의 수 : 0번째로 먹기(=먹지 않음), 1번째로 먹기, 2번째로 먹기를 이차원 리스트의 행(또는 열)로 나눠서 푼다

6일 전
·
0개의 댓글

백준 1309 동물원

dp + 이차원 리스트

6일 전
·
0개의 댓글

백준 1149 RGB 거리

dp + 이차원리스트

6일 전
·
0개의 댓글

백준 15988 1, 2, 3 더하기 3

메모리 초과 코드 : 나누기를 안함시간 초과 코드 : 매번 d를 다시 계산하면 시간 너무 많이 걸림시간 초과 코드 : 나름 머리를 써봄. 계산횟수를 줄였는데 그다지 줄여지지 않은듯먼저 d를 다 구하고 구함

6일 전
·
0개의 댓글

백준 11057 오르막수

dp + 이차원 리스트마지막 나누기 10007 안해서 틀림...

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

[BOJ] 11726 : 2xn 타일링

BOJ 11726 : 2xn 타일링2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.이 문제는 그림을 그려 생각해보면 쉬운데, n=1 일 때의 방법의 수 :

2021년 9월 18일
·
0개의 댓글