CS/자료구조

자료구조 기본 1

RangA 2023. 4. 16. 17:22

자료구조 기본

자료구조

자료 구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.

자료 구조를 설명하기에 앞서, 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. 그러나 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다. 그렇기에 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.

데이터를 정해진 규칙 없이 저장하거나, 하나의 구조로만 정리하고 활용하는 것보다 데이터를 체계적으로 정리하여 저장해두는 것이 데이터를 활용하는 데 있어 훨씬 유리하다.

개발자들은 무수한 상황에 데이터를 효율적으로 다룰 수 있는 여러 방법을 연구해두었고, 이런 방법들을 모아 자료 구조라고 이름을 붙였다.

그 중 알고리즘 테스트에서 가장 자주 등장하는 네 가지는 다음과 같다.

Stack, Queue, Tree, Graph

대부분의 자료 구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다. 따라서 많은 자료 구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료 구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.

Stack

스택(Stack)은 '쌓다', '포개지다'와 같은 뜻을 지닌 단어로 데이터를 순서대로 쌓는 자료 구조이다. 대표적으로 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 활용된다.

Stack의 특징

  1. LIFO(Last In First Out)
    • 먼저 들어간 데이터가 가장 나중에 나오는 후입선출의 구조를 지닌다
예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다.

Stack<Integer> stack = new Stack<>(); //Integer형 스택 선언

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 스택이 빌 때까지 데이터를 전부 빼냅니다.

stack.pop();
stack.pop();
stack.pop();
stack.pop();
---------------------------

---------------------------
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.
  1. 데이터는 하나씩 넣고 뺄 수 있다
    • 많은 양의 데이가 있어도 한꺼번에 여러 데이터는 넣거나 뺄 수 없다
  2. 하나의 입출력 방향을 가지고 있다
    • Stack 자료 구조는 데이터의 입출력 방향이 같다

Queue

큐(Queue)는 '줄을 서서 기다리다', '대기행렬'이란 뜻을 지닌 단어로 데이터를 순서대로 처리하는 자료 구조이다. 대표적으로 프린터의 인쇄 기능을 구현할 때 사용된다.

Queue의 특징

  1. FIFO(First In First Out)
    • 먼저 들어간 데이터가 가장 먼저 나오는 선입선출의 구조를 지닌다
예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언

queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.add(3);     // queue에 값 3 추가
queue.add(4);     // queue에 값 4 추가

                           queue.add(데이터)
출력 방향 <---------------------------< 입력 방향
                     1 <- 2 <- 3 <- 4
                <---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.

queue.pull();       // queue에 첫번째 값을 반환하고 제거
queue.pull();
queue.pull();
queue.pull();

                           queue.pull()
출력 방향 <---------------------------< 입력 방향

                <---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.
  1. 데이터를 하나씩 넣고 뺄 수 있다
    • 많은 양의 데이터가 있어도 한꺼번에 여러 데이터를 넣거나 뺄 수 없다
  2. 두 개의 입출력 방향을 가지고 있다
    • Queue 자료 구조는 데이터의 입력과 출력 방향이 다르다

Tree

Tree는 이름 그대로 나무의 형태를 가지고 있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습이다. 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.

트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조이며, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.

트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.

Tree의 구조와 특징

트리 구조는 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가지며, 부모 노드(Parent Node), 자식 노드(Child Node)라고 부른다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.

트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조이다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.

  • 깊이(Depth)
    • 트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다. 루트 노드는 지면에 있는 것처럼 깊이가 0이고, 자식 노드로 깊어질수록 1씩 증가한다.
  • 레벨(Level)
    • 트리 구조에서는 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있다. depth가 0인 루트 노드의 level은 1이며, 아래로 갈수록 1씩 증가한다. 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다.
  • 높이(Height)
    • 트리 구조에서 리프 노드를 기준으로 루트까지의 높이(Height)를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다. 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.
  • 서브 트리
    • 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다.

