파이썬과 함께하는 자료구조 8장 그래프(알고리즘) 연습문제.

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개의 초콜릿을 선택하는 것, 그것이 그리디 하다 할 수 있다(탐욕적이니까)

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

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

(작성중)