[C/C++] 백준 #1890 점프(동적 계획법)
이번 문제는 동적 계획법을 이용해서 풀었습니다. 사실 동적 계획법이 아니라 너비 우선 탐색(BFS)를 사용해도 같은 결과를 얻을 수 있습니다. 그렇지만 단순 반복문을 사용할 수 있는 동적 계획법에 비해서 효율이 떨어지게 되겠죠. 동적 계획법 알고리즘은 간단합니다. \(d_{i, j} \)를 시작점에서 \((i, j)\)로 가는 경로의 개수라고 한다면, 1. NxN 공간을 0으로 초기화합니다. \( d_{i, j} = 0 \) 2. 시작점을 1로 놓습니다. 즉, 시작점에서 시작점으로 가는 경로는 한가지입니다. \(d_{0, 0} = 1\) 3. 시작점에서부터 오른쪽 방향 우선으로, 아래로 이동하면서 갈 수 있는 모든 곳 \(d_{i+a_{i, j}, j}\) 값과 \(d_{i, j+a_{i, j}}\) 값..
2022. 11. 1.
[C/C++] 백준 #1874 스택 수열(스택)
이번 문제는 스택에 대해서 잘 이해를 해야 합니다. N의 숫자가 주어지고, 스택이 하나 주어졌을때, 1부터 N까지의 숫자를 차례로 스택에 Push할 수 있고, 스택이 비어있지 않는다면, 언제든 Pop을 한다고 했을 때, 우리는 1부터 N까지의 숫자가 한번씩 사용이 된 수열을 얻게 됩니다. 예를 들어서 Push 1, Push 2, Push 3, Push 4, Pop, Pop 을 하면, 4와 3이 출력되게 되고, Push 5, Push 6, Pop 하면 6을 출력하게 됩니다. Push 7, Push 8, Pop, Pop, Pop, Pop, Pop, Pop 하게 된다면, 8, 7, 5, 2, 1 이 나오게 되어 최종적으로 4, 3, 6, 8, 7, 5, 2, 1 이라는 수열을 얻게 됩니다. 이번 문제는 바로 ..
2022. 10. 31.
