문제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..
DP
문제 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 일때 확보할 수 있는 메..
배낭 문제 N 개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지고, 해당 물건을 배낭에 넣으면 V 만큼의 가치를 얻는다.최대 K 만큼의 무게만을 넣을 수 있는 배낭이 있을 때, 배낭에 넣을 수 있는 물건들의 가치의 최대값을 구하여라. 위의 문제가 배낭 문제 입니다.문제의 상황이나 디테일한 부분은 달라질 수 있겠지만 대게 가중치 W 와 값 V 가 주어지고 가중치의 합이 K를 넘지 않도록 물건들을 조합하여 V의 합이 최대가 되도록 구하는 문제로 정의할 수 있습니다. Fractional Knapsack Problem주어진 물건들이 분할 가능한 경우입니다. 물건들이 분할 가능하기 때문에 무게당 가치를 계산하여 높은 순서대로 배낭에 넣으면 K 까지 넣었을 때의 가치가 최대값 입니다.즉, 그리디 알고리즘..