Tree 용어 정리

  • 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
  • 루트(Root) : 트리 구조의 시작점이 되는 노드
  • 부모 노드(Parent Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
  • 자식 노드(Chile Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
  • 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

Graph

그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조이다.

컴퓨터 공학에서 이야기하는 자료 구조 그래프는 마치 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가지고 있다.

Graph의 구조

  • 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
  • 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
  • 하나의 점을 그래프에서는 정점(vertex)이라 표현하고, 하나의 선은 간석(edge)라고 한다.

Graph의 표현 방식

  • 인접 행렬
    두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접한다고 이야기한다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다. 만약 A라면 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표이다. 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장한다.
  • 인접 행렬 예시
    • A의 진출차수는 1개이다. (A -> C)
      • [0][2] == 1
    • B의 진출차수는 2개이다. (B -> A, B -> C)
      • [1][0] == 1
      • [1][2] == 1
    • C의 진출차수는 1개이다. (C -> A)
      • [2][0] == 1
  • 인접 리스트
    인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.
    순서는 보통 중요하지 않다. 그래프, 트리, 스택, 큐 등 모든 자료 구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가 및 삭제할 수 있다. 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있다. 이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있다. 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.

Graph 용어 정리

  • 정점(vertex) : 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
  • 간선(edge) : 정점 간의 관계를 나타냄(정점을 이어주는 선)
  • 인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
  • 가중치 그래프(weighted graph) : 연결의 강도가 얼마나 되는지 적혀져 있는 그래프
  • 비가중치 그래프(unweighted graph) : 연결의 강도가 적혀져 있지 않는 그래프
  • 무(방)향 그래프(undirected graph) : 일방통행이 없는 양방향 그래프
  • 진입차수(in-degree)/진출차수(out-degree) : 한 정점에 진입하고 진출하는 간선이 몇 개인지 나타냄
  • 인접(adjacency) : 두 정점 간에 간선이 직접 이어져 있는 것
  • 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다고 표현하며, 다른 정점을 거치지 않는다는 특징을 지님
  • 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 그래프를 사이클이 있다고 표현함

Binary Search Tree

트리 구조는 가지고 있는 특징에 따라 여러 가지 이름으로 불린다. 많은 트리의 모습 중, 가장 간단하고 많이 사용하는 것은 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)이다.

이진 트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.

이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Perfect Binary Tree)로 나눌 수 있다.

  이진 트리 종류     영어 표기     설명  
  정 이진 트리     Full Binary Tree     각 노드가 0개 혹은 2개의 자식 노드를 갖는다.  
  포화 이진 트리     Perfect Binary Tree     정 이진 트리이면서 완전 이진 트리인 경우이다.
모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.  
  완전 이진 트리     Complete Binary Tree     마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고
마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.  


이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한 쪽으로 노드들이 몰리게 될 수 있다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제로 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.

Search Algorithm

Tree traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회하고 한다.

트리를 순회할 수 있는 방법은 전위 순회, 중위 순회, 후위 순회로 세 가지 방법이 있다. 이 순회 방식과는 논외로 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽이다.

  • 전위 순회(preorder traverse)
    0->1->3->7->8->4->9->10->2->5->11->6
  • 중위 순회(inorder traverse)
    7->3->8->1->9->4->10->0->11->5->2->6
  • 후위 순회(postorder traverse)
    7->8->3->9->10->4->1->11->5->6->2->0

BFS / DFS

그래프의 가장 대표적인 정점 탐색 방법으로 BFS와 DFS가 있다.

  • BFS(Breathed-First Search)
    BFS는 너비를 우선적으로 탐색하는 방법으로 너비 우선 탐색이라고 한다. 주로 두 정점 사이에 최단 경로를 찾을 때 사용하며, 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 한다.
  • DFS(Depth-First Search)
    DFS는 깊이를 우선적으로 탐색하는 방법으로 깊이 우선 탐색이라고 한다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완벽히 탐색할 수 있다.
저작자표시 비영리 변경금지 (새창열림)