day23_tree, graph

선형(linear) vs 비선형(non-linear) 자료구조 ← 자료 간의 연결 형태/모양에 따른 구분

	선형 구조	비선형 구조
데이터 구조/저장	데이터를 순차적으로 직선 형태로 나/배열시킴 + 전후/인접/선후 원소들 간 1:1 연결/나열 형태 → 데이터를 순차적(sequential)/선형으로 순회할 수 있도록 저장	하나의 데이터 아래/뒤에 여러 개의 데이터/원소가 존재할 수 있음, 전후/인접 원소들 간 다:다 연결/배치 형태 → 데이터가 계층적으로 연결되어 저장
level	단일 level로 구성됨	multi-level로 구성됨 → 계층적(hierarchical) 구조 나타나기에 적절
순회/탐색	1번에 탐색 가능, 단일 동작으로 모든 데이터의 순차적 순회 가능, 모든 원소들을 순회하기 쉬움	복잡, 모든 원소들을 순회하기 쉽지 않음, 데이터 순회에 복수의 동작 필요
순서	원소들 간 순서 고려	원소들 간 순서 관계 중요하지 않음
구현	쉬움 ← 구조 간단	다소 번잡
메모리 활용	효율성 낮음? (어떤 설명에서는 기억장소 효율/메모리 밀도 높음)	좀 더 효율적
시간 복잡도	저장 공간이 늘어나면 비례해서 증가	저장 공간이 늘어나면 비례하는 수준보다 적게 증가
예시	- 기본: 배열, (선형)리스트(배열 기반 연속 방식 구조), 연결리스트(포인터 기반 연결 방식 구조) 등 → 자료 삽입/삭제가 어느 위치에서도 이루어짐 - 제한: 스택, 큐, 데크(스택+큐) 등 → 자료 삽입/삭제가 정해진 위치에서만 이루어짐	그래프(트리 포함), 가계도/조직도 상하 관계, 컴퓨터 폴더 구조 등

+ 기타 자료구조(집합, dictionary/사전 등)

나의 질문

• Java collections framework 중 map 및 set은 (비)선형 중 어떤 자료구조에 가까운가?
• 비선형 자료구조 heap, 2진탐색트리 등에서도 원소들 간 순서 관계 중요하지 않나?

tree

여러 가지 tree 구조

• binary tree
• binary search tree
• 균형 binary search tree

graph

인접 행렬

인접 리스트

graph vs tree(graph의 일종)

search algorithm

공통 사항

• 모든 정점을 1번씩/만 방문 ← 그래프는 배열처럼 정렬되어있지 않기 때문에 완전 탐색을 통해 데이터를 탐색해야 함
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함
  • 이를 검사하지 않을 경우 무한루프에 빠질 수 있음

1. bfs

• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐 사용 → 선입선출 원칙으로 탐색
• 재귀로 동작x
• 활용
  • 두 노드 사이의 최단 또는 임의의 경로를 찾고자 할 때

2. dfs

• 자기 자신을 호출하는 순환 알고리즘 → 재귀나 스택 자료구조 사용해서 구현
• bfs보다 더 간단 + 검색 속도 자체는 비교적 느림
• 활용
  • 모든 노드 방문하고자 할 때
  • 2진 트리 순회(traversal)
    • 전(pre)위(order) 순회
    • 중(in)위(order) 순회
    • 후(post)위(order) 순회