밤이 블로그

BOJ#1010 다리 놓기 * 문제https://www.acmicpc.net/problem/1010 * 풀이풀이 #1. 조합이 문제는 단순히 M개의 사이트 중에서 N개를 고르는 경우의 수를 구하는 문제입니다. 조합 : mCnmCn = m! / {(m-n)! * n!} 풀이 #2. 동적계획법dp[N][M] : 사이트가 각각 N개, M개일 때, 주어진 조건에 맞게 다리를 건설할 수 있는 경우의 수dp[N][M] = dp[N-1][M-1] + dp[N-1][M-2] + ... + dp[N-1][N-1] * 나의 코드https://github.com/stack07142/BOJ/blob/d8bb015604a276ecd8643e16c9ae052c2c36a2fa/BOJ%231010_BuildBridge/src/Mai..

BOJ#11729 하노이 탑 이동 순서 * 문제https://www.acmicpc.net/problem/11729 * 풀이 처음에는 bfs + 비트마스크를 이용하여 풀었습니다.하노이탑의 각 상태를 비트마스크를 이용하여 long 정수 하나로 구현하고, bfs 탐색을 해가면서 목표 정점을 찾는 방식(각 원판은 3개의 장대 중 하나에 존재할 수 있으므로 원판의 위치는 2비트로 표현할 수 있습니다.) 그러나 정점의 최대 개수가 3^20이고, 각 정점마다 3^2 loop를 통해 탐색을 하므로총 시간복잡도 3^22로 시간초과 발생합니다. , - 분할 정복법 : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하고, 그 결과들을 합병하면서 본 문제를 해결하는 방식- 단점 : 보통 재귀 방식으로 구현되는데, 재..