문제1509번: 팰린드롬 분할 (acmicpc.net) 풀이팰린드롬 확인문자열을 팰린드롬으로 분할하기 위해서는 우선 분할된 문자열이 팰린드롬인지 확인해야 합니다. `isPalindrome[start][end]` 를 이용하여 주어진 문자열의 start번 부터 end번 까지가 팰린드롬을 이루는 지 `true`, `false`로 판단하여 저장하겠습니다. start부터 end까지 팰린드롬을 이루기 위한 조건이 무엇이 있을까요?가장 먼저 문자열의 start 번과 end번의 문자가 같아야 합니다. 그 다음은 start +1 번 문자부터 end -1 번 문자까지의 문자열이 팰린드롬을 이루면 됩니다.다시 말해, `isPalindrome[start+1][end-1] = true` 이어야 합니다. 즉,isPalindrom..
백준/다이나믹 프로그래밍
문제 2186번: 문자판 (acmicpc.net) 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 풀이 문자판을 십자 방향으로 DFS 탐색하며 DFS 탐색의 깊이가 영단어의 길이와 일치할 때 주어진 영단어와 일치하는지 확인하는 작업이 필요합니다. 하지만 DFS 탐색만으로 해결하려 한다면 불필요한 경우도 중복 탐색하게 되어 연산 시간이 오래 걸리게 됩니다. 중복은 다이나믹 프로그래밍으로 줄일 수 있습니다. DFS 탐색을 한다면 메모이제이션으로 불필요한 재귀 호출을 줄일 수 ..
문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 메모리 M 이상을 확보하기 위해서 필요한 비용의 최소값을 구해야 하는 문제입니다. 즉, 메모리 M 이상을 확보하기 위해 앱을 비활성화 했을 경우의 수들 중에서 비용의 최소값을 구해야 합니다. 문제를 그대로 받아들이고 해결하려 한다면 상당히 어렵습니다. 문제를 재정의 해보죠. 메모리의 관점이 아닌 비용의 관점으로 생각해봅시다. 그렇다면 발생할 수 있는 상황들을 비용이 K 일때 확보할 수 있는 메..
문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 팰린드롬이란 거꾸로 읽어도 제대로 읽은것과 같은 문장이나 숫자, 문자열 입니다. 단순하게 탐색한다면 주어진 S, E 범위의 숫자열을 하나하나 비교하며 팰린드롬인지 아닌지 확인할 수 있지만 이 방법은 최대 2,000 * 1,000,000으로 제한시간내에 해결이 불가능합니다. 그래서 다른 방법이 필요한데요 우선, 각 범위에 대해서 팰린드롬인지 아닌지 미리 계산 후 범위가 주어졌을 때 출력만 하는것이 좋아보입니다. 다시 말하면 2..
