[특강] 자료구조와 알고리즘

1. 자료구조와 알고리즘

자료구조 : 자료를 효율적으로 관리하는 방법

알고리즘 : 목적지까지 최적의 이동 경로를 찾는 방법

 

2. 자료구조의 종류

1) 선형 자료구조 : 리스트, 스택, 큐

 - 데이터를 한 줄로 순차적으로 표현한 형태.

2) 비선형 자료구조 : 트리, 그래프

 - 하나의 데이터 뒤에 여러 개가 이어지는 형태.

 

3. 알고리즘 성능 : 시간 복잡도

- 데이터 양이 많아질수록 시간 복잡도가 크면 성능에 무리가 생김

- 좋은 알고리즘은 시간 복잡도가 작은 알고리즘

- 빅-오 표기법 : O(f(n)) 

 ( O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) ... )

 

---

1. 선형 리스트 : 데이터를 일정한 순서로 나열. 순차 리스트. 

 - 입력 순서대로 저장하는 데이터에 적당

 - 데이터만 있어도 됨. 접근 속도 빠름

 - 시계열 데이터 (시간 순서로 생성) : 신문의 날짜별 기사. 도서 연대별...

2. 단순 연결 리스트 : 물리적으로 떨어진 곳에 위치해있음. 선형 리스트와 유사

>>> 선형리스트에서 데이터 삽입은 오버헤드가 발생할 수 있으나

        단순연결리스트에서는 노드구조를 가지고 있어 링크 연결만 바꿔주면 됨

1) 노드 구조 : 클래스를 이용해서 노드 생성. 노드에 링크와 데이터 각각 저장

2) 일반 형태로 구현하기.

head : 첫번째 노드

current : 지금 처리중인 노드

pre : 지금 처리중인 노드의 바로 앞 노드

3. 원형 연결 리스트 : 단순 연결에서 끝과 앞이 이어져있음. 

 

---

1. 스택 : 가장 먼저 넣은걸 가장 마지막에 만날 수 있음. (선입후출, 후입선출) 한쪽 끝이 막힌 형태. 

 1) 스택 기본구조 : push(삽입), pop(추출), top(가장 위 데이터)

 - push : top 초기값은 -1로 설정해놓음. top = -1인 경우 스택이 비어있는 경우임. top을 하나 증가시키고 해당 값에 push함.

 - pop : top위치의 데이터를 추출함. top을 한칸 아래로 이동

2. 큐 : 입구와 출구가 따로 있는 원통 형태.

 - enQueue : 큐에 데이터 삽입

 - deQueue : 데이터 추출하는 작동

 - front : 저장된 데이터 중 첫 번째 데이터

 - rear : 저장된 데이터 중 마지막 데이터

 + 큐는 끝값(rear)을 보고 꽉 찼는지 아닌지 알 수 있음. 앞에 값이 나가도 꽉 찬 적이 있다면 더 삽입할 수 없다.

3. 원형 큐 

 - 머리와 꼬리가 이어져있는 큐. front와 rear 모두 0으로 시작해서 다음에 front = rear이 되는 경우 꽉 찬것으로 보면 됨.

4. 이진 트리

 - 나무를 거꾸로 뒤집어 놓은 형태. 자식이 최대 두개 (없어도 됨)

 - 왼쪽 서브트리는 더 작은값, 오른쪽 서브트리는 더 큰 값

 5. 그래프

1) 무방향 그래프 : 간선에 방향성이 없는 그래프

2) 가중치 그래프

3) 그래프 순회 방식

 (1) 깊이 우선 탐색

 (2) 너비 우선 탐색