hw2 ex3 질문입니다.

하재승 · 손님

문제 정의가 조금 모호한 거 같습니다.

1. 모든 subtree의 root는 "|"이고 그 가지의 중앙에 있다.

가지의 중앙이라는게 그 아래 두 child tree의 root로부터 중앙이라는 것인가요?

2. 왼쪽과 오른쪽 subtree의 깊이가 다른 경우에

정영범 · 가입: 2005년 9월 5일 올린 글: 167

1. 예 맞습니다.
2. complete binary tree의 정의를 보시기 바랍니다. Very Happy

A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

예로 든 경우는 complete binary tree가 아닙니다.

하재승 · 손님

음 주어진 문제로부터 complete binary tree 일꺼라고 전혀 생각을 못했네요.

정영범 · 가입: 2005년 9월 5일 올린 글: 167

남기웅 · 손님

한 팀이 탈락했을 경우, 대진표를 새로 짠다는 것이 잘 이해가 되지 않습니다.

대진표라는 것이 단순히 팀들의 나열이 아니고, 토너먼트의 tree구조가 있는 것인데, 한 팀이 탈락했을 경우 원래의 구조를 무시하고 새로운 토너먼트를 짜라는 말씀이신지요?

예를 들어서 A, B, C, D, E, F, G 7개의 팀의 토너먼트가 처음에는

____|_____
___|__ __|__
| | | |
A - B C - D E - F G

이런 식이었는데, C 팀이 탈락했다고 합시다. 그럼 남은 대진표의 구조는 complete binary tree가 아니게 되지요. 이 때 대진표를 완전히 새롭게 바꾸어서 complete binary tree가 되도록 해야 한다는 말씀이신지요?

문제에서 '새롭게 구성되는 대진표'를 출력하라고 했으므로, 원래의 대진표에서 한 팀이 탈락했을 때의 (이것도 애매한 면이 있는데, 그 팀이 첫 번째 경기에서 졌다고 가정하고) 대진표를 구하는 것이 의미가 있지 않을까 싶습니다.

남기웅 · 손님

위의 대진표가 이상하게 됐네요.

( ( (A, B), (C, D) ), ( (E,F), G) ) 단순히 이런 7개 팀의 대진표입니다.

여기서 C나 D를 빼게 되면, 트리의 구조 자체가 comlete binary tree로는 표현될 수 없다는 것을 말씀리는 것입니다.

김홍준 · 가입: 2007년 9월 16일 올린 글: 16

정영범 · 가입: 2005년 9월 5일 올린 글: 167

제가 답변을 잘못했습니다. Crying or Very sad

문제에 나와있는

하재승 · 손님

탈락이 그런식으로 생각되게 되면 3번 문제의 입력에 꼭 complete binary tree이여야한다는 조건도 살짝 의심스럽네요;

이우석 · 손님

탈락의 의미는 한팀이 승부에서 졌을 때를 의미한다고 하셨는데요, 그렇다면 부전승으로 올라간 팀이 탈락하면 어떤 모양의 대진표가 형성되나요? 부전승으로 올라가 있는 팀은 질 상대가 없는데요. 예를들어,

( (A, B) C) 에서 C가 탈락한다면 그냥 (A, B)로 보면 되는건가요?

김홍준 · 가입: 2007년 9월 16일 올린 글: 16

tree의 폭을 넉넉하게 잡고 문제에 주어진 조건을 만족하는 tree를 그려주기만 하면 되나요? 아니면 꼭 tree의 가로폭을 최소화 시켜서 tight 하게 그려야 되나요?

전자의 경우 간단한 traversal과 계산으로 node의 위치를 파악 가능하지만, 후자의 경우는 제가 여러시간 동안 고민해봐도 복잡한 자료구조를 유지하면서 여러차례 트리 순환을 해야만 구현이 될것 같네요.

예를 들자면

김진산 · 가입: 2006년 9월 13일 올린 글: 45

왜 저는 leaf 사이의 간격(whitespace)은 1이상으로 하며,

간격은 최소한으로 줄인다.

라는 이상한 규칙을 아무생각없이 만들고, 이 때문에 고생했을까요. ㅠ_ㅠ

ps. 그냥. 푸념입니다. ㅠ_ㅠ

화이팅~

김홍준 · 가입: 2007년 9월 16일 올린 글: 16

음 아무리 아무리 밤을 세워 생각해봐도 문제가 명확하지 않으면 풀기가 어려울것 같네요 ㅠㅠ

명확한 조건제시가 필요합니다.

위의 조건을 다시한번 생각해보면
아래와 같은 모양의 경우

1)

김병호 · 손님

너무들 복잡하게 생각하시는 것이 아닌지
문제에 써 있는대로 세가지 조건만 만족하면서 아름답기만 하면 된다고 생각합니다.
아름다운 한에서 쉬운 방법으로 구현하면 되지 않을까요?
전 김홍준님의 4번 방법도 충분히 아름다워 보입니다.

하재승 · 손님

나에게 아름다운게 남에게 아름답지 않을수 있는게 문제겠지요 Smile

이왕이면 조건이나 기준이 명확한게 서로 혼란스럽지 않으니까요.