jiyolla   3달 전

이번에는 부분부분 Unit test? 비슷한 것도 나름했는데, 어디서 틀렸는지 모르겠네요...

큰 과정은 

1. DFS순회 한 번 하면서 parent, depth만들기.

2. dp로 parent_2tothe만들기. parent_2tothe[i][j]는 j의 2^i번째 parent임.

3. parent_2tothe를 이용해서 log2(depth[])시간에 작동하는 parent_n()만들기. parent_n(i, j)는 j의 i번째 parent. 0번째 parent는 자신.

4. parent_2tothe를 이용해서(parent_n()로 쓰면 코드는 더 깔금하겠지만 python이 느린 거 같아서) find_LCA()만들기. find_LCA(a, b)는 a, b가 같지 않지만 같은 depth를 가진 경우에 말그대로 LCA를 찾아줌

이번에는 생각보다 코드가 제 개인적인 생각에는 나름 잘 정리되었다고 생각해서, 부분 테스트도 중간에 잘 되어서 그런지,

그래서 더 빨리 어디서 틀린지 모르겠다는 절망감이 확 밀려오고, 지금 이례적으로 Debugging한 지 1시간도 안 됐는데 이렇게 도움!글을 올립니다.

seico75   3달 전

15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
3
2 3
4 7
8 15

jiyolla   3달 전

아!!!!

그렇네요...역시나 find_LCA에서 문제가 있었네요...하...

아니 이걸 왜 생각못했지?ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 얼탱이 없네...

반성하겠습니다...

find_LCA의 테스트를 가장 적게 했고, 확신도 제일 덜하기 했는데, 진짜 여기서 문제가 있었군요.

다음에는 좀 더 확실하게 입력의 모든 범위를 고민했는지 생각해볼게요 감사합니다.

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