noeffserv   1년 전

3일째 풀고 있는데.. 알고리즘은 맞는것 같은데..왜 틀리는지 모르겠네요.


우선 어떻게 풀었는지 간략히 설명하겠습니다.

1. 각 노드에 대한 인접 리스트를 vector <int> tr[100001] 에 저장합니다.

2. 각 노드에 대해서 tr 을 오름차순 정렬 했습니다.

3. 다음 각 노드에 대해서 이진트리를 만듭니다. 이 이진트리의 목적은 노드들의 중간값(?) 과 첫 번째 값을 O(log) 만에 찾기 위한 것입니다.

4. 다음 dfs 를 실행시킵니다. 이 때, 방문한 노드를 n 이라고 두겠습니다. dfs 를 실행하면 remove(n) 함수가 작동됩니다.

이 함수는 n 을 인접리스트로 가지고 있는 모든 노드들의 이진트리에서 n 의 존재를 지워버립니다.

5. n 노드의 사이즈가 현재 홀수라면 next = findnext(n) 라는 함수로 중간값을 가져오고 아니면 첫번째 값을 가져옵니다.

6. 그리고 dfs(tr[n][next]) 로 재귀호출합니다.

7. 4~6을 반복합니다.


이런식으로 짰는데.. 어디가 문제인지 모르겠습니다.

아마 제 생각에는 이진트리 구현하면서 문제가 생긴 것 같은데..

번거롭더라도.. 코드를 한번 봐주셨으면 좋겠습니다...ㅠ



amugeona   1년 전

트리에 대해 좀더 설명해주세요

noeffserv   1년 전

네.

각 정점마다 이진트리가 있습니다.

그리고 이진트리 정보는 seg 에 저장되어있습니다.

예제 테스트케이스 를 통해.. 어떻게 정보가.. 저장되는지 설명해드릴게요.

5 6

1 2

1 4

1 3

3 2

3 4

2 5

일때,

그래프 1번 노드의 이진트리(seg[1])는 아래처럼 구성됩니다.

734f4ebdca6589aa06658e0381d8cf19.jpg

seg 의 first 는 방문할 수 있는 인접 노드의 개수입니다.

second 는 노드 번호인데.. 자식 노드가 있을 경우

양쪽 자식노드 중 큰 노드번호값을 취합니다.

위와 같은 이진트리를 만드는 역할을 하는게 BuildBtree 함수 입니다.

이 이진트리를 이용해서.. 방문했던 정점을 없애기(remove 함수)도 하고

방문할 수 있는 정점 (findnext 함수)을 찾아갑니다.

amugeona   1년 전

A는 합 인덱스트리이고, B는 최대값 인덱스트리네요.

이진 탐색으로 제거되는 원소를 찾는 과정도 나쁘지 않은것 같아요.

그런데 B 인덱스트리에서는 사라지는 원소가 전혀 고려되지 않는데 이걸 의도하신 알고리즘이신가요?

그리고 재귀함수로 DFS를 구현하셨는데, 원소 10만개가 선형 그래프로 구성되면 아마 터질꺼에요 x.x

비재귀함수로 구현하셔요~ 그리고 B 인덱스트리는 있을 필요 없는거 같아요.

아이디어는 맞는 방향이니 테스트케이스를 잘 만들어서 예외상황들을 잡아보세요. ㅋㅋ


4 5
1 2 1 3 1 3 1 3 2 3

도 문제조건에 위배되지 않는 테스트케이스인데, 정답이 정상적으로 나오는지 체크해보세요 ㅋㅋ

1 2 3

나오셔야합니당

noeffserv   1년 전

감사합니다. 예외처리 문제는 거의 해결된듯 싶습니다.

근데 55퍼센트에서 시간초과에 직면했네요.

음.. 다음 노드를 찾을 때, O(1) 만에 탐색이 가능한가요?

어떻게 푸셨는지 조금만 힌트를 주실수 있나요?

amugeona   1년 전

ㅂ위 시간복잡도는 O(NlgN) 아닌가요?

저는 대충 짜서 O(N(lgN)^2)으로 통과했었는데 BIT와 파라매트릭 서치를 합쳐서 써서 탐색을 (lgN)^2 만에, 업데이트는 lgN만에 했습니다.

불필요한 연산이 있거나 특정 부분에서 의도하지 않은 굉장히 오래걸릴 케이스가 있을수 있으니 꼼꼼히 따져보세요~

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