알고리즘 선행개념 — 2. 자료구조

자료구조의 정의

자료구조는 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 CS 기초이론입니다. 간단히 말하면 자료구조는 데이터를 메모리에 배치하고 저장하는 방식이라고 볼 수 있습니다.
자료구조를 구현하는데도 알고리즘이 필요합니다. 여기서 알고리즘은 자료를 조직하는 규칙을 논리적으로 구현하기 위해 쓰여요. 우리가 어떤 문제를 해결하기 위한 알고리즘을 구현할 때는 자료구조가 활용됩니다. 즉, 자료구조를 구현하는데는 알고리즘이 필요하고, 알고리즘으로 문제를 해결하기 위해선 자료구조가 필요한, 서로 상생하는 관계로 볼 수 있답니다.
자료구조는 대체적으로 대량의 데이터를 어떤 구조로 저장, 탐색, 삭제 해야 가장 효율적인지 탐구합니다. 여기서 효율적인 자료구조라 함은 프로그램의 실행시간 및 저장공간에서 효율이 높을 때를 의미합니다.

자료구조가 필요한 이유를 정리하면 다음과 같습니다.

• 현실의 문제를 컴퓨터 관점, 프로그래밍의 관점으로 어떻게 표현할지에 대해 고민하면서, 문제를 효율적으로 해결하기 위해 사용.
• 대량의 데이터에 대해 단시간의 최소한의 노력으로 원하는 결과(저장, 탐색, 삭제)를 얻기 위해 사용

좋은 자료구조의 특징으로 세 가지가 있습니다.

1. 효율성(Efficiency) : 데이터를 목적에 맞게 효율적으로 관리 및 사용
2. 추상화(Abstraction) : 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념만 간추림
3. 재사용성(Reusability) : 다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계

자료구조의 분류

효율적인 자료구조 활용을 위해서는 각 자료구조의 특성과 동작원리에 대한 이해가 필요합니다. 그 후에 현재 가지고 있는 자료가 ① 큰지 작은지 ② 탐색 빈도가 높은지 ③ 갱신(추가/삭제) 유무 등에 따라 자료구조를 선택할 수 있습니다.

• 단순 구조 : 컴퓨터가 기본적으로 제공하는 자료형
• 선형 구조 : 데이터들이 일렬로 쭉 저장되어 있는 형태. 인접 원소들 간 일대일 관계로 연결됨
• 비선형 구조 : 각 데이터가 1:N 또는 다대다로 연결되어 있는 형태.
• 파일 구조 : 보조 기억 장치에 저장되는 파일의 자료구조. 메모리에 한번에 올릴 수 없는 대용량을 다룸

위 분류표 중 선형구조와 비선형구조에 대해 아래에서 자세히 다뤄보도록 하겠습니다.

선형구조

리스트

1. 선형리스트

• 대표적으로 배열이 여기 속하며 물리적으로 연속되는 기억장소에 저장된다. 👉 기억장소를 연속으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다.
• 삽입 | 앞에서부터 순차적으로 삽입 가능하다. 중간 삽입이 어렵다.
• 탐색 | 인덱스로 접근하기 때문에 검색 속도가 빠르다.
• 삭제 | 모든 요소에 대해 삭제가 가능하나, 중간 위치의 요소를 삭제하면 빈칸을 메꾸기 위한 요소들의 이동이 필요하다.
  📌 제일 간단한 자료구조로, 순차적인 삽입 및 삭제에 가장 효과적이다. 빠른 검색이 필요할 때 사용하면 좋다.

2. 연결 리스트

• 자료들을 연속적으로 배치시키지 않고, 임의의 기억공간에 다음 항목의 링크를 기억시킨다. 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결한다. 👉 연결을 위한 링크를 기억해야 하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 좋지 않다.
• 삽입 | 어느 위치에 삽입해도 포인터의 링크변화만 있어 효율적이다.
• 탐색 | 인덱스가 없어 처음부터 포인터를 따라 탐색을 해야하기 때문에 검색 속도가 느리다.
• 삭제 | 어느 위치의 요소를 삭제해도 포인터의 링크변화만 있어 효율적이다.
  비선형구조의 트리를 표현할 때 가장 적합한 자료구조다.
  📌 탐색보다 삽입과 삭제의 비중이 높을 때 사용하면 좋다.

스택

• 리스트의 한 쪽 끝으로만 자료의 삽입과 삭제가 이루어진다.
  가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(Last In First Out) 방식이다.
• 삽입 | 가장 안쪽(Bottom)부터 순차적인 삽입만 가능하다. 명령어 PUSH.
• 탐색 | 탐색을 위한 자료구조가 아니다.
• 삭제 | 가장 바깥(Top)부터 순차적인 삭제만 가능하다. 명령어 POP.
  📌 함수 호출의 순서 제어, 복귀 주소 저장, 재귀 프로그램의 순서 제어 등에 쓰이며 히스토리를 기억해야할 때 사용하면 좋다.

큐

