파이썬 으로 쉽게 풀어 쓴 자료구조 8 장 - paisseon eulo swibge pul-eo sseun jalyogujo 8 jang

8장 연습문제. 약 30여개 문제가 있음.

너무 단순하거나 간단히 풀수 있는 것을 제외하고 기록함.

8.10 N개의 정점을 가진 무방향 그래프 G에 대해 다음의 설명중 맞는 것만 모아놓은 것은?

1) G의 각 쌍의 정점 사이에는 1개의 경로만 존재하면 G는 트리이다

2) G가 하나의 연결성분으로 되어있고 N-1개의 간선을 가지면 G는 트리이다.

3) G가 N-1개의 간선을 가지면서 싸이클이 없으면 G는 트리이다.

용어를 정확히 이해하지 않고 풀면 많이 헷갈린다.

1) 트리란 1개 이상의 노드를 갖는 집합이다. 그렇기에 각 쌍의 정점 사이의 한개의 경로, 즉 최소 2개의 노드로 구성되어진 G는

트리이다.

2) 연결성분이란 최대로 연결된 부분의 그래프.

G가 하나의 연결성분을 가진다고 하였으므로 모든 정점들이 연결되어있다.

그런데 모든 정점을 연결하면서 간선이 N-1개란 뜻은 싸이클을 완성 할 수 없다는 뜻이다.

예를들어 5개의 정점을 하나의 연결성분으로 하면서 싸이클을 만들려면 5개의 간선이 필요로 하다.

(중간에 다른 방향을 통해서 3개의 싸이클을 만든다고 할 경우 하나의 연결성분이라는 조건을 충족 못함)

그렇기에 G는 트리라고 할 수 있다

3) 2에서의 설명을 다르게 바꾼 것. 

8.18 Kruskal 알고리즘과 Prim 알고리즘을 비교한 것 중 가장 적절하게 설명한 것을 고르시오.

이 문제에서 짚고 넘어가야 하는 부분은 그리디 알고리즘과 동적계획 알고리즘이다.

그리디 알고리즘 : 탐욕 알고리즘 이라한다. 처음엔 탐욕이라길래 뭔가 많이 가져가는거가 목표인가 라고 생각했으나

그게 아님.. 그래서 개인적으론 이기적이다 라고 이해하고 있다.

그리디 알고리즘은 쉽게 생각하면 근시안적으로 보는 것이다. 바로 3개 초콜릿, 1분뒤 10개 초콜릿 을 준다고 했을 경우

바로 3개의 초콜릿을 선택하는 것, 그것이 그리디 하다 할 수 있다(탐욕적이니까)

동적 계획법은 위와는 살짝 다르다.

얘는 조금 생각을 한다. 큰 맥락이 아닌 부분에 대한 이해를 바탕으로 최선을 고려하고 이를 통해 전체의 해답을 얻는다.

(작성중)

안녕하세요, 여행벌입니다.

C언어로 쉽게 풀어쓴 자료구조 8장 - 트리 연습문제 풀이입니다.

틀린 부분이나 궁금하신 부분은 편하게 댓글에 남겨주세요!

8장연습문제풀이.zip

1.34MB

[ 6번 ]

문제가 잘못된 것 같습니다. 답이 보기에 없습니다.

[ 12번 ]

+) 풀이에는 제가 트리의 모든 노드 중 가장 큰 값을 반환한다고 적어놓았는데, 트리의 리프 노드 중 가장 큰 값을 반환하는 함수입니다! 풀이 수정하겠습니다~!

[ 13번 ]

재귀적으로 서브트리도 밸런스 트리인지 아닌지 확인하면 됩니다.

[ 19번 ]

이진 탐색 트리는 오른쪽 서브트리의 값들이 더 큽니다.

따라서, 가장 오른쪽부터 순회를 하면 내림차순으로 출력할 수 있습니다.

[ 22번 ]

책에 나와있는 '사전' 코드와 너무 유사해서 다루지 않았습니다.

1. 전위표기법 2020.02.27 19:42

   짧은 지식이지만, 댓글 남겨봅니다.
   6번의 경우엔 저 식을 (A * B + C / D) 트리로 그린 다음에 그 트리를 전위 순회 하는 방식이 아닐까 합니다.
   그러면 답은 3번이 됩니다.

   이런 글 써주셔서 너무 감사하고 언제나 좋은 하루 되십시오.

   • 아~ 그렇게 생각하면 될 것 같습니다....!! 의견 나눠주셔서 너무 감사드립니다!! 좋은 하루 되세요 :))

