후회가 없도록

문제 출처: https://www.acmicpc.net/problem/6549 1. 결과 메모리 44580KB, 시간 3468ms 2. 풀이 우선 풀었을 때, 첫 플래티넘 문제라는 것이 신기하고 좋았다. 분할 정복법의 큰 틀에서 벗어나지 않은 형식인 것 같은데, 의외로 난이도가 있었다는 이야기 같다. 말한 대로 이 문제는 재귀를 통한 분할 정복법을 이용한다. 주어진 높이 리스트를 반을 가른 후, 그 반의 왼쪽에 있는 높이들 중에서 가장 큰 넓이, 반의 오른쪽에 있는 높이들 중 가장 큰 넓이, 그리고 가운데 선을 포함하여 가장 큰 넓이를 각각 구한다. 그리고 이 셋 중 가장 큰 넓이를 반환하면 된다. 왼쪽과 오른쪽의 높이들에는 다시 이 함수를 재귀로 적용시키면 된다. 이 문제의 등급을 플래티넘으로 올리는데..

문제 출처: https://www.acmicpc.net/problem/10942 1. 결과 메모리 60000KB, 시간 1816ms 2. 풀이 동적 계획법을 다루는 문제에서 팰린드롬(Palindrome)은 대표적인 예제 중 하나이다. ABA, ABCBA와 같이 앞에서 한 글자씩 읽어도, 뒤에서 한 글자씩 읽어도 같은 문자열이 되는 경우를 팰린드롬이라고 한다. 주어진 문자열에서 가능한, 가장 긴, 연속된 팰린드롬 문자열의 길이를 구하는 문제가 팰린드롬 관련 문제 중 가장 기초가 되는 문제이고, 그 외에 가장 긴 팰린드롬 자체를 구하는 문제나 이 문제처럼 팰린드롬의 여부를 묻는 문제도 있다. 여기서 말한 다른 팰린드롬 문제는 블로그에 알고리즘 풀이를 기록하기 이전에 풀어봤기 때문에 아직 없지만, 추후에 특정..