오늘도 리트코드 추천문제 중 하나인 문제를 풀어보았다. 문제는 꽤 간단한데 strs 라는 벡터안에는 0 과 1로만 이루어진 스트링이 있다. 그리고 m 과 n 은 0 과 1 이 허용되는 최대의 숫자를 의미하는데. 이 허용범위 안에서 가장 길게 만들수있는 subset의 길이를 리턴하면 된다.
이 문제에서 중요한 점은 탐색을 하는 과정에서 굉장히 많이 중복되는 탐색을 하게 됨으로서 DP 의 개입이 필요하게 된다. 이 문제는 전형적인 KnapSack 문제이며 선택하냐/선택하지 않냐의 길로 나뉘게 된다. 사실 벨로그에도 이런 유형의 문제를 많이 풀어봐서 꽤 자신있게 풀어봤지만 좀 많은 의문점을 만든 문제이기도 하다. Bottom Up 과 TOP DOWN 을 모두 시도해봤고 내가 처음에 시도했던 Bottom Up 방식은 틀린답이 나와서 다른 사람의 풀이를 참고했다.
먼저 DP벡터를 만들때는 그냥 1차원 벡터가 아닌 0과 1의 숫자에 따른 값이 다 다르기 때문에 3차원 벡터를 만들어 주었다. Knapsack 문제에서 capacity 와 weights 에 따라서 DP벡터가 3차원이었듯이 비슷학 만들었다. 여기서 내가 의문점이 들었던거는 굳이 if 와 else 스테이트먼트가 필요하나 였는데 아직까지도 좀 의문이 든다.
이게 두번쨰로 푼 방식이고 이 유형은 구종만의 알고리즘 문제 해결 전략에 나온 방법이랑 정말 유사하다. 먼저 ret 로 index의 끝에서 부터 시작하고 특정 조건에 따라서 탐색을 한번씩 더 해주다 보면은 최대값을 리턴할수있다.
난 아직 DP에 대해 이해도가 살짝 아쉬운 느낌이여서 더 배워야겠다고 다짐이 드는 문제였던거같다.
배운점:
1. 비슷하지만 다른 문제 풀이 형태의 DP 도 다시 봐보자
2. 다 똑같은 문제가 아니기에 신중할것.
