- 알고리즘 : 문제를 해결하기 위한 일련의 단계적 절차를 정의하여 데이터를 처리하는 것
-> 좋은 알고리즘은 입력 크기가 커질수록 효율적으로 작동하고 빠른 실행속도를 나타냄 - 알고리즘 학습 : 특정 문제를 통해 알고리즘의 설계 및 분석 방법 습득
- 프로그래밍언어 -> 자료구조 -> 알고리즘 순으로 학습 (수학적 지식 동반)
- 자료구조는 데이터를 효율적으로 저장하고, 조직화하며, 관리하는 방법을 다룸.
프로그램이 사용하는 데이터를 적절한 형태로 저장하고 처리할 때 필수적.
자료구조는 다양한 유형이 각각의 특정 문제를 해결하는 데 최적화되어 있다.
<가장 기본적인 자료구조>
배열 / 연결 리스트 / 스택 / 큐 / 트리 / 그래프
선형 자료구조 비선형 자료구조
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) 트리
- 하나 이상의 노드로 구성된 유한 집합, 노드와 간선으로 구성
- 계층적 구조를 표현
- 탐색 및 삽입/삭제 연산 빠름 -> 정렬된 데이터 검색 시 유용
* 트리의 조건
ⓐ 원소에는 단 하나의 루트(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) 각각의 간선이 가중치를 갖고 있는 그래프
- 가중 그래프에선 각 간선이 얼마나 중요한지를 가중치 정보로 나타낸다.
'자료구조와 알고리즘' 카테고리의 다른 글
| 알고리즘 학습을 위한 기초지식 - 자료구조(2) (0) | 2023.04.27 |
|---|---|
| 자료구조의 기초 (0) | 2023.03.17 |
- 알고리즘 : 문제를 해결하기 위한 일련의 단계적 절차를 정의하여 데이터를 처리하는 것
-> 좋은 알고리즘은 입력 크기가 커질수록 효율적으로 작동하고 빠른 실행속도를 나타냄 - 알고리즘 학습 : 특정 문제를 통해 알고리즘의 설계 및 분석 방법 습득
- 프로그래밍언어 -> 자료구조 -> 알고리즘 순으로 학습 (수학적 지식 동반)
- 자료구조는 데이터를 효율적으로 저장하고, 조직화하며, 관리하는 방법을 다룸.
프로그램이 사용하는 데이터를 적절한 형태로 저장하고 처리할 때 필수적.
자료구조는 다양한 유형이 각각의 특정 문제를 해결하는 데 최적화되어 있다.
<가장 기본적인 자료구조>
배열 / 연결 리스트 / 스택 / 큐 / 트리 / 그래프
선형 자료구조 비선형 자료구조
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) 트리
- 하나 이상의 노드로 구성된 유한 집합, 노드와 간선으로 구성
- 계층적 구조를 표현
- 탐색 및 삽입/삭제 연산 빠름 -> 정렬된 데이터 검색 시 유용
* 트리의 조건
ⓐ 원소에는 단 하나의 루트(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) 각각의 간선이 가중치를 갖고 있는 그래프
- 가중 그래프에선 각 간선이 얼마나 중요한지를 가중치 정보로 나타낸다.
'자료구조와 알고리즘' 카테고리의 다른 글
| 알고리즘 학습을 위한 기초지식 - 자료구조(2) (0) | 2023.04.27 |
|---|---|
| 자료구조의 기초 (0) | 2023.03.17 |
