그래프

그래프: 정보들의 관계를 이용해서 정리한 자료구조다

node: 그래프에서 표현하고자하는 주체(=vertex, 정점)
edge: 관계를 나타낸 선(=간선)
간선에 화살표의 유무에 따라: 유향 그래프 / 무향 그래프
간선에 저장된 값: 간선의 가중치
사이클: 어떤 노드를 출발해 간선을 두 번 이상 지나지 않고 원래 노드로 돌아오는 경로

유향그래프과 ABCD사이클

무향 그래프와 간선의 가중치, ABD사이클

예제 - 구슬크기

무게가 서로 다른 n개의 구슬이 있다. 편의상 1번~n번 구슬이라고 하자. 우리는 양팔 저울을 이용해서 어떤 두 구슬에 대해 어떤 구슬이 더 무거운지 측정할 수 있다. k번 측정한 결과가 주어질 때, 자신이 몇번 째로 큰지  정확하게 알 수 있는 구슬은 몇 개인지 구하여라
n=8, k=9
1<2
2<3
2<4
3<7
4<7
4<6
7<5
6<8
5<8 

 

풀이

그래프화