수다닷컴

안녕하세요....질문이 조금 많은데.. 최대한 제가 공부해보고 질문드리는것이니 이해해주시면 감사드리겟습니다..일단 최대힙 최소힙에 관한 문제입니다. 이건 풀기는 풀었는데 제가 푼 답이맞앗는지 궁금해서요문제입니다1) 다음 숫자들을 순서대로 입력받아 최대 힙과 최소힙을 구성하시오44 30 50 22 50 55 77 55결과값은 일단 최대힙의 경우 아래와 같습니다.7755 55 50 30 50 44 22최소힙의 경우는 아래와 같습니다 2230 44 50 50 55 55 77이렇게 결과값이 나왔고요 물론 저기 숫자 사이사이에는 힙은 완전 이진트리이므로 트리 형식으로연결이 되어있구요.. 중간에 삽입되면서 이동되는 과정도 잇지만 일단 결과값만 적엇습니다...그리고 그래프 문제입니다.1) 인접 행렬과 인접 리스트로 표현하시오2) 각 정점의 차수를 구하시오3) 깊이 우선탐색 방법을 사용하여 그래프의 모든 정점을 방문하시오4) 너비 우선 탐색 방법을 사용하여 그래프의 모든 정점을 방문하시오이렇게 4개의 문제를 풀어야합니다. 이 문제도 제가 도서관에서 끙끙거리면서 고민해봣는데결론은 답은 나오긴 햇지만 확신이 없고 그래서.. 조금 저도 염치 없지만 1~4번 설명과함께 답을 알려주셧으면정말 감사드리겠습니다...또 하나는 최소비용 스패닝 트리에 관한 문제인데.. 사이클에관한 의문점이 있어서 질문드립니다.문제는 다음 그래프의 최소 비용 스패닝 트리를 구하시오 입니다.여기서 첫번째 그래프의 최소 비용 스패닝 트리를 구하고자 하는데...저는 답이 2개라고 생각하는데 제 생각이 맞는지 확인해주셧으면 감사드리겠습니다.책의 정의부분에서 사이클이 형성되면 최소 비용 스패닝 트리에 어긋난다고 하는데 제가볼때 사이클은 형성이 안되는데2가지의 경우가 나와서요이렇게 2가지의 경우가 나왔습니다. 두번째 그래프의 저의 답은 아래와 같습니다 각각 최소 비용 값을 더하면 10+12+13+14 로 최소이면서 모든 정점들이 연결상태그리고 이건 스레드 이진트리 문제입니다...위의 그래프를 스레드 이진 트리로 변환하라고 하는데...책을 읽어봐도 일정 수준의 내용만 나와있고 위의 단말노드나 자식을 하나 갖는 노드의 처리경우에널값을 지니는 포인터를 정확히 어느곳으로 향해야 되는지 안나와잇더라고요...스레드 이진트리로 바꾸라는것이 보통 연결리스트로 만들면예상햇던것보다 널값을 지니는 포인터들이다수 생겨 그것을 낭비(?)하지 않고 활용하기위해서 스레드이진트리가 나온걸로 공부햇습니다만..정확히 표현해보려고하니 한계가 잇어서 질문드립니다.마지막으로...이 그래프에서 문제는1) 다음 그래프에서 최단 경로르르 구하시오 이런 문제입니다.s-t로 향하는 최단경로를 구하라는 소리인지? 문제파악도 정확이 씰ㅘ??안됩니다.물론 책을 꼼꼼하게 읽어봣는데 난감하더라구요...저는 그래서 s-t로 가는 최단경로 s-a-b-d-t 해서 (7+4+6+5)햇는데..아무리 생각해도이건 아닌것 같아서요...친구들과 상의도 해보고...그러다가 모르는 문제와 의아한 문제만 추려서 질문올려보았습니다..항상 행복하시고 좋은일만 가득하시길 빌겟습니다...^^

신청하기