데이터와 정보
- 컴퓨터가 이해할 수 있는 방식으로 표현 필요
- 데이터(data)
- 가공되지 않은 어떤 사실
- 예) 미로에서의 개별 거리
- 정보(information)
- 특정 도메인에서 데이터에 대한 통찰력을 제공하는 사실의 해석(데이터를 의미있는 맥락으로 만듬)
- 예) 미로에서의 총 이동 거리
- 자료구조
- 알고리즘이 효율적으로 처리할수 있도록 데이터를 표현
- 특정한 방식으로 구조화된 데이터와 연산으로 구성
1. 트리
- 값이나 객체의 계층 구조를 나타내는데 주로 사용되는 자료 구조
- 트리는 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조임
- 그러나, 트리는 두개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다.
- 이러한 특성 때문에 '최소 연결 트리' 라고 부르며 부모-자식 관계가 성립하기 때문에 계층형 모델이라 부름
1. 트리의 특징
- 부모 - 자식 관계가 존재해 레벨이 존재한다.(최상위 노드 = root)
- 노드가 N개이면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 개
- 방향성이 존재하고 사이클이 존재하지 않음(비순환)
- 트리의 순회는 전위순회, 중위순회, 후위순회 3가지가 존재함
2. 정보 없는 검색
1 . 너비 우선 탐색(Breadth-first search)
- 특정 깊이에서 모든 선택 가능한 탐색을 한 후에 트리의 더 깊은 선택지를 탐색
- 깊이 우선 탐색(Depth-first search)
- 출발점으로부터 특정 경로의 가장 깊은 지점에 있는 목표를 찾을 때까지 탐색
Robotics