[Algorithm] 알고리즘 개요 & 자료구조

알고리즘(Algorithm) 개요 & 자료구조

알고리즘의 필요성

알고리즘은 왜 필요한가?

알고리즘은 무엇인가?

자료구조(Data Structure)

알고리즘과 자료구조의 상관 관계

• 자료구조라 함은 컴퓨터 기억공간 내에 자료를 표현하고 조직화하는 방법을 의미한다. 문제에 맞는 적절한 자료구조를 선택해야만 보다 효율적으로 자료를 처리할 수 있다.
• 결국, 좋은 프로그램을 만들려면 자료구조와 알고리즘이 적절히 조화를 이루어야 한다.

선형구조(Linear)와 비선형 구조(Non-Linear)

선형구조와 비선형 구조의 종류

• 선형구조란 자료를 순차적으로 나열시킨 형태
• 하나의 자료 뒤에 하나의 자료가 존재
• 자료 간의 앞뒤 관계가 1:1

선형 구조

• 비선형 구조란 하나의 자료 뒤에 여러 개의 자료가 존재
• 자료들 간의 앞뒤 관계가 1:n 또는 n:n의 관계

비선형 구조

선형/비선형 사진 출처: https://allg.tistory.com/29

[자료구조] 자료구조란?(선형구조, 비선형구조)

배열(Array)과 연결 리스트(Linked List)

배열(Array)

• 배열이란 같은 자료형을 갖는 여러 원소(데이터)를 하나의 변수 이름으로 모아 놓은 데이터의 집합이다. 배열은 인덱스(index), 원소 값(value) 쌍의 집합으로, 하나의 인덱스가 주어지면 이와 연관된 원소 값이 결정되는 대응 관계를 갖는다.
• 배열 표현의 가장 큰 특징은 데이터의 논리적 순서와 저장된 물리적 순서가 같다는 것이다.
• 장점
  • 표현이 간단하다.
  • 순서에 따른 순차적 데이터 접근이 아니라 인덱스를 이용하여 빠른 임의 접근이 가능하다.
• 단점
  • 메모리 크기가 정적이다.
  • 데이터 삽입/삭제 과정이 비효율적이다.(데이터들이 순차적으로 저장되기에, 데이터의 삽입과 삭제가 발생하는 경우에 시간적인 오버헤드(Overhead)가 발생한다)
  • 오버헤드(Overhead): 어떤 처리를 하기 위해 들어가는 간접적인 처리 사간, 메모리 등을 일컬음.
  • 데이터 재정렬 방식이 비효율적이다. (데이터의 논리적 순서와 동일하게 물리적 순서를 유지하기 위해서 데이터가 삽입/삭제가 수행되는 위치 이후에 있는 모든 데이터를 한 자리씩 뒤나 앞으로 이동시켜야 한다)
  • 배열의 크기 대부분은 정적으로 결정되기에 삽입과 삭제가 동적으로 발생하는 상황에서 적절한 배열의 크기를 미리 결정하는 것이 어렵고, 이로 인해 오버플로(Overflow)나 저장공간의 낭비를 초래할 수 있다.
  오버플로(Overflow): 컴퓨터의 정수 연산의 계산 결과가 허용 범위를 초과할 때 발생하는 오류. 메모리가 꽉 차서 발생되는 스택 오버플로(Stack Overflow)도 있다.

연결 리스트(Linked List)

• 배열의 문제점을 보완한 형태의 자료구조
• 물리적으로는 데이터를 기억장치의 어느 곳에 저장해도 되지만, 기억 장치의 임의 위치에 저장된 데이터 간의 논리적인 순서를 유지하는 것이 필요하다.
• 하나의 데이터를 저장할 때 논리적으로 다음 데이터가 어디에 저장되어 있는지를 함께 나타내야 한다. 이를 위해 데이터 필드와 링크 필드로 이루어진 노드라는 저장구조를 이용한다.
• 노드는 참조 시스템으로 작동된다. 데이터를 각 노드에 저장할 때 다음 수선의 자료가 있는 위치를 데이터에 포함시킨다. 이렇게 각 노드들은 서로 연결되어 있다.
• 장점
  • 새로운 데이터들의 삽입/삭제가 용이하고 효율적이다.
  • 논리적 순서와 물리적 순서를 반드시 일치시킬 필요 없다.
  • 새로운 데이터 삽입/삭제 시 배열처럼 구조의 재구성이 필요 없다.
  • 메모리 크기가 동적이다.
  • 대용량 데이터 처리에 적합하다.
• 단점
  • 배열보다 메모리 사용량이 많다.
  • 특정 데이터를 찾는데 비효율적이다.(특정 데이터를 찾기 위해 배열은 인덱스 값만으로 바로 접근이 가능하지만, 연결 리스트는 첫 번째 데이터를 가진 노드부터 시작해 원하는 데이터가 있는 노드까지 모든 노드를 찾아야 한다.)

배열과 연결 리스트의 종류

배열과 연결 리스트의 종류

• 배열은 인덱스 개수에 따라 1차원 배열과 다차원 배열(2차원, 3차원 배열)로 나뉜다.
• 단일 연결 리스트
  • 단방향으로 움직인다.
  • 하나의 링크 필드를 갖고 있다.
