[엘리스 AI 트랙 2기] Day 7 - 자료구조

자료구조란?

자료을 어떻게 저장하여 삽입, 삭제, 추출 등을 빠르고 효과적으로 수행할 것인가?
내가 개발하고자 하는 프로그램의 원활한 작동을 위해 어떤 자료구조를 써야할까?

같은 숫자도 숫자형인지, 유니코드인지에 따라 완전히 다른 의미를 가질 수 있다.

배열, 연결리스트에 대해 학습했다.

스택과 큐

배열과 연결리스트를 사용하여 구현

트리

트리의 종류는 다양하게 있다.

이진트리 : 자식 노드를 최대 2개까지만 갖는 트리.
포화 이진 트리 : 모든 정점이 자식을 2개씩 갖고 모든 리프노드의 트리가 같은 트리
완전 이진 트리 : 마지막 깊이를 제외하고 모든 정점이 완전히 채워져있으며 가능한 한 왼쪽에 있는 트리
정 이진 트리 : 리프노드 제외하고 모든 노드가 2개의 자식을 갖는 트리

탐색방법은 크게 두가지이다.

깊이 우선 탐색 (스택, 재귀호출)

1. 전위 순회
2. 중위 순회
3. 후위 순회
코드 자체는 똑같지만 append 해주는 타이밍을 조절하여 다르게 구현할 수 있다.

너비 우선 탐색 (큐)

노드 방문 -> 팝 -> 팝 노드의 자식을 추가 -> 팝 -> 자식 추가 -> 팝 -> ....

우선순위 큐와 힙

힙은 우선순위 큐를 사용해 만들 수 있다.

최대힙: 부모가 자식보다 큰 값을 가짐
최소힙: 부모가 자식보다 작은 값을 가짐