PGR21.com
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
Date 2010/11/01 19:05:48
Name DeathMage
Subject C++ 알고리즘 질문입니다. (LCS 백트래킹 문제)
다이나믹 프로그래밍 기법의 LCS(longest common subsequence) 문제중 되추적 방법에 대한 질문입니다.

일단 LCS 테이블은 만들어졌는데, 이게 답이 하나면 쉬운데 답이 여러개일때가 문제가 됩니다.

예를들어서 가장 긴 수열이 5인데 그에 따른 답이 3개라던가.. 하는 식으로요.

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution

여기에 있는 의사코드(Reading out all LCSs)가 참조가 될꺼 같은데 봐도 무슨소린지 모르겠네요. R은 왜 있는건지;;


즉, 가장 긴 수열의 답이 몇개가 될 수 있는가를 구하고 싶습니다.

손으로는 풀 수 있는데 코드로 표현이 안되네요;;

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
꿀호떡a
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가지 경우의 수가 있겠네요. 매 번 세 가지 경우를 다 보아서 가능한지 보고, 그에 따라 재귀적으로 들어가면서 문자열을 완성하시면 됩니다.

일부러 좀 간단하게 적었는데 잘 이해가 안 가시면 더 자세히 써 볼게요.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
94321 헬스에 관해 해박한 지식을 가지고 계신 PGRer 분들께 여쭙니다~ [16] zzangdang2179 10/11/01 2179
94320 시스템복원을 하면 자료까지도 복구가 되나요? [4] 강아지1528 10/11/01 1528
94319 종교글 관련해서 언제쯤 운영진의 결론이 나옵니까? [1] Ben1520 10/11/01 1520
94318 중학교 수학과목 교육과정에 대해 궁금합니다. [6] 신인왕유창식1406 10/11/01 1406
94317 현대건설광고 [8] 올빼미1642 10/11/01 1642
94316 DVD R 이 노트북에서 읽히지 않습니다 ㅠ 강아지1121 10/11/01 1121
94315 엑셀을 익히려고 하는데 교재 추천좀 부탁드립니다. [3] 드라카1511 10/11/01 1511
94313 여자친구와 대구에서 당일치기로 갈만한 여행지+생일선물 [5] 루자티2894 10/11/01 2894
94312 여자분들한테 질문드릴게요 [27] Jolie2873 10/11/01 2873
94311 서울 쪽에 원룸을 구할려고 합니다. [12] 업매직1839 10/11/01 1839
94310 DSLR 질문입니다. 550D+50mm F1.8 vs D90+18-70mm F3.5-4.5 [5] 아나키1582 10/11/01 1582
94309 컴활 자격증에 대해서 몇가지 질문 좀 드릴게요! [2] Rukawa1649 10/11/01 1649
94308 C++ 알고리즘 질문입니다. (LCS 백트래킹 문제) [2] DeathMage3915 10/11/01 3915
94307 모니터 23인치랑 24인치랑 차이 많이 나나요? [5] 가아든2951 10/11/01 2951
94306 송년회 장소 문의 [1] 프린키피아1550 10/11/01 1550
94305 유게에서 본 동영상을 찾아요 ~ [3] Rx.Sirius1279 10/11/01 1279
94304 드라마'파스타'에서 이선균씨 목도리 [2] PGR끊고싶다1752 10/11/01 1752
94303 자게 뜨거운 눈물님의 그래픽카드 교체만으로 신세계가열렸다고 해서 적어봅니다 [9] BLACK-RAIN1761 10/11/01 1761
94302 비둘기를 어떻게 해야될까요? [2] 아싸리삐약~*1628 10/11/01 1628
94301 [급]서울 근교 드라이브 코스 추천 부탁드립니다!! [9] 베일2098 10/11/01 2098
94300 제주도(전국) 여행 질문드립니다. [1] 구하라1495 10/11/01 1495
94299 컴퓨터 부품 구매 관련해서 질문 드립니다. [8] 미소년1363 10/11/01 1363
94298 신입사원 재테크 질문입니다... [3] 담백한호밀빵1801 10/11/01 1801
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로