• 단일 원형 연결 리스트
  • 단방향으로 움직인다.
  • 하나의 링크 필드를 갖고 있다.
  • 마지막 노드와 첫 번째 노드가 서로 연결되어있어 순회한다.
• 이중 연결 리스트
  • 양방향으로 움직인다.
  • 두 개의 링크 필드를 갖고 있기에, 선행 노드와 후행 노드 전부 접근 가능하다.
  • 선행 노드에 직접적으로 접근이 가능하다.
• 이중 원형 연결 리스트
  • 양방향으로 움직인다.
  • 두 개의 링크 필드를 갖고 있기에, 선행 노드와 후행 노드 전부 접근 가능하다.
  • 선행 노드에 직접적으로 접근이 가능하다.
  • 마지막 노드와 첫 번째 노드가 서로 연결되어있어 순회한다.

스택(Stack)과 큐(Queue)

스택(Stack)

• 스택은 선형 리스트의 한쪽에서만 데이터의 삽입과 삭제가 발생하는 자료구조
• 스택은 가장 나중에 삽입된 데이터가 가장 먼저 삭제되기 때문에 후입선출(LIFO, Last In First Out) 리스트라고도 일컫는다.
• 삽입 연산은 push, 삭제 연산은 pop을 사용한다.

큐(Queue)

• 큐는 선형 리스트의 한쪽 끝에서는 데이터의 삽입만 수행되고 다른 한쪽 끝에서는 데이터의 삭제만 수행되는 자료구조
• 큐는 가장 먼저 삽입된 데이터가 먼저 삭제되므로 선입선출(FIFO, First In First Out) 리스트라고도 일컫는다.

트리(Tree)

• 트리는 노드(node)가 간선(edge)으로 연결되어 계층적 구조를 이루는 비선형 자료구조

트리

트리 주요 용어

• A, B, C, D 등 트리의 구성요소가 노드(node)
• 트리 구조 최상위에 존재하는 노드는 루트(root) 노드
• 루트 노드를 기준으로, 다른 노드로 접근하기 위한 것이 깊이(depth)
• 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 형제(sibling) 노드로 일컫는다.
• 루트노드 A와 B, C, D는 부모(parent) 자식(child) 관계이다.
• 노드와 노드를 잇는 선이 간선(edge)
• 노드의 서브 트리 개수를 차수(degree). A의 노드 차수는 3, C의 노드 차수는 0이다. 트리 차수는 노드의 차수 중 가장 큰 값을 일컫는다. 트리의 차수는 3이다.
• 차수가 0인 노드를 리프(leaf) 노드 혹은 단말 노드(terminal node)이다.
• 숲(forest) 이란 서브 트리의 집합으로 트리에서 루트 노드를 제거하면 숲이 된다.

이진 트리(Binary Tree)

• 이진 트리란 각각의 노드가 최대 두 개의 자식 노드를 가지는 즉, 각 노드의 차수가 2 이하인 순서 트리

이진 트리

• 공백도 이진 트리로 포함한다.
• 이진 트리는 순서에 따라 달라지기에 5번째, 6번째 트리는 서로 다른 트리이다.

이진 트리 특성

이진 트리 종류

이진 트리 구현

그래프(Graph)

• 그래프는 G=(V, E)는 도형으로 표현되는 비선형 자료구조
• G=그래프(Graph), V=정점, 노드(Vertex, Node), E=간선(Edge)
• 연결할 객체를 나타내는 정점의 집합 V와 정점을 연결하는 간선의 집합 E로 구성된다.
• 그래프는 간선의 방향성 여부에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 구분된다.
• 무방향 그래프는 간선을 나타내는 두 정점의 쌍에 순서가 없으며, 점점 u에서 정점 v사이의 간선을 (u, v) 또는 (v, u)로 표시한다.
• 방향 그래프는 정점 u에서 정점 v로의 간선을 <u, v>로 표시하며, 이때 u는 꼬리이고 v는 머리라고 한다.
• 간선에 비용이나 시간과 같은 의미를 갖는 가중치를 부여한 그래프를 가중 그래프(Weighted Graph)라고 한다.

그래프

그래프 주요 용어

• 인접(adjacent), 부수(incident): 두 정점 u, v 사이에 간선이 있으면 u와 v는 인접한다고 하며, 해당 간선은 정점 u, v에 부수되었다고 한다.
• 경로(path): 그래프 G에서 정점 v1로부터 정점 vn까지의 경로란 간선으로 연결된 정점의 순서 리스트를 말하며, 경로에 존재하는 간선의 개수를 길이(length)라고 한다.
• 차수(degree): 해당 정점에 부수된 간선의 수를 의미. 방향 그래프에서는 차수를 세분화하여 정점으로 들어오는 간선의 수를 진입 차수(in-degree)라고 하고, 그 정점에서 나가는 간선의 수를 진출 차수(out-degree)라고 한다.
• 단순 경로(simple path): 한 경로상에서 처음과 마지막 정점을 제외한 모든 정점이 서로 다른 경로를 말한다.
• 사이클(cycle): 처음과 마지막 정점이 같은 단순 경로를 말하며, 특히 사이클이면서 경로의 길이가 1인 경로를 루프(loop)라고 한다.

그래프 구현

본 글은 한국방송통신대학교 자료와 개인 공부로 만들어졌습니다.