자료구조

자료구조

• 데이터 집단을 어떻게 관리 해야할까?
• 기초적인 배열도 자료구조지만  한계가 있음
• 자료구조는 수많은 데이터를 효율적으로 관리하는 기법이다

---

 

자료구조란?

1. 자료를 왜 정리해서 보관해야 할까?
   • 방대한 양의 자료가 있고 규칙없이 막 던져둔다면 필요할 때 찾기힘듬
   • 물건을 분류별로 나열해 놓으면 나중에 찾기 쉽듯, 데이터도 어떤 형태로 배치하고 분류하는지 따라 더 찾기 쉬워짐
2. 자료를 정리하는 기준
   • 순서대로 배치해 데이터가 어디있는지 안다면 더 쉽게 접근가능
   • 데이터 간의 관계도를 구축해 하나의 데이터를 불러들이면 연관된 데이터가 어떤게 있는지 참조도 가능

---

대표적인 자료구조의 형태

1. 선형 자료구조
   • 일렬로 쭉 나열된 형태로 원하는 자료가 어떤 위치에 있는지 안다면 금방 찾을 수 있음
2. 비선형 자료구조
   • 자료 사이의 관계도를 표현할 때 사용할 수 있음

---

자료구조 효율 판단

1. 효율을 판단하는 이유
   • 더 좋은 성능의 프로그램을 만들기 위해
2. Big-O 표기법
   • 데이터 연산에 대한 성능을 표현하는 수학적 표기법
   • 알고리즘에 대한 성능을 예측하는 것이 목적
3. 공간 복잡도
   • 프로그램의 실행부터 완료까지 필요한 저장공간의 양
   • 현대의 PC는 하드웨어의 발달로 덜 중요한 개념이 되었음
4. 시간 복잡도
   • 프로그램의 실행부터 완료시까지 필요한 과정의 양
   • 알고리즘의 효율성을 결정하는 중요한 요소
   • 읽기, 삽입, 검색, 삭제에 대한 동작에 대해서 측정

요약

개념	측정 대상	표기법	관심 영역
시간 복잡도	연산 횟수 (실행 속도)	O (Big-O)	입력이 커질 때 알고리즘이 얼마나 느려지는가
공간 복잡도	메모리 사용량	O (Big-O)	입력이 커질 때 메모리를 얼마나 더 사용하는가
Big-O	상한선 (Worst-Case)	O(N), O(N2), 등	알고리즘의 비효율성을 나타내는 표준

---

Big-O표기법

• 빅오 표기법은 알고리즘 실행 시간 또는 사용 메모리의 상한선 즉 최악의 경우의 성능을 나타냅니다
• 입력 데이터의 크기(N)가 증가함에 따라 알고리즘 성능이 얼마나 빠르게 나빠지는지 나타내는데 중점을 둠

 

표기법	명칭	성능 특징 (예시)
O(1)	상수 시간 (Constant Time)	입력 크기와 관계없이 일정한 시간이 걸림. (예: 배열의 특정 인덱스 접근)
O(logN)	로그 시간 (Logarithmic Time)	입력 크기가 커져도 시간이 매우 느리게 증가함. (예: 이진 검색, Binary Search)
O(N)	선형 시간 (Linear Time)	입력 크기에 비례하여 시간이 증가함. (예: 배열의 모든 요소 순회)
O(NlogN)	선형-로그 시간 (Linearithmic Time)	비교적 효율적이며, 정렬 알고리즘에서 많이 사용됨. (예: 병합 정렬, Merge Sort)
O(N2)	2차 시간 (Quadratic Time)	입력 크기의 제곱에 비례하여 시간이 증가함. 비효율적임. (예: 이중 루프를 사용한 버블 정렬)