다이나믹 프로그래밍 문제이다.       처음 생각했던 접근방식(오답) 간단한 DP문제일 것이라고 생각하고 익숙한 방식대로 생각했었다.예를 들어서 11은 3^2 + 1^2 + 1^2, 즉 3이 최소 항의 개수이고 1^2 + 1^2은 2의 최소 항의 개수인 2다.13은 3^2 + 2^2 + 2^2, 즉 3이 최소 항의 개수이고 2^2 + 2^2은 4의 최소 항의 개수인 2이다. 따라서 11에 가장 가까운 제곱수를 찾은 후 (FindMinSquare), -> 항 1개구하려는 N에서 그 제곱수를 빼고 나머지는 memoization을 활용하면 된다고 생각했었다. -> dp[i-pow(minSquare,2)] 그리디 + DP 방식이였는데 이 방식은 틀렸다. 최대 제곱수를 선택하는 방식이 항상 최적의 해를 보장하지..

다이나믹 프로그래밍 문제이다.         합당한 접근방식 이 문제도 처음 봤을 때 식을 어떻게 써야할지 난감했다.후회되는 점은 N=3인 케이스부터 적어서 패턴을 찾는데 시간이 오래걸렸다.오히려 N=1, N=2, N=3.. 차근차근히 케이스를 써내려갔다면 풀이에 근접했을 수도 있었다.. 1. N=1 이라면1, 2, 3, 4, 5, 6, 7, 8 ,9 가 가능하다. 2. N=2 라면10, 21, 32, 12, 43, 23, 54, 34, 65, 45, 76, 56, 87, 67, 98, 78, 89.....옆 자리수와 1이 차이나야 한다. 여기서 섬세하게 바라보면,- 마지막 수가 0이면 왼쪽에 있는 수는 무조건 1 - 마지막 수가 9라면 왼쪽에 있는 수는 무조건 8 이어야 한다. (물론 두자리 수에서는 ..

0-1 BFS문제이다.        처음 생각했던 접근방식 처음에는 다이나믹 프로그래밍 방법을 생각했다.그 이유는 N과 K가 범위가 큰 상황에서 3가지 이동정보 (앞, 뒤, 2배 점프)를 고려하여최소 이동거리만 DP에 업데이트하면 될 것이라 생각했기 때문이다.그러나 일반적인 단방향 DP로 코드를 구성했을 때의 문제점은 N이 K보다 큰 상황일 때와 같은 양방향을 생각하기 복잡해지는 것이다. 그래서 보다 효율적인 풀이가 있을까 해서 다른 사람들의 풀이를 참고하였는데, 대부분 0-1 BFS라는 알고리즘을 사용하였다.BFS는 알고있지만 앞에 "0-1" 이 붙어있는 이유는 뭘까, 처음 접한 방법이라 호기심을 갖고 공부하였다.  "0-1" BFS란 가중치가 0과 1로만 이루어져 있는 그래프에서 최단경로를 찾고자할 ..

다이나믹 프로그래밍 문제이다. 처음 생각했던 접근방식 이 문제 전에 "백준 15989번: 1,2,3 더하기 4" 문제를 풀어서 그런지 다이나믹 프로그래밍으로 풀어야겠다는 생각을 했고, 어렵지 않게 수기로 논리적인 흐름을 작성할 수 있었다. 정보를 가진 shortcut 배열(도착 기준)에 여러개의 지름길을 넣고 차례대로 순회하며 지름길이 없을경우 현재 거리는 이전 거리+1 지름길이 있는 경우 여러개의 지름길을 확인하며 중 최솟값을 저장한다. 그러나 예상치 못한 결괏값으로 당황했는데, 터무니 없는 큰 숫자가 리턴되는 것이였다. 초기화가 이상하게 된 것이었다. Memset 함수 사용시 주의점 memset 함수는 void* memset(void* ptr, int value, size_t num)으로 value ..

다이나믹 프로그래밍 문제이다. 처음 생각했던 접근방식 다이나믹 프로그래밍 문제에 아직 익숙하지 않아서인지, 처음 이 문제를 보았을 때 어떻게 접근해야할지 바로 떠오르지 않았다. 조합과 관련된 문제라 생각하여 DFS를 먼저 떠올렸지만, 1+2와 2+1은 같다고 보는 조건과 n은 10000이하라는 조건 때문에 O(n^2)의 시간복잡도를 가지는 DFS의 방식은 올바른 방법이 아니라는 것을 깨달았다. 그렇다면 다이나믹 프로그래밍 문제인건 알겠는데, 항상 식을 어떻게 작성해야하는지 감이 잡히질 않았다. 그래서, 힌트를 보았다. 1. 중복을 피하기 위해 오름차순으로 정렬하여 생각한다. 2. dp[i][n]: i라는 숫자를 만들기 위해 1~n까지의 숫자를 사용한 개수라고 정의한다. 힌트를 보고나니, 어떻게 풀어야하는..