amok   1년 전

DAG를 트리에 embedding 하는 방법의 수를 찾는 문제인 것 같네요

embedding이란 표현이 적절한지는 모르겠는데, 노드 N(<=50) 개짜리 트리의 서브그래프 중 주어진 DAG와 동형인 것의 개수를 찾아야 할 것 같은데... 

graph isomorphism 문제가 아마 NP-완전 이었나요? 뭔가 그런 문제랑 관련 있을 것 같은데... 그래서인지 문제 사이즈도 굉장히 작네요.

이 문제는 가능한 방법의 수를 찾는 문제인데, 이것보다 더 쉬운 가능한지 아닌지 (YES/NO) 찾는 문제조차도 푸는 방법을 모르겠네요.

근데 이 문제 출처가 어디죠... 메탈은 뭐고 이강토는 누구고 와치아웃 레코드는 뭐지...

아 역시 아무도 못 푼 문제 같은거 건드리는게 아니었어 어제부터 몇시간째 계속 고민하지만 방법은 모르겠고 아아아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ 죽고싶다

zlzmsrhak   1년 전

조건이 8개밖에 없다는 것을 이용하면, 순서를 고려해야 하는 카드 수는 16개 정도만 필요하겠네요.

아마 카드를 0번지부터 배열하면서 2^16 DP를 돌리면 될 것 같은 느낌이 드네요.


제가 문제만 읽고 답글을 다는 것이기 때문에 이 방법으로 풀리지 않을 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.