데이터 구조의 핵심 개념
데이터 구조 관련 용어
데이터
- 정의: 정보를 담는 매체로, 기호들의 집합입니다. 컴퓨터 프로그램이 처리하는 원재료 역할을 합니다.
데이터 요소
- 정의: 데이터의 기본 단위로, 일반적으로 하나의 완전한 개체를 의미합니다.
- 데이터 항목: 데이터 요소를 구성하는 더 이상 분할할 수 없는 최소 단위입니다.
- 예시: 학생 정보는 하나의 데이터 요소이며, 학번, 이름 등의 데이터 항목으로 구성됩니다.
데이터 객체
- 정의: 동일한 특성을 가진 데이터 요소들의 모임으로, 데이터의 부분 집합입니다.
- 예시: 정수 데이터 객체는 집합 \\(N=\\{0, \\pm 1, \\pm 2, \\dots\\}\\)입니다.
데이터 타입
- 정의: 값의 집합과 해당 값에 대한 처리 연산을 통합한 개념입니다.
- 종류:
- 원자 타입: 값을 더 이상 분할할 수 없는 데이터 타입
- 구조 타입: 값을 여러 구성 요소로 나눌 수 있는 데이터 타입
- 추상 데이터 타입(ADT): 수학적 모델과 그 위에서 정의된 연산들의 집합으로, 데이터의 범위와 구조 형태, 데이터 연산들을 정의합니다.
데이터 구조
- 정의: 서로 하나 이상의 관계를 가지는 데이터 요소들의 집합입니다.
- 구조: 데이터 요소들 간의 상호 관계를 의미합니다.
- 데이터 구조 구성 요소:
- 논리 구조
- 저장 구조
- 데이터 연산
알고리즘 설계는 선택된 논리 구조에 의존하며, 구현은 저장 구조에 따라 결정됩니다.
데이터 구조의 세 가지 구성 요소
데이터의 논리 구조
- 정의: 데이터 요소들 간의 논리적 관계로, 데이터를 논리적 관점에서 기술합니다.
- 선형 구조
- 선형 리스트
- 비선형 구조
- 집합
- 트리
- 그래프
데이터의 저장 구조
- 정의: 데이터 구조가 컴퓨터 내에서 표현되는 방식으로, 물리 구조라고도 합니다. 데이터 요소들의 관계와 관계 표현을 포함합니다.
- 분류:
- 순차 저장
- 특징: 논리적으로 인접하면 물리적 위치도 인접합니다.
- 장점: 임의 접근이 가능합니다.
- 단점: 외부 단편화가 발생할 수 있습니다.
- 연결 저장
- 특징: 단편화 현상이 없습니다.
- 장점: 단편화가 발생하지 않습니다.
- 단점: 포인터 저장을 위한 추가 공간이 낭비됩니다.
- 인덱스 저장
- 특징: 정보 저장과 동시에 인덱스 테이블을 구축합니다.
- 인덱스 항목: 인덱스 테이블의 각 항목으로, 일반적으로 (키, 주소) 형태입니다.
- 장점: 검색 속도가 빠릅니다.
- 단점: 데이터 추가와 삭제 시 인덱스 테이블 유지에 시간이 소요됩니다.
- 해시 저장
- 특징: 요소의 키워드를 이용해 직접 저장 주소를 계산합니다.
- 장점: 검색, 추가, 삭제 연산이 모두 빠릅니다.
- 단점: 해시 함수가 적절하지 않으면 요소 저장 단위 충돌이 발생하며, 충돌 해결을 위해 추가 시간과 공간이 필요합니다.
- 순차 저장
데이터의 연산
- 정의: 연산의 정의와 구현을 포함합니다.
- 연산 정의: 논리 구조를 대상으로 하며, 연산의 기능을 명시합니다.
- 연산 구현: 저장 구조를 대상으로 하며, 연산의 구체적 실행 단계를 명시합니다.
알고리즘과 성능 평가
알고리즘의 기본 개념
정의: 알고리즘은 특정 문제를 해결하기 위한 단계별 설명으로, 유한한 명령어들의 순서이며 각 명령어는 하나 이상의 연산을 나타냅니다.
알고리즘의 다섯 가지 중요 특성:
- 유한성: 알고리즘은 유한한 단계 실행 후 종료되어야 하며, 각 단계는 유한 시간 내에 완료되어야 합니다.
- 명확성: 각 명령어는 명확한 의미를 가지며, 동일한 입력에 대해 동일한 출력을 생성해야 합니다.
- 실행 가능성: 알고리즘에 기술된 연산들은 모두 이미 구현된 기본 연산들을 사용해 유한 횟수 내에 실행 가능해야 합니다.
- 입력: 알고리즘은 0개 이상의 입력을 가집니다.
- 출력: 알고리즘은 1개 이상의 출력을 생성합니다.
좋은 알고리즘의 목표:
- 정확성: 문제를 올바르게 해결합니다.
- 가독성: 이해하기 쉬워 인간이 파악하기 용이합니다.
- 견고성: 잘못된 데이터에 대해 반응하며, 이상한 출력을 생성하지 않습니다.
- 효율성과 낮은 저장소 요구:
- 효율성: 알고리즘의 실행 시간
- 저장소 요구: 알고리즘 실행 중 필요한 최대 저장 공간
알고리즘 효율성 측정
시간 복잡도
- 명령어 빈도: 알고리즘 내에서 명령어가 반복 실행되는 횟수입니다.
- 빈도 합: \\(T(n)\\)
- \\(n\\): 알고리즘 문제의 규모입니다.
- 시간 복잡도
- 정의: 알고리즘의 기본 연산 실행 횟수의 수량적 규모입니다.
- 목적: 주로 \\(T(n)\\)의 수량적 규모를 분석합니다.
- 표기: \\(O(f(n))\\)
- \\(O\\): 수량적 규모를 나타냅니다.
- 엄밀한 수학적 정의: \\(T(n)\\)과 \\(f(n)\\)이 양의 정수 집합에서 정의된 두 함수일 때, 양의 상수 \\(C\\)와 \\(n\_{0}\\)이 존재하여 \\(n\\geq n\_{0}\\)일 때 \\(0\\leq T(n)\\leq Cf(n)\\)을 만족합니다.
- 분류:
- 최악 시간 복잡도: 일반적으로 최악의 상황을 고려합니다.
- 최선 시간 복잡도: 최상의 상황에서의 알고리즘 시간 복잡도입니다.
- 평균 시간 복잡도: 알고리즘의 기대 실행 시간입니다.
시간 복잡도 연산 규칙:
- 덧셈 규칙:
- \\(T(n)=T\_{1}(n)+T\_{2}(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))\\)
- 곱셈 규칙:
- \\(T(n)=T\_{1}(n)\\times T\_{2}(n)=O(f(n))\\times O(g(n))=O(f(n)\\times g(n))\\)
덧셈 규칙 예제:
// x: O(1)
x {
y {} // y: O(n^2)
z {} // z: O(n)
}
최종 복잡도: \\(O(1\\times O(max(n^{2}, n)))=O(n^{2})\\)
곱셈 규칙 예제:
x { // x: O(1)
y { // y: O(n^2)
z { } // z: O(n)
}
}
최종 복잡도: \\(O(n^{2}\\cdot n\\cdot 1)=O(n^{3})\\)
일반적인 점근적 시간 복잡도 순서:
\[O(1)<O(\log_{2}n)<O(n)<O(n\log_{2}n)<O(n^{2})<O(n^{3})<O(2^n)<O(n!)<O(n^n) \]
공간 복잡도
기호: \\(S(n)\\)
정의: 알고리즘이 요구하는 저장 공간입니다.
표기:
\[S(n)=O(g(n)) \]
예시: 데이터 규모 \\(n\\)과 동일한 보조 배열을 사용하면 공간 복잡도는 \\(O(n)\\)입니다.
알고리즘 내부 작업: 필요한 보조 공간이 상수일 때, 즉 \\(O(1)\\)을 의미합니다.