왜 최적화 하지 못했을까?🤔
이번 문제는 사실 완전 탐색으로는 해결했지만, 어떻게 메모이제이션을 적용할지 모르겠어서 결국 풀이를 본 문제였다. 그래도 종만북 공부하고 나서는 dp, 완전탐색 문제들을 어떻게 풀어야 할지는 조금은 보인다는 점에서 아주 다행이라고 느꼈다. 하지만 이런 메모이제이션을 적용하는 부분이나 이것을 위해 점화식을 다듬는 능력이 부족하다고 느꼈다.
먼저 풀이를 떠올린 과정은 이러하다.
조건 4개를 살펴 보면
1. 문자열의 어떤 위치에 어떤 문자를 삽입 (시작과 끝도 가능)
2. 어떤 위치에 있는 문자를 삭제
3. 어떤 위치에 있는 문자를 교환
4. 서로 다른 문자를 교환 (한 번만 가능함)
마지막 조건이 너무 수상하다..! 그래서 먼저 조합을 만들고 4번 연산을 한 뒤에 나머지 연산을 구현하는 방식으로 해야겠다는 풀이가 떠올랐다.
그리고 나머지 3조건에 대해서 각각 점화식을 작성했다. 나는 분명 인자로 first와 end인덱스를 따로 넘겨주었으면서도 계속해서 오른쪽 end 인덱스에 추가를 하거나 교환하는 방법으로 풀어나갔다. 그렇게 되면 완전탐색을 하면 결국에는 찾겠지만, 이 부분에서 메모이제이션을 하지 못하게 되었고 계속해서 맞는 답이 나오니 다른 방법을 생각하지 못하게되었다...
어떻게 메모이제이션을 할까?📚
결국 풀이를 보았는데 정말 깔끔하게, 심지어 문자열을 수정도 안하고 풀 수 있었던 문제였다. 나는 추상화가 덜 되어서 문자열을 수정한 다음에 직접 first인덱스와 end인덱스를 추가하는 방법으로 풀어 나갔다. 하지만 조건을 자세히 보면 삽입 조건과 삭제 조건은 인덱스를 옮기는데에 동일한 역할을 하고 있다.
고로 나처럼 first 인덱스를 고정시키고 움직이면 메모이제이션을 할 수 없지만
ret = min(ret, factory(left+1, right) + 1)
ret = min(ret, factory(left, right-1) + 1)
왼쪽 오른쪽을 모두 고려할 수 있게 된다.
그리고 교체 연산은 사실상 두개가 같아지는 것이기 때문에 이렇게 해결이 가능하다.
ret = min(ret, factory(left+1, right-1) + 1)
나는 재귀를 호출할 때 팰린드롬이 아닌 인덱스가 나올 때까지 first 인덱스를 더하고 end 인덱스를 빼는 작업을 했기 때문에 굳이 string을 수정하지 않고서도 인덱스로만 나타 낼 수 있게된다.
아직 갈 길이 멀구나👨🏻💻
그래도 종만북 보기전에 이 문제 보고선 아예 아무것도 할 수 없다는 것을 많이 느꼈었다. 진짜 감도 안오고 뭘 어떻게 하라는 거지..? 라는 생각만 들었지만 그래도 최소한 완탐으로 풀 수 있었다는 것에 감사함을 많이 느낀다.
하지만 아직 갈길이 멀다는 것을 느끼는 문제였다. 최소한 지금의 풀이를 개선해서 다른 시각으로 문제를 더 간결하게 보는 능력이 필요하다고 느껴졌다. 문제를 좀 다양하게 풀면 이런 실력이 좀 늘어날 텐데, 아직은 구현도 벅차하는 나에게 어려운 문제들을 완벽하게 하나 하나 완벽하게 다져나가야겠다.
내 파이썬 코드이다.
https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_1053.py
