dp도 완전탐색 입니다. 다만 메모이제이션을 통해 같은 동작을 반복하지 않을 뿐이죠

DP까지 안가도 되고 그냥 쉬운 문제입니다. 쉽다는 걸 상기하면서 다시 한번 생각해 보시는것이..

@ljh6274 아 용어를 제대로 모르고있었네요ㅎ

@koosaga 백준님 dp 강의에 있는 문제이길래 dp가 어떤식으로 적용되어서 성능을 더 향상시키는지가 궁금해요ㅠ

아주 쉬운 n^2 풀이가 있고 n으로 줄일 수 있습니다. manacher algorithm을 dp라고 주장한다면야 dp로 줄인거긴 한데 음..

@koosaga n^2는 알겠습니다만 이 문제의 분류도 dp고 백준님 dp 강의 예제들중 앞쪽에 있는걸로 보아 꽤 간단한 dp 풀이가 있을거라고 예상했는데 그게 아닌건가요 ㅠ

1) 주어진 문자열의 길이가 n이라고 하면, n일 때 팰린드롬이 되는지 확인

2) 만약 주어진 문자열이 팰린드롬이 아니라면, n+1일 때 팰린드롬이 될 수 있는지 확인

-> n+1번째 문자는 1번째 문자와 같아야겠죠?

만약 n+1일 때 팰린드롬이 안된다면, n+2일 때 팰린드롬이 되는지 확인

-> n+2번째 문자는 1번째 문자와 같아야하고, n+1번째 문자는 2번째 문자와 같아야겠죠?

이 작업을 답을 찾을 때까지 반복하면 O(N^2)에 naive하게 구현할 수 있고, 조금 더 관찰하면 O(N)으로 줄일 수 있습니다.

@appa 감사합니다. 그런데 이 문제의 분류가 dp 인 이유가

n일 때 팰린드롬이 안되면 현재 문자열에서 맨앞에 한글자를 뺀 부분문자열에 대해 또 펠린드롬인지 확인하는 것이 

최적부분구조를 갖는 부분문제를 푸는 것이라는점에서 dp 라고 한것일까요..?

@appa 이런식으루여

음... 저는 dp라고 보여지진 않네요.

dp가 2가지 property(오버래핑 서브프로블럼, 옵티말 서브스트럭쳐)를 만족하는 method라고 배웠는데...

푼 방법에 따라 조금 생각이 다를 수 있겠어요.

dp라는 게 명확히 정의되어 있는 건 아닙니다. 놀랍게도 dp의 창시자도 그걸 정의한 적이 없습니다. 그렇기 때문에 뭐 말하기 나름입니다. 전 다익스트라를 dp라고 하는 사람도 봤어요 ㅋㅋ 다만 일반적인 기준은 존재하고 (appa님이 언급하신) 저 코드는 둘 다 사용하지 않았기 때문에 dp라고 하기 애매할 거 같네요.. 아니 dp라 할 수 없다고 말해도 괜찮을 거 같습니다.

Manacher Algorithm이라는 것도 있습니다. 스트링 S에 대해서, 각각의 중심에서 뻗어나가는 가장 긴 팰린드롬을 찾을 수 있습니다. 시간 복잡도는 O(N)이고, 이 알고리즘을 사용해 임의의 substring이 palindrome인지 O(1)에 알 수 있습니다. 구글에 검색해 보시면 자료가 좀 있을겁니다. Manacher Algorithm을 DP라고 주장하는 사람들이 많습니다. 저는 그렇게 생각하지 않습니다만은, 정해진 답은 아니고 생각하기 나름입니다.

백준님이 왜 DP라고 하셨는지는 잘 모르겠습니다. Manacher Algorithm보다 쉬우면서 O(n^2) 미만에 풀리는 dp 알고리즘이나, 지금 작성하신 알고리즘보다 쉬우면서 시간 안에 들어오는 dp 알고리즘은 전혀 모르겠네요.