# 동적프로그래밍

22개의 포스트
post-thumbnail

Programmers - 피보나치수

프로그래머스 - [Level2] 피보나치 수 및 Memoization과 Bottom-up 정리

2021년 4월 2일
·
0개의 댓글
post-thumbnail

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

백준 11054 가장 긴 바이토닉 수열이 문제는 각각의 인덱스 기준 양옆의 LIS를 구하는 문제였다.그러니까 1 2 3 2 1은 1 2 3과 같이 3기준 LIS가 만족함과 동시에, 3기준 뒤쪽에 있는 값은 감소하는 부분 수열이 되어야 한다.그럼 감소하는 부분 수열은 맨

2021년 2월 26일
·
0개의 댓글
post-thumbnail

백준 11053 가장 긴 증가하는 부분 수열

백준 11053 가장 긴 증가하는 부분 수열예를 들어서 10 20 10 30 20 50이 있다고 하면, 가장 긴 증가하는 부분 수열은 10 20 30 50이다.즉, 위의 수의 나열에는 여러가지의 부분 수열 중 ex) 10 20, 10 20 30 .... 중 가장 긴 부

2021년 2월 25일
·
0개의 댓글
post-thumbnail

백준 1256 포도주 시식

백준 1256 포도주 시식 문제 > 해결 이 문제는 이전에 계단 오르기와 많이 비슷했다. 백준 2579 계단 오르기

2021년 2월 19일
·
0개의 댓글
post-thumbnail

백준 1463 1로 만들기

백준 1463 1로 만들기이 문제의 조건을 풀어쓰면 다음과 같다X가 3의 배수이면 3으로 나눈다.X가 2의 배수이면 2로 나눈다.X가 3 또는 2의 배수가 아니라면, 1을 뺀다.문제는 말 그래도 위의 조건식으로 1을 만드는 과정중, 최소의 루트를 찾는 것이라고 생각하면

2021년 2월 18일
·
0개의 댓글
post-thumbnail

백준 1932 정수 삼각형

백준 1932 정수 삼각형처음에 입력은 아래와 같이 준다.73 88 1 02 7 4 44 5 2 6 5이 중, Top down에서, 대각선으로 이동 한 결과 최대 경로를 구하는 문제이다.이 문제를 처음 마주했을 때, 정말 햇갈렸던 것은, "문제 예시랑 입력이랑 다르잖아

2021년 2월 16일
·
0개의 댓글
post-thumbnail

백준 9461 파도반 수열

백준 9461 파도반 수열음.. 이 문제는 처음에 그림만 봤을 땐, 기하로 가야하나 정도로 많이 복잡해 보였다.하지만 파도반이 사람 이름이라는 것을 알게되었고 그 사람의 방정식이 존재한다는 것을 알게 되었다.Padovan sequence이 방정식을 뭐 읽어보고 풀면 그

2021년 2월 16일
·
0개의 댓글
post-thumbnail

백준 1904 01타일

1904번: 01타일우리가 사용할 수 있는 카드는 00과 1뿐이다.잘 생각해보면, 현재 번째에 카드를 만들 수 있는 카드는 이전에 나열되었던 카드 수열에,00과 1을 더 붙히면 된다. 예를 들어, $i-1$번째에, 0011이었다면, 현재로의 만들 수 있는 카드는 001

2021년 2월 16일
·
0개의 댓글
post-thumbnail

백준 2579 계단 오르기

백준 2579 계단오르기동적계획법은 “전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식” 입니다.해결은 결국 DP를 사용해야 했던 문제 이다.계단을 오르기 위해선, 3가지의 조건이 있다.계단은 한 번에 한 계단

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

[코딩테스트 준비] 동적 프로그래밍 - 거스름돈 주기

위의 예시에서 14원을 거슬러줄 수 있는 방법은 아래와 같다.이를 봤을떄, 현재 change 에서 각각의 동전의 값을 뺀 값의 갯수 + 1 중에서 가장 작은 값을 return 해주면 된다.이렇게, 큰 값(14원) 의 갯수 를 작은 값(13원 일때, 12원 일때, 7원

2021년 2월 7일
·
0개의 댓글
post-thumbnail

[프로그래머스 LV2] 가장 큰 정사각형 찾기

먼저 이 문제를 효율성에 맞춰서 풀기 위해서는 Dynamic Promgamming(동적 프로그래밍) 알고리즘을 사용해야한다동적 프로그래밍 알고리즘 이란, 큰 케이스를 작은 케이스로 나눠서 작은 케이스들을 계속해서 검사하는 Top - Down 방법과작은 케이스 부터 검사

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

[다이나믹]-1912_연속합

링크텍스트배열이 주어졌을 때 연속적(인접한 인덱스끼리)으로 더했을 경우 가장 큰 값을 골라내야 하는 로직을 짜는 문제였다.예제10 -4 3 1 5 6 -35 12 21 -1연속적으로 옆에 있는 수를 더함으로써 최댓값인지 아닌지를 판별하는 문제로 인접한 수가 더하는데 연

2021년 2월 2일
·
0개의 댓글

[다이나믹]-1149_RGB거리

1번 2번 3번 .. n번 집을 인접한 집의 색과는 다르게 칠했을 경우최소비용 값을 구하는 문제ex. ) 1번집이 빨강 파랑 초록 중 빨강을 선택했다면 2번쨰 집은 빨강이 아닌 파랑 초록 중에 골라야 하고 3번째 집은 2번째 집에 의존하여 2번째 집이 칠하지 않는 색을

2021년 2월 2일
·
0개의 댓글

[다이나믹]-10844_쉬운 계단 수

링크텍스트일일히 계산을 하면서 규칙? 을 만들어 내려고 했지만. 1의 경우의 수가 너무 햇갈렸다.먼저 1자리인 경우는1~92자리인 경우는10,1221,2332,34...983자리인 경우는101 121 123232 234 212 210...898 876 878987 98

2021년 1월 31일
·
0개의 댓글
post-thumbnail

다이나믹 프로그래밍

중복되는 연산을 줄이기 위한 동적 계획법(DP)👏메모리 공간을 약간 더 사용하여 연산속도를 비약적으로 증가시킬수 있는 방법수학자들은 점화식을 사용해 다음과 같이 수열의 항이 이어지는 형태로 간결하게 표현한다.이를 해석하면,1번째 피보나치수 =1 , 2번째 피보나치수

2021년 1월 22일
·
0개의 댓글
post-thumbnail

동적 프로그래밍

최근 취업 준비를 하면서 알고리즘을 공부 중인데, 알고리즘 공부방법이 최근까지 잘못됬다는걸 깨닫고 공부 방법을 바꿔보려고 한다. 유형을 먼져 공부하고 해당 유형에 맞는 문제들을 20문제 정도 풀어보니 Velog 에 글을 쓰며 설명할 정도로는 이해한 것 같아 적어보려고

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

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

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

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

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

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

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

2020/01/16 재귀와 동적 프로그래밍

재귀와 동적 프로그래밍 재귀적 해법의 접근법 재귀적 해법은 부분문제에 대한 해법을 통해 완성된다. 가장 흔하게 사용되는 방법은 상향식(botton-up), 하향식(top-down), 반반(half-half)이 있다. >### 1. 상향식 접근법 하나 풀고 그걸로 다음 거 풀고 다음 거 풀고.. 이전에 풀었던 사례를 확장하여 다음 풀이를 찾는다. 가장 직...

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