만약 예를들어서
1, 2, 3, 4, ,5 ... n 개의 공이 있어
근데 1번 공을 고르면 2, 5, 6..의 공을 고를 수 없고
2번 공을 고르면 3 ,12, 1, 5 ...의 공을 고를 수 없어
이렇게 n개의 공마다 조건이 붙어 있는 상태에서
최대한 많은 공을 고를려면 으떠케 풀어야대??
단, 선택할 공과 그 공과 같이 고를 수 없는 공 사이의 관계는 없어.
어디 뭐 문제 풀려고 여기 가져온게 아니라 갑자기 생각나서 쓴 글이야.
알려주면 고맙겠엉!
26개의 댓글
무분별한 사용은 차단될 수 있습니다.
STM8a
차고보
STM8a
STM8a
백트래킹으로 풀면될것같음
7ebf0a9aᅟᅟᅟᅟ
차고보
렙 개드리퍼
차고보
HIGH SIERRA
비트마스크(또는 string key) + 메모이제이션쓰면 될듯
1뽑고 1을 뽑은뒤 가능한 것들에 대해 다 뽑음.
2도 뽑을 수 있으면 2뽑은 뒤 가능한 것들에 대해 다 뽑음.
뽑을 수 없는데까지 간 뒤 다시 버퍼를 비우고 2부터 다시 뽑음
이미 구해져있다면 구해진 값을 사용
간단한 예시로 공 8개중에 1,2,5,6을 뽑았고 더이상 뽑을게 없다면
m[11001100] = possible
이렇게 나타낼 수 있음
자료구조는 해시맵 같은거 쓰면 될거같고
1에선 2가 안되고 2에선 1이 되고 이런규칙이 생기면 다른 방법을 써야 할 듯
차고보
이건 당연하다 생각 했었어 근데 그런 조건을 넣을수도 있겠네
그리고 n을 그래도 1000?개 정도 생각하고 있었어...
HIGH SIERRA
n이 천이어도 저건
공간복잡도 n^2이니깐
백만
djd
여기서 비트DP를 밀고 나가서 최적화를 더 하면 2^(n/2)까진 될 거 같긴 한딩...
HIGH SIERRA
4edg587
규칙이 점과 점에 선분이 놓아져잇다하면
최대한 많은 점을 잇는 문제임
한붓그리기 또는 다리건너기로 찾아보면 될듯
문제는 1번점은 3번점으로 이어지는데
3번점은 1번으로 안이어진다던가 이런 일방통행규칙이 어려운 부분이 될것같음
아니면 한점에서 다른점으로 가는 출발의 가짓수가 아닌
각 지점마다 다른 점에서 오는 가짓수를 배열하면 왠지 간단하게 답이 나올것같은 직감이 든다
차고보
머학띵소
차고보
머학띵소
차고보
머학띵소
정확하게 문제가 어떻게 나왔는지 궁금한데....
djd
정답 = 부분 그래프 중에서, 가장 큰 완전 그래프의 크기
이렇게 되는데,
부분 그래프 중에서 완전 그래프 = Clique 라고 부르고, 여기에 대한 이것저것들이 있음.
가장 큰 clique를 찾는 게 가장 큰 이슌데, 위키 주소 남김.
https://en.wikipedia.org/wiki/Clique_problem
근데 플로우, MCMF로 할려고 했는데 증명이 계속 삑나서 보니까 별다른 조건 없이, 최대 clique를 찾는 건 NP라는 것 같음.
----
반대로 1,2를 동시에 고를 수 '없을 때', 1-2를 연결하는 식으로 생각할 수 도 있는데(결국 똑같은 얘기니까 이것도 NP겠지만)
조건을 좀 더 넣어서 다항시간으로 가능하게 만든 버전은 ACM 한국 대회에 나온 적 있음.
조건은 1->3, 3->4 이 있을 경우, 1->4도 있는 것.
http://weeklyps.com/entry/BOJ-8898-%EC%8A%A4%ED%8F%AC%EC%B8%A0-%EC%A0%84%EB%AC%B8-%EC%B1%84%EB%84%90-GSK
차고보
근데 아까 지워서 말은 안했는데 이분 뭐시기? 용어좀 다시 알려줄수 있어?? 궁금하자너
djd
이분 그래프에 대해서 네트워크 플로우 돌리는 걸 이분 매칭이라고 함.
저기 링크 걸어둔 acm 한국 대회 문제의 경우엔 이분 매칭으로 풀림.
네트워크 플로우에서 시간복잡도는 늘어나지만, 더 많은 문제를 풀 수 있는 방법 중에 MCMF도 있음.
NP가 아닌, 대부분의 그래프 문제는 MCMF로 다 풀린다는 속설이 있을 정도로 강력함.(시간복잡도를 다항시간인 것만 신경쓰면..ㅎㅎ)
저 문제 생각나서 이것도 이분매칭or MCMF로 될 줄 알았는데 증명 해놓고, 그 다음에 반례나와서 지움 ㅠㅠ
djd
위키에서는 제일 빠른 게 이거라는 거 같은데,
대회나 코딩테스트에 문제 나오면, 결국 비트마스크DP 로 풀라고 하는 느낌으로 나올 거 같네...
아니면 저 문제처럼 조건을 더 넣어서 네트워크 플로우 문제로 바꾸던지...
차고보
djd
다항시간에 해결하는 건 아직 전문 연구자들도 못한 거고,
a->b,b->c 가 되면, a->c가 된다는 절라 강력한 조건이 있는 저 acm 문제도 당시에 한국에서 푼 팀이 5팀 이하였던 걸로 기억 하는데... 네트워크 플로우 응용이 원래 어려운 파트라서...
백트래킹 보단, 비트DP가 더 빠를 테니, 비트DP만 공부하면 뭐...