알고리즘/백준 알고리즘
[BOJ] 1519 부분 문자열 뽑기 게임
문제 링크 www.acmicpc.net/problem/1519 모든 알고리즘 문제는 C++로 구현되어 있습니다. 다이나믹 프로그래밍 사용해 풀 수 있는 문제이다. 이 문제의 핵심은 크게 두 가지로, 첫 번째는 어떤 수의 진 부분 문자열을 구하는 것이고, 두 번째는 승패를 판정하는 것이다. 부분 문자열을 뽑아내기 위해 나는 입력값을 string으로 받아 substr() 함수로 부분 문자열을 뽑아내고, stoi() 함수를 이용해 int형으로 바꿔서 뺄셈했다. for (i = 1; i < len; i++) { // i : 부분 문자열의 길이 for (j = 0; j + i
[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번 경우도 마찬가지로 ..