알고리즘
[BOJ] 5502 팰린드롬
문제 링크 www.acmicpc.net/problem/5502 모든 알고리즘 문제는 C++로 구현되어 있습니다. 주어진 문자열과 이를 뒤집은 문자열의 LCS를 구한 뒤, 전체 문자열 길이에서 이를 빼주면 답을 구할 수 있는 문제이다. 방법을 알면 구현 자체는 쉽지만, 방법을 떠올리기가 어려워 애를 먹었던 문제였다. 한번 경험해봤으니 다음에 비슷한 문제가 나오면 LCS로 접근을 해봐야겠다. #include #include #include using namespace std; int dp[5000][5000]; int main() { int i, j, n; string s, sRev; cin >> n >> sRev; s = sRev; reverse(sRev.begin(), sRev.end()); for (i..
[BOJ] 15999 뒤집기
문제 링크 www.acmicpc.net/problem/15999 모든 알고리즘 문제는 C++로 구현되어 있습니다. 격자판의 초기상태로 가능한 경우의 수는, 눌러서 최종 상태로 갈 수 있는 격자의 수를 n이라 하면 2^n가지가 나올 수 있다. 이러한 격자를 누를 수 있는 격자라고 해보자. 누를 수 있는 격자의 수는 어떻게 구해야 할까? 최종 상태의 격자판에서 두 개의 격자가 배치되는 경우의 수를 생각해보자. - 1번 경우에서는 다른 상태에서 A를 눌러 이 상태로 올 수 없다. A가 B와 같은 검은색이었다면 A를 눌렀다면 B도 같이 하얀색으로 변했을 것이고, A가 하얀색이었다면 A를 눌러서 검은색으로 바꾸고, 다시 눌러서 하얀색으로 바꿀 때 B도 같이 하얀색으로 바뀌기 때문이다. - 2번 경우도 마찬가지로 ..
[BOJ] 11444 피보나치 수 6
문제 링크 www.acmicpc.net/problem/11444 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제는 일반적인 재귀함수로 풀면 시간 초과를 받고, 메모이제이션을 적용하려 해도 메모리 제한에 걸리게 된다. 이 문제는 피보나치 수를 행렬로 생각하고, 행렬의 거듭제곱을 이용해서 풀어야 한다. 현재 피보나치 수와 이전 수를 각각 1행, 2행에 배치한 2X1 행렬을 생각해보자. 이 다음 피보나치 수를 구하려면 두 수를 더한 수를 첫 번째 행에, 기존에 첫 번째 행에 있던 현재 피보나치 수는 두 번째 행으로 옮겨줘야 한다. 이런 동작은 아래와 같은 행렬 곱셉으로 간단하게 수행할 수 있다. 현재 피보나치 수가 1, 이전 피보나치 수가 1이라고 했을 때, 행렬 [[1 1], [1 0]]을 곱해주..