[Python, C/C++] 백준 #1914 하노이 탑(재귀 함수)
재귀 함수를 배울 때, 가장 자주 사용하는 예제가 하노이 탑입니다. 하노이 탑의 이동 횟수는 다음의 점화식을 통해서 간단하게 구할 수 있습니다. \[ T(1) = 1 \] \[ T(N) = 2T(N-1) + 1 \] 위의 정화식을 풀면 \( T(N) = 2^N - 1 \) 이라는 것을 금방 풀 수 있습니다. 프로그램을 파이썬을 이용해서 작성해 보았습니다. 소스는 참고용으로 봐주세요. """ // baekjoon #1914 // - by Aubrey Choi // - created at 2019-07-23 """ def hanoi(n, a, b, c): if n == 0: return hanoi(n-1, a, c, b) print '%d %d'%(a,b) hanoi(n-1, c, b, a) a = raw_..
2022. 11. 3.
[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.
