그럼 내가 알고리즘 떡밥을 내겠습니다

[알고리즘(130.126)]

n개의 노드를 가진 rooted 트리가 있음.

각 턴마다 트리의 노드 한개를 랜덤으로 정해서 그 노드가 루트인 서브트리를 삭제함. 여기서 각 노드가 선택될 확률은 동일함.

모든 정점이 다 삭제될때까지 총 턴 개수의 기대값은?

[CodeCraft(lionix)]

기대값이란 의미가 정확히 어떤거야 형?

[알고리즘(130.126)]

확률 안배우셨나여

[ㅅㅅㅅ(221.145)]

기대값은 lgN 아닌가? (log_2(N)) 너무 쉬운 거 아녀? :)

[ㅅㅅㅅ(221.145)]

각 노드가 선택될 확률이 동일하다면 일단 한 번 선택하면 절반 정도가 날라간다고 기대해볼 수가 있잖아.

[알고리즘(130.126)]

기대값을 정확히 계산해야합니다만. 그리고 이미 남아있는 노드중에 선택될 확률이 동일하다는겁니당

[?(175.116)]

오레노턴

[ㅅㅅㅅ(221.145)]

다시 생각해 보니 레벨이 내려가면 내려갈 수록 노드 개수가 많아지니 root 쪽을 선택할 확률은 극도로 낮아지는 군.

[알고리즘(130.126)]

예, 그리고 문제 자체는 기초 확률 지식만 있어도 쉬움여

[ㅅㅅㅅ(221.145)]

단순히 개수로 보고 잠시 1/2 생각한 내가 멍청했다.

[ㅅㅅㅅ(221.145)]

그럼 보나마나 N이지 뭐.

[ㅅㅅㅅ(221.145)]

Root node를 지우지 않는 이상 모든 정점이 사라질 일은 없거든.

[ㅅㅅㅅ(221.145)]

아니다. 이 말 취소.

[알고리즘(130.126)]

아닌데여

[ㅅㅅㅅ(221.145)]

트리는 바이너리 트리지?

[알고리즘(130.126)]

아닌데여. 걍 루트 있는 아무 트리.

[알고리즘(130.126)]

문제를 수갤에 내야했었나

[어휴(121.144)]

꼭 이런식으로 자위질하고싶을까;