[자료구조] 1. 자료구조(Data Structure)란?

1. 자료구조(Data Structure)란?

 

 

자료구조 정의

• 자료구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하기 위해 조직하는 방법과 규칙
• 효과적인 자료구조를 통해 데이터를 빠르게 접근하고, 삽입, 삭제, 정렬, 탐색 등의 작업을 효율적으로 수행할 수 있음
• 다양한 자료구조들은 특정 상황에 맞게 최적화되어 있음
• 각 자료구조는 특정한 시간과 공간 효율성을 가짐

 

 

자료구조 분류

Primitive Data Structure

1. 기본 데이터 유형
2. 하나의 값만 가질 수 있음
3. 고정된 크기를 가짐
4. 정수, 실수, 문자, 논리형 등

 

Non-Primitive Data Structure

1. 복합 데이터 유형
2. 한번에 여러 값을 가질 수 있음
3. 가변 크기를 가짐
4. 배열, 연결리스트, 스택, 큐, 트리, 그래프 등

Linear Structure

1. 데이터들이 일렬로 저장되어 있는 형태
2. 메모리에서 연속적인 공간에 데이터를 저장하거나
3. 각 요소가 다음 요소와 직접 연결됨
4. 탐색이 간단하고 한 번에 하나의 방향으로 이동 가능
5. 배열, 연결리스트, 스택, 큐 등

Non-Linear Structure

1. 데이터가 계층적 또는 비연속적으로 되어있는 형태
2. 비연속적인 메모리 사용을 허용
3. 여러 경로로 접근 가능
4. 트리, 그래프 등

 

 

시간 복잡도

• 알고리즘이 실행되는 데 걸리는 시간을 입력 크기(n)와의 관계로 표현한 것
• 입력 크기가 커질 때 알고리즘의 실행 시간이 어떻게 변하는지를 나타내어, 알고리즘의 효율성을 평가하는 데 사용됨 
• 일반적으로, 시간 복잡도는 최악의 경우를 기준으로 하여 빅오(Big-O) 표기법을 사용해 표현함

Big-O

• 입력 크기 n이 증가할 때 실행 시간이 어떻게 증가하는지 나타내는 것
• 예를 들어, 실행 시간이 3𝑛^2+2𝑛+1인 알고리즘이 있을 때, n이 커질수록 𝑛^2  항이 가장 큰 영향을 주므로, 시간 복
• 도는O(n²)이 된다.
• 종류
  1. O(1) - 상수 시간(Constant Time) : 입력 크기와 상관없이 실행 시간이 일정. ex) 배열의 특정 인덱스에 접근
  2. O(log n) – 로그 시간(Logarithmic Time) : 입력 크기가 커질수록 실행 시간이 매우 완만하게 증가. ex) 배열에 이진 탐색으로 요소를 찾는 경우
  3. O(n) - 선형 시간(Linear Time) : 입력 크기에 비례하여 실행 시간 증가. ex) 배열의 모든 요소를 한 번씩 확인하는 경우
  4. O(n log n) - 로그 선형 시간(Log-linear Time)
  5. O(n²) - 이차 시간(Quadratic Time)
  6. O(2^n) - 지수 시간(Exponential Time)
  7. O(n!) - 팩토리얼 시간(Factorial Time)