[일반] 이거 잘못 풀어진 문제 맞지요?

[건국우유(konkuk16)]

허프만 코드 만들때

만들어진 트리의 총합이 현재 남아 있는 노드들 중에서 최소값 보다 작거나 같으면 기존 트리의 옆에다가 노드를 집어넣고

다음 최소값이랑 합쳐서 새로운 트리 만드는거 아님?

이게 답 아닌가...

- dc official App

[0xrgb(0xrgb)]

문제 나온 트리 맞고 님꺼는 먼가 좀 이상한데

[0xrgb(0xrgb)]

아니다 둘 다 맞는거같음 원래 같은 빈도가 많으면 트리가 여러 종류 나올 수 있음

[건국우유(konkuk16)]

제가 묻고 싶은건 이거에요 다른 사람들꺼 코드도 봤거든요? 근데 연결하고자하는 노드의 값이 기존트리 총합보다 작아야 기존트리에 연결하더라고요... 그래서 이사람꺼 문제 있나 싶었음요 - dc App

[0xrgb(0xrgb)]

아 그런데 중간에 이상한 값이 있음 님꺼 뭔가 잘못됬는데

[0xrgb(0xrgb)]

딱히 연결하고자 하는 값이 기존 트리 총합보다 작아야한다거나 그런조건은 없음. 그냥 가장 작은 노드 2개를 항상 연결해주면 됨

[건국우유(konkuk16)]

아 이거 트리를 뭐같이 그려서 그래요 - dc App

[건국우유(konkuk16)]

근데 그러면 걍 꼴리는 대로 두개 묶을 수도 있단거에요? - dc App

[0xrgb(0xrgb)]

이미 연결된 얘들을 하나로 치고, 가장 빈도 낮은 2개를 쭉 연결하면 됨

[0xrgb(0xrgb)]

빈도가 낮은 두 개면 뭘 묶어도 상관없음. a, b를 묶나 a, c를 묶나 b와 c의 빈도수가 같다면 나오는 코드의 평균 길이는 같을테니까 큰 상관없다는 사실을 알 수 있음

[건국우유(konkuk16)]

그럼 관건이 빈도수가 같은 애들끼리 묶는건가요? 그건 아니던데 또 - dc App

[0xrgb(0xrgb)]

책 다시 읽으셈

[0xrgb(0xrgb)]

https://wooyaggo.tistory.com/95

[건국우유(konkuk16)]

혹시 제 코드가 이상하다는게 빈도수가 높으면 트리의 상단에 위치해야하는데 그렇지 않아서 이상하신건가요? - dc App

[0xrgb(0xrgb)]

19가 나오면 안 됨

[건국우유(konkuk16)]

돌아버리겠네.. - dc App

[0xrgb(0xrgb)]

8이랑 9가 연결되야 하는데 왜 9 - 10, 8 - 12 연결함?

[건국우유(konkuk16)]

아! ㅋㅋㅋㅋㅋㅋㅋ 뭐가 잘못되었다는지 이해됐습니다 혹시 다시 트리만들면 봐주실 의향이.. - dc App

[0xrgb(0xrgb)]

이해했으면 맞겠지 ㅅㄱ

[건국우유(konkuk16)]

작은거끼리 연결되어야하는데 왜 작은거들끼리 안묶였냐 말씀하신거자늠 - dc App

[건국우유(konkuk16)]

그럼 만약 작은것들끼리 묶으면 제답도 해답이 될 수 있단거죠? - dc App

[0xrgb(0xrgb)]

묶을때마다 가장 작은 2개를 묶었으면 맞는거임

[건국우유(konkuk16)]

감사합니다 - dc App