티스토리 뷰

CS/자료구조&알고리즘 공부

자료 구조(Data Structure) 개념 및 종류 정리

on1ystar 2021. 12. 15. 19:08
728x90
반응형

자료 구조란?

데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것.

예를 들어 한정된 크기의 책장이 있고, 넣어야 될 책들이 있다고 하자.

빈 책장

가장 많은 책을 넣는 방법은 아무 규칙 없이 있는 책을 모두 꽂아 넣는 것이다. 그럼 당장은 이 책장의 공간을 가장 효율적으로 사용한 것 같지만, 이후 책을 찾을 때 큰 문제가 발생한다. 아무 규칙 없이 책을 꽂아 넣었기 때문에 찾을 때도 규칙 없이 모든 범위를 찾아야 한다.

따라서 이번에는 책의 제목을 오름차순 형태로 꽂아 넣는다는 규칙을 세워 넣어 보면, 이후에 책의 제목을 이용해 어디에 꽂혀있는지 찾기가 훨씬 수월해질 것이다.

책 제목을 오름차순으로 정렬해 진열

또한 책의 모든 공간을 모두 사용할 수 있다. 다만 처음에 책을 꽂거나 이후에 책을 추가할 때 수고스러움이 생기게 된다.

이번에는 IT관련 서적을 찾고 싶은 사람이 있을 수 있다. 이 경우에는 위의 방법이 딱히 도움되지 않는다. 따라서 이번에는 다음과 같이 분야별로 분류해 책을 정리했다.

각 책장의 층을 분야별로 구분

이제 IT 관력 서적만 찾아볼 수 있다. 하지만 위 그림처럼 IT 서적은 더 진열해 놓고 싶은데 자리가 없고, 소설이 꽂혀있는 라인은 너무 여유롭다. 즉 공간의 비효율이 발생하기 시작한다. 이를 위해 다음과 같이 수정해 보자.

가림막 설치

가림막을 이용해 라인 별로 분류하는 것이 아닌 좀 더 공간을 효율적으로 사용해 남은 IT 관력 서적들을 모두 꽂아 넣었다. 하지만 가림막이 불필요한 공간을 차지하게 되고, 분류 역시 IT나 소설 분류가 밑으로 넘어가버려 책을 꽂을 때나 찾을 때 약간의 헷갈림이 발생할 수 있게 됐다.

서론이 매우 길었는데, 결국 예시의 책장과 책은 컴퓨터 세계에서는 메모리와 데이터로 유사하게 비유할 수 있다.

  • 책장 = 메모리
  • 책 = 데이터

물론 디테일이 많이 다를 수 있지만 전체적인 개념을 이해하는 데에는 무리가 없다고 생각한다. 연산에 사용되는 컴퓨터의 메모리 자원은 매우 한정적인데 반해 처리해야 할 데이터는 무수히 많을 수 있다. 따라서 이 메모리 공간을 효율적으로 사용해야 하는데 필요한 것이 자료 구조이다.

모든 목적에 맞는 자료구조는 없다. 따라서 각 자료구조가 갖는 장점과 한계를 잘 아는 것이 중요하다.

위의 간단한 예시에서도 책장 안에 다양한 이유와 목적을 가지고 책들을 진열할 수 있었다.

단, 자료 구조에서는 메모리 공간의 효율뿐만 아니라 실행 시간의 효율성도 따진다.

자료 구조와 알고리즘의 관계

Algorithm(알고리즘 또는 알고리듬)은 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것. 문제풀이에 필요한 계산절차 또는 처리과정의 순서다.

알고리즘의 중요한 특징은 같은 지식수준을 가진 사람이라면 그 알고리즘을 보고 누구나 같은 결과를 낼 수 있어야 한다. 요리의 레시피(recipe)에 비유해 볼 수 있다.

보통 자료 구조가 선택되면 그에 적용할 알고리즘은 거의 명확해진다. 즉, 자료 구조가 효율적인 알고리즘을 사용할 수 있게 함으로 자료 구조와 알고리즘은 매우 밀접한 관계를 가질 수밖에 없다.

위의 예를 다시 생각해 보면, 책장에 진열된 책들을 어떤 순서나 규칙을 가지고 찾을 지에 대한 방법이라고 생각하면 된다. 왼쪽부터 순서대로 찾을 수도 있고, 역순으로 찾을 수도 있고, 중간부터 찾을 수도 있다.

