:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
10/11/01 21:01
답이 여러 개일 때,
1. 가능한 문자열의 개수를 구하는 것이라면 굳이 되추적 방법을 사용하실 필요가 없습니다. 다이나믹 프로그래밍 기법을 사용할 때, '경우의 수' 컬럼을 따로 만들어서 같이 돌리면 됩니다. 조금 더 생각해보시면 아실 수 있으실 것 같아요. 2. 가능한 문자열을 모두 구하는 것이라면 백트래킹을 사용하셔야 할텐데, 다이나믹 테이블을 채울 때 D(i, j)가 어느 배열을 참조했는지를 같이 적어서, 그 경로를 따라 되추적하시면 됩니다. D(i, j)가 참조할 수 있는 경로는 3가지 있겠죠. D(i-1, j), D(i, j-1), D(i-1, j-1). 따라서 2^3가지 경우의 수가 있겠네요. 매 번 세 가지 경우를 다 보아서 가능한지 보고, 그에 따라 재귀적으로 들어가면서 문자열을 완성하시면 됩니다. 일부러 좀 간단하게 적었는데 잘 이해가 안 가시면 더 자세히 써 볼게요.
|