(CS) 자료구조 기초

자료구조

• 추상 데이터 타입(Abstract Data Type, ADT): 데이터와 그 데이터에 적용할 수 있는 연산을 정의한 개념적 모델
• 알고리즘(Algorithm): 문제를 해결하기 위한 일련의 명확한 단계나 절차
• 자료구조(Data Structure): 데이터를 조직하고 저장하는 방법을 정의한 구체적인 구현
• 데이터 구조 구현(Data Structure Implementation): 특정 프로그래밍 언어로 자료구조를 실제로 구현한 것

이상적인 자료구조

완벽한 자료구조는 없지만, 이상적인 자료구조는 다음과 같은 특성을 가질 것이다.

• 빠름(Fast): 연산이 빠르게 수행되어야 함
• 적은 메모리 사용(Low Memory Usage): 메모리를 효율적으로 사용
• 단순함(Simple): 구현이 간단하고 이해하기 쉬워야 함

하지만 현실에서는 이걸 모두 만족하는 자료구조는 존재하지 않는다. 그래서 우리는 특정 상황에 맞는 자료구조를 선택해야 한다.

생기는 충돌

속도(Time) vs 메모리(Memory)

Array: 빠른 접근 속도를 제공하지만, 크기가 고정되어 있고 삽입/삭제가 느릴 수 있음
Linked List: 삽입/삭제가 빠르지만, 접근 속도가 느릴 수 있음

단순함(Simplicity) vs 범용성(Generality)

Array: 범용적으로 사용되지만, 크기가 고정되어 있고 삽입/삭제가 느릴 수 있음
Linked List: 단순한 구조로 구현이 쉽지만, 배열보다 접근 속도가 느릴 수 있음

특정 연산은 빠름(One operation) vs 다른 연산은 느림(Another)

연산	Array	Linked List
검색	빠름 O(1)	느림 0(n)
삽입	느림 O(n)	빠름 O(1)

결론

자료구조 공부 = 트레이드 오프를 이해하는 것

각 상황에 따라 맞는 자료구조가 다르기 때문에, 트레이드 오프를 이해하고 적절한 자료구조를 선택하는 것이 중요하다.