자료구조

개요

자료구조는 컴퓨터 과학에서 데이터를 효율적으로 저장, 관리, 접근 할 수 있도록 설계된 체계적인 조직 방식. 자료구조는 데이터의 물리적 저장 방식뿐만 아니라 해당 데이터에 적용될 수 있는 연산의 집합도 포함된다!!

자료구조의 선택은 알고리즘의 효율성에 직접적인 영향을 미치며, 프로그램의 성능을 결정하는 중요한 요소 중 하나다. 동일한 데이터를 사용하더라도 어떤 자료구조를 사용하느냐에 따라 프로그램의 실행 시간과 메모리 사용량이 크게 달라질 수 있기 때문이다.

사용하는 이유

효율성의 극대화와 추상화를 통한 개발의 용이성 확보를 위함

1. 효율적인 자원 관리

프로그램이 처리해야 하는 데이터의 양이 증가함에 따라, 데이터를 찾거나 추가, 삭제하는 작업에 소요되는 시간은 급격히 늘어날 수 있다. 자료구조는 다음과 같은 측면에서 컴퓨터 자원의 효율적인 관리를 가능하게 한다.

• 시간 복잡도(Time Complexity) 최적화: 특정 연산(e.g. 검색)에 소요되는 시간을 최소화하여, 프로그램이 대규모 데이터셋에서도 빠르게 동작하도록 보장한다. 만약 무작위 접근(Random Access)이 중요한 경우 배열(Array)이 적합하며, 삽입과 삭제가 빈번한 경우 연결 리스트(Linked List)가 유리하다.

• 공간 복잡도(Space Complexity) 절약: 필요한 메모리 공간을 최소화하여 시스템 리소스의 낭비를 방지한다. 자료구조는 오버헤드(Overhead)를 최소화하는 방식으로 데이터를 저장한다.

2. 추상화 및 재사용성

자료구조는 프로그래밍에서 추상적 데이터 타입 (ADT : Abstract Data Type)의 개념을 구현한다.

스택을 예시로 간단히 설명하자면,

• ADT : 데이터와 그 데이터에 적용되는 연산되는 집합을 정의하는 논리적 모델. Stack의 경우 LIFO(Last-In,First-Out)라는 논리적 규칙(ADT)를 정의하며 이를 배열이나 연결 리스트를 사용하여 구현할 수 있다.
• 개발 용이성 : 내부 구현 방식에 구애받지 않고, 스택의 push와 pop이라는 추상적인 연산을 사용하여 문제를 해결할 수 있다. 이는 코드의 재사용성을 높이고 유지보수를 용이하게 해준다.

핵심 개념

ADT

ADT는 자료구조의 개념적 명세를 의미한다. 데이터가 무엇이고, 어떤 연산이 가능한지에 대해 초점을 맞추고, 어떻게 구현 될지는 명시하지 않는다. 이를 통해 내부 구현과 관계없는 일관된 인터페이스를 제공하도록 한다.

연산

대부분의 자료구조는 다음 네 개의 기본 연산을 중심으로 설계된다.

• 탐색
• 삽입
• 삭제
• 순회

복잡도 분석

자료 구조의 성능을 객관적으로 측정하는 도구, 입력 크기 $N$에 따라 필요한 자원이 얼마나 증가하는지를 함수로 표현하는 것.

복잡도는 시간 복잡도와 공간 복잡도가 있다.

시간 복잡도 문서 바로가기

표기법	의미	예시
$O(1)$	상수 시간 : 입력 크기에 관계 없이 일정한 연산	해시 맵에서 특정 키를 이용한 삽입
$O(log N)$	로그 시간 : 입력 크기가 커져도 연산 증가율이 낮음	이진 탐색 트리에서의 탐색
$O(N)$	선형 시간 : 입력 크기에 비례하여 연산 시간 증가	배열에서 특정 값 검색
$O(N^2)$	다항시간 : 입력 크기의 제곱에 비례하여 연산 시간 증가	선택 정렬, 버블 정렬

공간 복잡도 : 알고리즘이 실행을 완료하는 데 필요한 메모리 공간의 양을 $N$의 함수로 표현하는 것.

종류

선형 자료구조

데이터 요소들이 순서에 따라 일렬로 나열되어 저장되는 구조.

• 배열(Array) : 메모리 상에 연속적으로 저장된다. 인덱스를 통한 $O(1)$ 접근이 가능한 정적 혹은 동적 크기의 컬렉션
• 연결 리스트(Linked List) : 각 노드가 데이터와 다음 노드의 주소를 담고 있어 메모리상에 비연속적으로 저장될 수 있는 구조, 삽입/삭제가 배열보다 용이함
• 스택(Stack) : LIFO 규칙을 따르는 선형 구조
• 큐(Queue) : FIFO 규칙을 따르는 선형 구조

비선형 자료구조

데이터 요소들이 일렬로 연결되지 않고 계층적이거나 무작위적인 형태로 연결된 구조.

• 트리(Tree) : 계층적 구조를 표현하는 비선형적 자료구조. 노드들이 간선으로 연결되며, 루트(Root) 노드가 최상위에 위치함.
  • 이진 트리
  • 이진 탐색 트리
  • 힙
  • 균형 트리
• 그래프 : 노드(Vertex)와 이를 연결하는 간선(Edge)의 집합으로 이루어진 구조로 네트워크 소셜 관계 등 복잡한 연결 관계에 사용

해싱 및 기타 구조

• 해시 테이블 및 해시 맵 (Hash Table / Hash Map) : 키를 해시 함수를 통해 Index로 변환하여 데이터를 저장하는 구조, 평균적으로 $O(1)$의 빠른 삽입 및 검색 속도를 가진다.
• 집합(Set) : 중복을 허용하지 않는 데이터의 모음

여담

• 코딩 테스트에서 우리를 괴롭히는 그 알고리즘 문제가 자료구조를 활용해야 하는 경우가 많다.
• 모르는 곳에서 이미 패키지를 통해 최적화 된 자료구조를 사용하고 있는 경우가 많다.
• 각 언어가 지원해주는 자료형을 알고 있는 것도 좋다.