코드저장소

최근 동적계획법 문제가 약한것 같아 다시 해당 단계를 풀어보는 중이다. 이번 문제는 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하는 문제이다. 점화식을 만드는데 꽤 애를 먹었는데 어떻게 풀었는지 정리해보고자 한다. 점화식이 가장 중요하다. 이번 문제에서의 핵심은 점화식을 어떻게 만드느냐였다. 처음에 점화식을 어떻게 만들지를 생각하지 못해서 꽤 애를 먹었는데 결국 핵심은 어떤 정수를 1,2,3의 합으로 나타내는 방법이므로 만드는 숫자는 3개로 한정된 것이 핵심이였다. 우선, 초기값으로 1,2,3에 해당하는 값인 1,2,4를 dp배열에 넣어두었다. 그 후, 4 이상의 값은 n-3,n-2,n-1을 모두 더한값과 같게된다. 무슨 말인지 잘 이해가 안되니 4와 5..

이제 동적 계획법도 얼마 남지 않았다. 이번 문제는 양 쪽의 전봇대에 전깃줄이 교차하지 않도록 없애야 하는 전깃줄의 최소 갯수를 출력하는 문제이다. 점화식을 어떻게 만들지가 좀 어려운 문제였는데 어떤 식으로 풀었는지 살펴보자. 어떻게 구해야 할까? 이번 문제의 핵심은 점화식을 어떻게 만들것인가가 핵심이었다. 처음 생각했을때는 1차원 배열 2개를 만들어 각각의 전봇대의 숫자를 넣은 후, A 전봇대를 기준으로 하여 반복문을 돌린 후 B 전봇대의 값이 이전 인덱스의 최대 값 보다 높으면 카운트를 추가하는 형식으로 구현하려고 하였다. 예를 들어서 예제를 기준으로 보자. 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 8 2 9 1 4 6 7 10 A 전봇대를 기준으로 하면 다음과 같이 ..

이번 문제는 각각의 집을 RGB중 하나로 칠한다고 할때, 규칙을 만족하면서 비용의 최솟값을 구하는 문제이다. 핵심은i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다라는 조건을 어떻게 구현할 것인지 였는데 어느정도 동적계획법에 익숙해져서 인지 아니면 문제가 쉬웠던 건지 조금 생각해본 후에 간단하게 풀어 낼 수 있었다. 그럼 어떻게 풀었는지 되짚어 보자. 규칙은 무엇인가? 우선 입력값을 보면 딱 봐도 2차원 배열 형태로 저장해야 할 것 같은 느낌이 든다. 예제 입력 1을 기준으로 살펴보자. 나는 이번 동적계획법을 2차원 배열을 사용하여 구현했다. 우선 각각의 값을 기록하기 전 초기 상태는 다음과 같을 것이다. 0 1 2 26 40 83 당연히 0번 index에는 첫행이 ..

이번 문제는 특정 수열 A가 주어 졌을때, 가장 긴 증가하는 부분의 수열길이를 구하는 문제이다. 나는 Top-Down 방식으로 구현하였는데 어떤 부분에서 잘못 생각을 했고 어떻게 풀어 냈는지 살펴보자. 문제를 살펴보자! 문제 자체는 사실 비교적 간단해 보인다. 가장 작은 값과 가장 큰 값을 찾은 후 둘 사이의 값이 몇개인지만 찾아내면 되기 때문이다. 간단하게 표를 만들어 살펴보자. 0 1 2 3 4 5 10 20 10 30 20 50 1 2 1 3 2 4 각 값을 들어온 순서대로 배열에 담는다면 위와 같이 담기게 될 것이다. 그렇다면 10~50 사이에는 10, 20, 30, 50이라는 4개의 값이 들어오기 때문에 최종적으로 가장 긴 배열의 길이는 4이다. 중간에 같은 값이 껴있더라도 어차피 최소 숫자 ~..

이번 문제는 동적 프로그래밍을 이용하여 배낭에 넣을 수 있는 최대 가치 값을 찾아내는 문제이다. 골드 난이도 답게 난도가 좀 있었는데 혼자서 이리저리 짜보다가 생각처럼 잘 되지 않아 ChatGpt의 도움을 약간 받아 해결하였다. 그러면 어떻게 문제를 풀었고 어디가 문제였는지 살펴보자. 무엇이 반복되는가? 이전 글에서도 서술 했지만 동적 계획법의 핵심은 반복되는 요소를 기록하여 시간을 단축시키는 것이다. 그러면 무엇이 반복되는 것이고 그것을 어떤 방법으로 기록할 것인지가 핵심이 되겠다. 문제는 배낭의 넣을 수 있는 물건들의 최대 가치값만을 요구하고 있기 때문에 안에 몇개가 들어가는지, 몇종류가 들어가는지는 중요하지 않다. 즉, 배낭에 무게별로 들어가는 가치합이 반복되는 요소가 될 것이다. 그럼 남은 문제는..

이번 문제는 동적 프로그래밍을 이용하여 피보나치 수열을 풀어보는 문제이다. 기존에 재귀를 이용하여 피보나치 수열을 계산하는 것을 해보았지만, 이번에는 동적 프로그래밍을 이용하여 더 빠르고 효율적인 프로그래밍을 하는것이 목적이다. 그럼 우선 동적 계획법에 대해서 자세하게 살펴보자. 동적 계획법(Dynamic Programming) 이란... 동적 계획법(줄여서 DP라고 부르기도 한다.) 을 간단하게 설명하면 답을 재활용하는 것이다. 좀 더 본질적인 의미를 살리자면 기억하며 풀기라고 생각해도 되겠다. 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거의 구한 해를 활용하는 것이 동적 계획법의 핵심이다. 문제를 작은 문제로 쪼개어 생각한다는 점에서 분할 정복 알고리즘과 비슷하게 보이기..

이번 문제는 주어진 테스트 케이스의 각각의 경우의 수를 출력하는 문제이다. 위 문제를 풀기 위해서는 이항 계수를 이해할 필요가 있는데 수학을 조금 아는 사람이라면 로직 자체는 어렵지 않기 때문에 금방 풀 수 있을 것이다. 하지만 나는 수학에 손을 놓은지 꽤 된 터라... 문제를 이해하는데 꽤나 애를 먹었다. 그러면 이항계수가 무엇이고 이를 이용하여 어떻게 문제를 풀어야 하는지 알아보자. 이항 계수(Binomial Coefficient)란? en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient - Wikipedia en.wikipedia.org 이항 계수에 대한 정확한 개념은 위 글에 잘 정리가 되어있다. 이항계수란 주어진 크기의 집합에서 원하는..