alsdk3586   10일 전

값이 들어올때마다 힙의 최솟값보다 작으면, 패스하고 크다면 pop하고 그 값을 insert합니다. 

제 생각상으로는 맞다고 생각하는데 틀렷다고 하네요 ㅠㅜㅠ

혹시 뭐가 문제인지 아시는 분 계시나요? ㅠㅜㅠㅜ

1207koo   10일 전

0. delete_heap이 아니라 delete_haap...

1. 25번째 줄은 의도 상으로는 자식 노드가 없는 것을 체크하는 것 같은데, 저렇게 체크하면 2250000/2 부근의 리프 노드는 리프 노드로 체크가 되지 않을 수 있습니다. 차라리 pp와 비교하는 것이 맞습니다.

2. 27번째 줄에서 실제 숫자가 0인 경우 힙에 두 자식 노드의 값이 0일 수도 있습니다.

3. 29, 37번째 줄에서 0인 것으로 리프 노드가 있는지를 확인하는데, 우선 29번째 줄은 불가능합니다. 자식 노드가 하나면 무조건 왼쪽에 있습니다.

4. 또한 자식 노드의 값이 0일 수 있기 때문에 저렇게 체크하면 안 됩니다.(같은 이유)

5. 45번째 줄은 자식 노드가 두 개인 경우인 것 같습니다. 다만, break문이 하나도 없다는 것이 문제입니다. (없도록 만들 수 있지만 저렇게 되진 않습니다) 두 자식노드의 값 중 작은 것과 바꾸는 것이 아니라 큰 값과 바꿔야 하며, 그 큰 값 조차도 부모의 값이 더 크다면 바꾸지 않고 멈춰야 합니다.

6. 코드 자체가 비효율적입니다. 힙에 n^2개를 전부 들고 있을 필요 없습니다. 설명하신 것처럼 최소힙으로 n개만 들고 있어도 됩니다. 그런데 코드는 그렇게 짜여 있지 않습니다.

--------------------------------------------------------------------------------------------

설명하신 것하고 코드 짜여진 것하고 완전히 차이가 있는데 그건 왜 그런건가요...

그리고 delete_haap함수는 완전히 처음부터 짜야 할 것 같습니다. 한 두 군데가 틀린 것이 아닙니다. 하지만 맞게 짠다고 해도 heap에 n^2개가 들어가는데 시간이 될 지는 모르겠습니다. 시간초과가 날 수도 있습니다.

alsdk3586   9일 전

제가 두가지 방법으로 짜다가 하나의 방법이 안되서 도움을 청한 것였는데 올리는 도중에 소스가 꼬인 것 같습니다 ㅠㅜㅠ 혼란을 드려서 죄송합니다. 

피드백 감사히 잘 받았습니다. delete함수가 이상한다는 느낌을 받았는데 어느 부분을 간과했는지 알 수 있었습니다. 

덕분에 다시 차근차근 이론부터해서 시작할려고 합니다.

감사합니다~~^^ 도움 많이 됬어요!!

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