# 다이나믹프로그래밍

25개의 포스트
post-thumbnail

[알고리즘] DP 박살내기 1. 문제 해결하기

DP가 어떤 경우에 사용될 수 있는지 저번 글을 통해 알아봤다.이번에는 본격적으로 문제를 DP적으로 접근하는 방법 에 대해 공부하자.GeeksforGeeks - How to solve a Dynamic Programming Problem ?특정 조건 하에 최대의, 최소

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

[알고리즘] DP 박살내기 0. 기본 개념

다이나믹 프로그래밍 뭔지 알겠다! → 코테 박살내러 간다! → 하지만 박살나는 건 나였다아는 것 같은데 항상 시도할 때마다 벽을 느꼈던 다이나믹 프로그래밍 기본기가 부족하다고 항상 느껴왔던 터라 이참에 알고리즘의 기본들을 하나하나 박살내보기로 마음먹었다.LeetCode

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

백준 17208 카우버거 알바생

문제 중간고사 종료를 기념해 계획 없이 돈을 쓰던 영석이는 안타깝게도 통장 잔고가 100원도 남지 않게 되었고, 결국 영석이는 카우버거 주방 알바를 하기로 했다. 카우버거는 치즈버거와 감자튀김을 파는 중앙대학교의 유명한 음식점이다. 알바 첫날, 영석이가 주방에 들어선

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

[코딩테스트]백준 - 정수 삼각형(1932)

정수 삼각형(1932)※ 다이나믹 프로그래밍으로 해결한다. 삼각형을 한층한층 내려갈 때마다 가장 왼쪽과 가장 오른쪽을 제외하고는 모두 중복되어 더해진다. ex. 예를 들면,이렇게 생긴 삼각형을 살펴보자.첫번째 : 7두번째: 3 8max(7+3, 7+8)여기까지는 중복되

2020년 8월 17일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 1, 2, 3 더하기 (9095번)

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작

2020년 7월 28일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 피보나치 함수(1003번)

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1)

2020년 7월 27일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 가장 긴 증가하는 부분 수열(11053번)

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

2020년 7월 26일
·
2개의 댓글
post-thumbnail

백준 2579번: 계단 오르기

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

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

백준 2156번: 포도주 시식

문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고

2020년 7월 18일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 연속합

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수

2020년 7월 12일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - RGB 거리

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비

2020년 7월 11일
·
0개의 댓글
post-thumbnail

[코딩테스트]프로그래머스 - 2xn 타일링

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.타일을 가로로 배치 하는 경우타일을 세로로

2020년 7월 11일
·
0개의 댓글
post-thumbnail

[코딩테스트]백준 - 1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의

2020년 7월 11일
·
0개의 댓글
post-thumbnail

[문제]땅따먹기

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

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

[코딩테스트]백준 - 포도주 시식

포도주 시식 문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는

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

[코딩테스트]백준 - 계단오르기

백준.. 친해지기 어려워 (┬┬﹏┬┬)계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 <그

2020년 6월 3일
·
2개의 댓글

[프로그래머스] 거스름돈 (JavaScript)

프로그래머스 거스름돈JavaScript로 구현하면서 좀 더 효율적인 방법을 생각해봤는데 기존의 2차원 dp 테이블을 유지할 필요가 없다는 생각이 들었다. 2차원 테이블을 채워나가는 방법이 이전 화폐 구성(위쪽 행)을 바탕으로 하는 것이므로 이전 행을 갱신하는 방식이다.

2020년 5월 5일
·
2개의 댓글

[프로그래머스] 거스름돈 (Java)

프로그래머스 거스름돈다이나믹프로그래밍 문제를 항상 피하기만 했는데 자주 풀어서 익숙해져야겠다. 직접 표를 그려서 규칙성을 찾아보면 2차원 dp로 풀이가 가능함을 알 수 있다.money 배열을 오름차순으로 정렬한다. 화폐를 오름차순으로 차례대로 쓸 것이기 때문이다.2차원

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

[프로그래머스] 보행자 천국 (Java)

프로그래머스 보행자 천국이전의 이동방향을 기억해야한다는 점에서 BOJ 17070 파이프 옮기기1 문제가 떠올랐다. 이 문제에서는 아래쪽 또는 오른쪽으로 이동할 수 있으므로 두 방향을 저장할 수 있도록 하였다.보통 이런 문제를 풀 때 dp\[i]\[j]가 나타내는 바는

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

[프로그래머스] 피보나치의 수 (Java)

프로그래머스 피보나치의 수 문제풀이 피보나치의 수는 다이나믹프로그래밍을 설명하는 기초 문제일 정도로 명확하게 알고 넘어가야한다. 아주 잘 정리된 피보나치 수열을 구하는 여러가지 알고리즘 글이 있어서 이를 바탕으로 다시 공부하였다. 단순 재귀는 O(2^n) 단순 반복

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