여기서 만약 클린 코드라는 책을 찾아야 할 때 책장에 진열되어 있는 구조에 따라 효율적으로 책을 찾는 방법이 달라지게 된다.

제목 순으로 진열되어 있다면 역순으로 찾는 방법을 선택하게 되고, 분야 별로 진열되어 있다면 IT 서적 쪽을 먼저 찾게 될 것이다.

즉, 위와 같이 보통은 자료 구조의 선택 → 효율적인 알고리즘의 선택이 된다.

또한 알고리즘을 프로그램 명령어들의 집합이라고도 한다.

프로그램은 특정 문제를 해결하기 위한 처리 방법과 순서를 기록한 명령어들의 모음이다. 이 프로그램이 실행되기 위해서는 메모리에 올릴 데이터가 필요하며 이 데이터들을 담아내는 방식은 자료구조다.

즉, 넓은 의미에서 자료구조 + 알고리즘(+a) = 프로그램이라고 할 수 있다.

위의 정의만 보면 프로그램 = 알고리즘 같아 보이지만, 디테일을 따지면 엄연히 다르다. 가장 간단한 예로 알고리즘은 항상 같은 결과를 보장하지만 프로그램은 그렇지 않을 수 있다.

필수 자료 구조 8개

자료 구조 분류

 

자료 구조 실행 시간 정리 표

 

1. Array(배열)

  • 동일한 타입의 데이터들을 저장하며, 고정된 크기를 가지고 있다.
  • 인덱싱이 되어 있어 인덱스 번호로 데이터에 접근할 수 있다.

→ 배열 목록, 힙, 해시 테이블, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용

→ 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용

2. Linked List(연결 리스트)

  • 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조
  • 동적인 데이터 추가/삭제에 유리하다.

  • 각 요소는 Node
  • 각 Node에는 key와 다음 노드를 가리키는 포인터인 next가 포함
  • 첫 번째 요소는 Head
  • 마지막 요소는 Tail

→ Alt + Tab을 사용하여 프로그램 간 전환

→ 갤러리

사실 위 배열과 연결 리스트는 아래의 자료 구조들을 구현하는 데 사용되는 기본 자료 구조들이다.

3. Stack(스택)

  • 순서가 보존되는 선형 데이터 구조
  • 가장 마지막 요소(가장 최근 요소)부터 처리하는 LIFO (Last In First Out)

→ 실행 취소

→ 수학적 표현식을 구문 분석하고 평가

→ 재귀 프로그래밍에서 함수 호출을 구현

4. Queue(큐)

  • 가장 먼저 입력된 요소를 처리하는 FIFO (First In First Out)

→ 멀티스레딩에서 스레드를 관리

→ 대기열 시스템

5. Hash table(해시 테이블)

  • 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조
  • 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적

→ 데이터베이스 인덱스 구현

→ 사용자 로그인 인증

→ "set" 데이터 구조 구현

보통 테이블 내에 더 작은 서브그룹인 버킷(bucket)에 키/값(key/value) 쌍(pair)을 저장한다.

단, 충돌이 자주 일어날 수 있으며 이를 위해 다양한 방법으로 해시 함수를 개선하거나 해시 테이블의 구조 개선(chaining, open addressing 등)의 방법이 사용된다.

(참고: 해시 충돌 개선)

6. Graph(그래프)

  • nodes/vertices(노드) 사이에 edge(엣지)가 있는 collection
  • directed(방향) 그래프는 일방통행
  • undirected(무방향) 그래프는 양방향

→ 소셜 미디어 네트워크를 나타내는 데 사용

→ 검색 엔진에 의해 웹 페이지 및 링크를 나타내는 데 사용

→ GPS에서 위치와 경로를 나타내는 데 사용

7. Tree(트리)

  • 그래프가 계층적 구조를 가진 형태
  • 최상위 노드(루트)를 가지고 있음
  • 상위 노드를 부모(parent) 노드, 하위 노드를 자식(child) 노드라 한다.

→ Binary Trees(이진트리)

→ Binary Search Tree(이진 검색 트리)

→ Heap(힙)

8. Heap(힙)

  • Binary Tree(이진트리)
  • 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다.
    • 루트 노드의 키 값이 트리의 최솟값
  • 최대 힙: 부모의 키 값이 자식의 키 값보다 크거나 같다.
    • 루트 노드의 키 값이 트리의 최댓값

최대 힙

→ 힙 정렬 알고리즘

→ 우선순위 큐

 

References

 

728x90
반응형
댓글