Min IT's Devlog

풀이 일자: 23.04.14 난이도: [Medium] 분류: [DP] 문제 내용 s가 주어졌을 때 해당 s의 subsequence 중 가장 긴 회문의 길이를 구하는 문제이다. subsequences > 0개 이상의 원소를 삭제함으로써 반들어지는 substring으로 보면 된다. 회문 > 앞으로 읽어도 뒤로 읽어도 똑같은 것을 의미한다. ex)기러기.. 문제 해결 흐름 1. 처음 이 문제를 보고 떠오르는 알고리즘은 two-pointer나 DP정도뿐이었다. → 그 이유로는 전체를 일단 쪼개서 작은 것부터 처리하고 점차 붙여나가면서 답을 만들어가는 해결방식뿐이었다. dp[i][j] = i ~ j번째의 문자를 이용하여 만들 수 있는 최대 회문의 크기 dp[i][i] = i ~ i번째의 문자를 이용하여 만들 수 ..