2. 도라에몽 2020.03.20 23:24

   11번에대해 질문드립니다.
   저는 왼쪽부터 노드를 채워 나가서, 5가 3레벨의 노드이고 왼쪽노드가 4, 오른쪽노드가 6으로 풀이를 하였습니다. (해설해주신 풀이에는 보니 4가 3레벨의 노드이고 5가 오른쪽 노드로 하셨습니다) 제가 생각한 트리도 맞는것인지, 아니면 따로 조건이 있는것인지 궁금합니다.:)

   • 안녕하세요~ 도라에몽님! 책에 나와있는 이진 탐색 트리 노드 삽입 과정을 보시면 입력이 된 값을 현재 만들어져있는 이진 탐색 트리 루트부터 비교해서 크면 오른쪽, 작으면 왼쪽으로 내려갑니다! 따라서 5가 입력되기 전의 트리는 다음과 같은 상황입니다.
     11
     6 19
     4 8
     10
     이때 5가 입력되면 11보다 작으므로 왼쪽 서브트리로, 6보다 작으므로 왼쪽 서브트리로, 4보다 크므로 오른쪽 서브트리로 이동되는게 맞을 것 같습니다!

     도라에몽님이 말씀해주신 트리도 이진 탐색 트리의 정의에는 부합하는 것 같습니다! 다만, 제 개인적인 생각으로는 11번 문제는 다음 순서로 자료가 입력된다고 가정했으므로 4 뒤에 5가 입력되는 경우라 제가 그린 트리가 조금 더 정답에 부합하지않을까 싶네요...!! ( 제 풀이가 정답이라는 보장이 없어서... 확신을 못드리겠네요 ㅠㅠ 제 댓글이 이해에 도움이 되면 좋겠네요...!! )

3. 도라에몽 2020.03.25 16:54

   이해되었습니다 너무 감사합니다^^

4. 12번 2020.03.28 22:09

   다름이 아니라 12번 문제에 대해 궁금한점이 생겨서 댓글을 납깁니다.
   12번 문제가 최대값을 반환한다고 적어주셨는데..
   저는 루트3 -> 왼쪽 오른쪽 자식 중에 큰 값인 5-> 여기서 다시 왼쪽 오른쪽 자식 비교 후 4
   3,5,4 순으로 탐방한다고 생각하였는데.. 잘 이해가 가지않아 댓글을 납깁니다ㅜㅜ

   • 안녕하세요~ 12번님! 일단 제 풀이에도 실수가 있는 것 같네요! 12번 문제는 트리에서 최대값이 아니라 리프노드 중 최대값을 반환하는 함수입니다~!
     루트노드부터 차례대로 함수를 따라가보겠습니다!

     (1)
     [3] 노드는 NULL 도 아니고, 왼쪽과 오른쪽 자식이 모두 NULL도 아니므로 마지막 else 구문이 동작합니다. 따라서 먼저 mystery(p->left) 함수가 호출이 되서 [5] 노드로 이동합니다.

     (2)
     [5] 노드로 이동을 해왔습니다. 마찬가지로 자식 노드 모두 NULL 이 아니고, [5] 노드도 NULL 이 아니므로 mystery(p->left) 가 호출되서 [4] 노드로 이동합니다.

     (3)
     [4] 노드로 이동을 해왔습니다. 자식노드가 모두 NULL 이므로 4를 return 해주면서 (2)로 돌아가게 됩니다.

     (4)
     (2) 번에서 mystery(p->left) 는 4를 반환받았으므로, mystery(p->right) 가 호출됩니다.

     (5)
     [2] 노드로 이동을 해왔습니다. 자식노드가 모두 NULL 이므로 '2' 를 return 해주면서 (4) 로 돌아가게 됩니다.

     (6)
     [5] 노드에서 왼쪽 오른쪽 자식을 모두 탐색해서 얻은 값이 4와 2이므로 가장 큰 값이 4를 return하고 [5] 노드 탐색이 끝납니다.

     (7)
     다시 [3] 노드로 돌아와서 mystery(p->right)를 수행합니다. 그러면 결국 오른쪽 서브트리의 리프노드 중 가장 큰 값인 '8' 을 return 받을 것이고 따라서 4와 8중 가장 큰 값인 8을 return하면서 함수가 종료됩니다.

     이해하시는데 도움이 되면 좋겠네요!

   • GHJ 2021.05.21 21:33

     저도 12번님처럼 생각했어요! 재귀적 함수의 성질은 알겠는데 여기서는 4의 경우 return p->data; 하고 다시 노드 5로 되돌아간다는 게 어디에 명시되어 있나요? 그냥 3-5-4에서 끝 아닌가요?

   • 함수의 호출과 반환을 생각하시면 좋을 것 같아요!!

5. 체리 2020.07.06 21:30

   안녕하세요. 좋은 내용 올려두셔서 감사합니다
   16번에 대해 질문있습니다

   Count=count+find(root->left)+find(root->rount);
   return count에서

   각각 누적되어 반환되는 count를 더하면 값이 점점 커지는게 아닌지 궁금합니다

   (예를 들어 6+7+8 ... 식으로)

   그래서 저는

   find(root->left)
   find(root->rount)
   로 해야 하는게 아닌지 궁금합니다

   Count는 공통변수라 누적되는것으로 이해하였습니다

6. 체리 2020.07.06 21:57

   한가지 더 질문드립니다!

   20번 문제에서
   search plue one(root->right)
   root->data++
   search plue one(root->left)
   로 하셨는데

   root->data++ 해주는 부분의 위치가 꼭 중간에 있어야 되는 이유가 있을까요?

7. ㅇㅇ 2021.06.26 20:47

   감사합니다