• 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어진다.
  가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(First In First Out) 방식이다.
• 삽입 | 가장 안쪽부터 순차적으로 삽입된다. 제일 마지막에 위치한 자료의 기억공간을 가르키는 포인터를 Rear라고 부르며 삽입작업이 이루어진다.
• 탐색 |탐색을 위한 자료구조가 아니다.
• 삭제 |가장 안쪽부터 순차적으로 삭제된다. 제일 첫 번째에 위치한 자료의 기억공간을 가르키는 포인터를 Front라고 부르며 삭제 작업이 이루어진다.
  📌 대기 행렬의 처리, 운영체제의 작업 스케줄링에 사용되며 선착순으로 자료를 처리할 때 사용하면 좋다.

큐

• 스택과 큐의 장점만 골라 만들어진 자료구조로, 리스트의 양쪽 끝에서 삽입과 삭제가 모두 가능하다.
• 삽입 | 양쪽 끝에서 모두 가능하다. 입력 제한 데크인 Scroll을 사용하면 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있다.
• 탐색 | 탐색을 위한 자료구조가 아니다.
• 삭제 | 양쪽 끝에서 모두 가능하다. 출력 제한 데크인 Shelf를 사용하면 출력이 한쪽에서만 발생하고 입력은 양쪽에서 일어날 수 있다.
  📌 우선순위를 주고 싶거나 새치기(?)를 허용할 때 사용하면 좋다.

비선형 구조

트리

• 정점(Node)와 선분(Branch) 을 이용하여 사이클이 이루어 지지 않도록 구성된 그래프의 특수한 형태이다.
• 트리는 계층 모델로 노드가 N개인 트리는 항상 N-1개의 가지를 갖는다.
• 어떤 노드로 가는 최단 경로는 유일하다.
• 차수(Degree) 는 각 노드에서 뻗어나온 가지의 수이다. 위에서 A의 차수는 4, C의 차수는 1, H의 차수는 3이다. 트리에서 가장 큰 차수의 값을 트리의 차수로 친다. 지금 트리의 차수는 4이다.
• 레벨(Level)은 트리의 각 층수를 의미한다. 루트 노드를 레벨 1로 보고 아래로 한층마다 1씩 증가한다.
• 단말 노드(Leaf Node) 는 자식이 하나도 없는 노드이다. 자식이 하나라도 있으면 비단말 노드이다.
• 자식 노드(Children Node) 는 어떤 노드에 연결된 다음 레벨의 노드들을 의미한다. 위에서 F와 G는 B의 자식 노드이다.
• 부모 노드(Parent Node) 는 자식노드와 반대로 어떤 노드에 연결된 이전 레벨의 노드이다. F와 G의 부모는 B 노드이다.
• 형제 노드(Sibling) 는 부모가 같은 노드를 의미한다. F와 G는 부모가 같으므로 형제 노드이다.
• 깊이(Depth) 는 트리에서 노드가 가질 수 있는 최대의 레벨을 의미한다. 이 트리의 깊이는 4이다.
• 더 알아보기🧐 : 이진트리의 종류와 순회의 종류는 잘 정리된 링크를 걸어두겠습니다.

그래프

• 그래프는 단순히 노드(Node)와 그 노드를 연결하는 간선(Edge)을 하나로 모아놓은 자료구조로 사이클이 존재할 수 있다. 그래프를 통해 연결되어 있는 객체 간의 관계를 표현할 수 있다.
• 트리와 달리 그래프는 루트와 부모-자식의 개념이 없다. 한 노드에 두개 이상의 경로가 연결될 수 있어 최단 경로의 갯수도 많아질 수 있다.
• 위 그래프에서 간선에 화살표가 없으면 무방향 그래프, 화살표가 있으면 방향 그래프라고 한다. 간선에 숫자가 적혀 있으면 가중치 그래프라고 부른다. 👉 방향 그래프에서는 화살표 쪽으로만 진행할 수 있고, 가중치 그래프에서는 간선의 가중치가 클수록 에너지가 많이 쓰이는 경로라고 볼 수 있다.
• 인접 정점(Adjacent Vertex) : 간선에 의해 직접 연결된 노드를 말한다.
  노드의 차수(Degree) : 무방향 그래프에서 하나의 노드에 인접한 노드의 갯수다. 인접 정점의 갯수와 동일한 의미이다.
• 집입 차수(In-Degree) : 방향 그래프에서 외부로부터 어떤 노드에게 오는 간선의 수이다. 사랑의 작대기를 몇 개 받았는지 세면 된다.
• 진출 차수(Out-Degree) : 방향 그래프에서 어떤 노드로부터 외부로 향하는 간선의 수이다. 여기선 사랑의 작대기를 여러 개 보낼 수 있다.
  경로의 길이 : 한 경로를 구성하는데 사용된 간선의 수이다.
• 더 알아보기🧐 : 그래프의 종류와 순회의 종류는 잘 정리된 링크를 걸어두겠습니다. 🔗