chsong91   4년 전

자바에 발 담근지 두 달도 안 된 초보입니다.

코딩에 깊이도 없고 개념을 자세히 알지 못하지만 알고리즘이 재미있어 감히 탐색부터 시작하여 풀어내려오다가 

이 문제까지 왔습니다.

문제를 풀다가 구상한 바를 구현하는데 성공했지만 첫 번째 시도에서 메모리초과가 뜨더군요

인접리스트와 인접행렬에 대한 개념이 없던 제가 메모리초과를 계기로 인접리스트를 조금 알아보고

인접리스트까지 쓰는데 성공했는데(제가 여태껏 쓰던 boolean[][] 간선 배열이 인접행렬인지도 몰랐습니다...) 

그런데  이번에는 시간초과가 나네요...

백준 저지에 제출을 하면서 가장 어려운 게 시간을 관리하는 것 이더라구요

개념과 지식이 많이 부족한 탓이겠지요. 

배움에는 거부감이 없습니다.  고수님들이 지적하면 달게 받겠습니다.

공부방향과 자세 등을 조언해주셔도 경청하겠습니다.

부디 코딩꿈나무를 도와주세요!!

lovinix   4년 전

주석을 보니 각 집합에 속하는 정점의 개수가 1 2 3 ... N/2 인 경우로 나누어서 걍 경우를 완전탐색하려고 하셨던 것 같습니다

그렇다면 정점이 V개 있을 경우 이 코드는 연산을 몇 번이나 수행할까요?

단순히 정점을 두 집합으로 나누는데만 C(V, 1) + C(V, 2) + ... + C(V, V/2)  개의 경우가 있을텐데 문제의 조건에 1<=V<=20000 이니 V가 커질수록 아주 많은 연산이 필요하겠군요

실제로 이 코드에

1

10000 1

5 6

정도의 적당히 V가 큰 입력을 넣으면 답이 나오지 않습니다.

gunwookim   4년 전

이정도가 어딜봐서 초보입니까;;

chsong91   4년 전

@lovinix

그렇다면 모든 경우의수를 탐색할 필요 없이 간선정보가 주어진 정점들만 탐색해야할까요? 감이 잡히질 않네요... 

lovinix   4년 전

한 정점에 연결된 모든 정점은 이 정점과 다른 집합에 속해야겠네요

또 그 모든 정점은 각각 자신이 연결된 정점들과 반대 집합에 속해야겠죠

그러니 정점들이 어느 집합에 속했는지 관리해주면서 정점들마다 자신이 연결된 간선들을 타고 계속 탐색해주면 되겠네여

푸신 문제 목록을 보니 충분히 푸실 수 있는 문제라고 생각합니다

chsong91   4년 전

@lovinix

그렇군요 답변 감사합니다. 더 고민하고 풀어보겠습니다 

좋은 하루 되세요 :)

chsong91   4년 전

탐색 대상 표본을 인접리스트에 들어있는 정점들로 한정하니 풀렸습니다.

그룹을 어떻게 유동적으로 나눠줄지 고민을 많이하다가 지인에게 팁을 받고 겨우 해냈네요

도와주신 분들 정말 감사합니다.

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