# dynamic programming
[ BOJ / Python ] 14002번 가장 긴 증가하는 부분 수열 4
이번 문제는 DP를 이용하여 해결하였다. 증가하는 부분 수열의 길이는 구하기 쉬웠지만, 수열을 구하는 과정에서 시간이 걸렸다. 우선 dp리스트를 2중 for문을 통해 순회하며 자신보다 앞에 있는 수 중 자신이 더 클 경우 dp를 갱신하였다. 이렇게 되면 증가하는 수열에
[BACKJOON] 9461번 : 파도반 수열
문제 출처 : https://www.acmicpc.net/problem/9461어떤 한 삼각형의 변의 길이는 다른 두개의 삼각형의 변의 합으로 구성되는 규칙을 보인다. 구체적으로 i번째로 형성되는 삼각형의 변의 길이는 (i-3)번째, (i-2)번째 삼각형의 변
[BOJ] 10844: 쉬운 계단 수
쉽다매... '쉬운' 계단 수라며...모든 걸 깨우친 지금에서야 아~ 괜찮네~ 싶지만 풀이를 이해하기까지 조금 어려웠다. 인터넷에 여러 글을 참고하면서 깨우친 듯하다.처음에는dp = 점화식이라고 생각을 하니까 1차원적으로 전체 가짓수의 규칙을 찾으려고 했다. 하지만 이
[BOJ] 16194: 카드 구매하기 2
저번 문제에서 아주 조금 변형된 문제.왜 d,p 라는 변수를 만들었는지는 설명하지 않겠다 ~ 저번 풀이에 있으니까!(https://velog.io/@drizzle0171/BOJ-11052-%EC%B9%B4%EB%93%9C-%EA%B5%AC%EB%A7%A4%ED
[BOJ] 11052: 카드 구매하기
쉬우면서도 어려운 그것...일단 다이나믹 프로그래밍이 나에게 어려운 이유:규칙 찾기가 너무 어렵다규칙 찾기가 꽤나 어렵다규칙 찾기가 제일 어렵다라는 것이다 ^^ ~규칙만 찾으면 금방 구현할 수 있는데 (당연한 소리) !사담은 이만 줄이고 풀이를 설명해보겠다.2가지의 리
[BOJ] 9095: 1,2,3 더하기
점화식이다? 그럼 일단 DP를 생각해보자.DP 문제를 풀면서 깨달은 바는,점화식 = 일단은 DP라고 생각해보자는 것이다.이번 문제 역시 점화식을 발견(만 한다면) 하면 쉽게 풀리는 문제이다.n=1일 때 1n=2일 때 2n=3일 때 4n=4일 때 7n=5일 때 14n=
[BOJ] 1520 내리막 길
https://www.acmicpc.net/problem/13023아이디어처음에 DP 생각을 못하고 class 만든 후 DFS를 stack으로 구현했다가 메모리초과 발생했다.map에 해당 높이만 저장하고 재귀로 풀었는데 DP를 이상하게 구현해서 시간초과 발생
[BOJ] 11727: 2xn 타일링 2
저번과 비슷한 맥락의 문제였기 때문에 어렵지 않았다 !점화식 찾는 게 조오금 어려웠다... 내가 이래서 수2도 못했는데... (요즘 수2랑 다름)규칙을 보면,n=1일 때, 방법의 수: 1n=2일 때, 방법의 수: 3n=3일 때, 방법의 수: 5n=4일 때, 방법의 수:
[백준] 1로 만들기 - 실버 3
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의
N으로 표현(lv3)
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.12 = 5 + 5 + (5 / 5) + (5 / 5)12 = 55 / 5 + 5 / 512 = (55 + 5) / 55를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.이처럼
[Algorithm] DP
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이미 계산된 결과를(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다.일반적으로 두 가지 방식탑다운 : Memoization, 큰 문제에서 작은 문제들을 재귀를 통해 호출되며
[백준] 평범한 배낭
지금까지 이 블로그를 운영하면서 생각해보면은 나는 DP류의 문제도 꽤 경험을 했다. 언제부터인지 모르겠지만 예전에 SK 코딩테스트에서 1번부터 DP문제를 때려맞고 너무 무기력하게 아무것도 못한 내 모습을 보면서 DP의 중요성을 내심 느꼈었던거같다. 코딩테스트 문제중에서
[백준] 동전 2
저번에 풀었던 동전 1 문제에서 다이나믹 프로그래밍에 대한 Tabulation 이해도를 높혔었다. 그리고 이번에 다시 풀어보는 동전 2 문제는 동전 1 문제와는 다르게 최소한의 동전 "개수" 를 이용하여 K원을 만들어야한다. 동전 1 문제에서는 K원을 만들수 있는 동전
[백준] 동전 1
여러가지 시행착오가 있었던 문제였다. 각각의 동전을 이용하여 K만큼의 값이 나올수 있는 경우의 수를 구하면 되는 문제이다. 동전의 구성은 같지만 순서는 다른것도 포함될수있다는 말에 여러가지를 생각했는데 처음 생각했던것은 Permutation 방식이었다. 테스트케이스 까
[BACKJOON] 1463번 : 1로 만들기
문제 링크 : https://www.acmicpc.net/problem/1463정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때,
[Leetcode]198. House Robber
업로드중..You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopp
[ BOJ / Python ] 2482번 색상환
이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 점화식을 구하기 위해 각 n과 k에 대한 결과들을 정리해보았다. 그 결과 다음과 같은 점화식이 도출되었다.이 점화식을 통해 문제를 금방 해결할 수 있었다.업로드중..