알고리즘 학습을 위한 기초지식 - 자료구조

• 알고리즘 : 문제를 해결하기 위한 일련의 단계적 절차를 정의하여 데이터를 처리하는 것 
  -> 좋은 알고리즘은 입력 크기가 커질수록 효율적으로 작동하고 빠른 실행속도를 나타냄 
• 알고리즘 학습 : 특정 문제를 통해 알고리즘의 설계 및 분석 방법 습득
• 프로그래밍언어 -> 자료구조 -> 알고리즘 순으로 학습 (수학적 지식 동반)
• 자료구조는 데이터를 효율적으로 저장하고, 조직화하며, 관리하는 방법을 다룸.
  프로그램이 사용하는 데이터를 적절한 형태로 저장하고 처리할 때 필수적.
  자료구조는 다양한 유형이 각각의 특정 문제를 해결하는 데 최적화되어 있다.
  
  

---

<가장 기본적인 자료구조>
배열 / 연결 리스트 / 스택 / 큐 / 트리 / 그래프
   선형 자료구조        비선형 자료구조  

1. 선형 자료구조(배열, 연결 리스트, 스택, 큐) - 논리적 관계가 선형

1) 배열 (index, value) 
같은 자료형을 갖는 여러 개의 데이터를 하나의 변수에 모아놓은 데이터의 집합체
A = [1,2,3] / A[0(index)] = 1(value) 
- 배열은 연속된 메모리 블록에 데이터 저장
- 인덱스를 사용하여 원하는 요소에 빠르게 접근 -> 탐색이 빠름
- 생성 시 크기가 고정됨
- 논리적 순서와 물리적 순서가 동일 -> 삽입/삭제 시 자료의 이동이 발생

2) 연결리스트 (순차접근) 
- 노드들이 메모리 어디에나 위치할 수 있음
- 논리적 순서와 물리적 순서가 같지 않지만 순서는 유지시켜줘야함 (head에서 시작) 
- 노드는 데이터와 다음 노드를 가리키는 포인터를 갖음
 *노드는 (데이터필드/링크필드)로 구성됨 
- 동적으로 크기가 조정가능 -> 삽입/삭제 시 링크필드를 간단히 조작하여 데이터 삽입/삭제 가능
- 처음부터 시작하여 원하는 노드를 검색 -> 탐색에서 배열보다 느림

3) 스택(Stack) 

- 데이터의 삽입과 삭제가 한쪽 끝에서만 이뤄지는 선형 리스트
- push(A->B->C)순, pop(C->B->A)순으로 '후입선출' (Last in First Out, LIFO) 

 

4) 큐(Queue) 

- 한쪽에서는 데이터의 삽입만, 한쪽에서는 데이터의 삭제만 이뤄지는 선형 리스트 
- '선입선출' (First In First Out, FIFO) 
- Front : 삭제가 이뤄질 곳을 가리킴 / Rear : 삽입이 이뤄질 곳을 가리킴 

 

2. 비선형 자료구조 
1) 트리

이미지 출처 :  tutorialspoint.com

- 하나 이상의 노드로 구성된 유한 집합, 노드와 간선으로 구성 
- 계층적 구조를 표현
- 탐색 및 삽입/삭제 연산 빠름 -> 정렬된 데이터 검색 시 유용
* 트리의 조건 
  ⓐ 원소에는 단 하나의 루트(root)노드 존재
  ⓑ 루트 노드 제외 나머지 노드는 부분집합으로 나뉘며, 각 부분집합(서브트리)는 트리가 됨

* 트리의 종류
  ⓐ 이진 트리 
    -각 노드의 차수가 2이하인 순서 트리
    -특징 : 레벨n에서 최대 노드 개수 : 2ⁿ (0레벨:1, 1레벨:2, 2레벨:4 ..)
               높이h인 이진 트리의 최대 노드 개수(h>=1) -> 2h-1(2의 h-1) 
    -종류 : 포화 이진 트리, 완전 이진 트리, 전 이진 트리, 균형 이진 트리 등 
* 용어
  ⓐ 차수 (노드의 차수, 트리의 차수) :
    -노드의 차수 : 노드가 가진 서브트리의 개수(가지 개수)를 의미
   -> 위 사진에서의 A의 차수는 3개, B의 차수는 2개, J는 차수가 0
    -트리의 차수 : 트리의 모든 노드의 차수 중 가장 큰 값 
  ⓑ 리프 노드(단말 노드), 비단말 노드 
    -리프 노드: 노드 차수가 0
    -비단말 노드: 리프 노드를 제외한 나머지 노드 
  ⓒ 레벨, 높이(깊이)
    -레벨 : 루트 노드로부터의 거리
    -높이(깊이) : 트리의 길이 -> 위 사진의 트리 높이 : 4 
 ⓓ 숲 
    -숲 : 여러 트리의 집합 (여러 개의 루트 노트)

2) 그래프 
- 그래프는 G = ( V, E) 도형으로 표현되는 비선형 자료구조  (V : 정점의 집합,  E : 간선의 집합)
 *그래프 종류 
 - 간선의 방향성 유무에 따라 무방향 그래프, 방향 그래프로 나뉨 
 - 가중 그래프(Weighted Graph) 각각의 간선이 가중치를 갖고 있는 그래프
 - 가중 그래프에선 각 간선이 얼마나 중요한지를 가중치 정보로 나타낸다.