사부작사부작해요

주어진 문자열에서, 패턴(=폭발 문자열)과 일치하는 부분 문자열을 모두 삭제하는 문제이다. 문자열에 일치하는 패턴이 없을 때 까지 계속 반복한다. KMP로 풀어서 제출하면 시간초과로 통과하지 못한다. 패턴에 반복/공통되는 문자열이 없기 때문이다. 다른분들 풀이를 확인했는데, 스택을 많이 사용하더라. 폭발 후 문자열을 연속해서 폭발시킬 수 있어 논리가 단순해 스택을 많이 사용하는 것 같다. 왜 KMP가 안되는지, 왜 스택을 사용했는지, 특히 str 타입이 아니라 list 타입을 써서 해결한 이유는 뭔지 알아보자. KMP로 풀었을 때 문제를 다시 읽다보니, 조건에서 KMP로 풀지 말라고 알려주고 있었다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. KMP는 패턴에 공통 문자열이 많을수록 효과적인..

배낭문제 계속 메모리초과가 난다. 어떤부분이 잘못됐는지 모르겠어서 알아보려고 한다. 1. 문제 정의 배낭에 넣는 물품은 무게 w와 가치 v를 갖는다. n개의 물품에서 총 v의 합이 최대가 되도록 선택하여 배낭을 채운다. 배낭은 weight_possible만큼의 무게를 견딜 수 있다. 물품을 중복해서 선택할 수 없다. 2. 아이디어 Full binary tree로 표현할 수 있다. 각 노드는 배낭에 담긴 물품의 총 w와 v를 저장하며 왼쪽 자식은 각 물품을 포함하는 경우, 오른쪽 자식은 포함하지 않는 경우로 나타낼 수 있다. 물품의 무게를 배열 w에, 가치를 배열 v에 저장할 때 레벨 k와 k+1의 노드는 다음 그림과 같이 표현한다. 트리의 레벨은 0부터 시작하여 n까지 존재하며, 가능한 모든 경우는 리프..