자료구조와 알고리즘의 차이

서론

알고리즘과 자료구조의 차이가 있다는 것은 알고 있지만 정확하게 어떤 차이가 있는지 헷갈렸던 적이 많다. 이번 포스팅을 통해 둘 사이에 정확하게 어떤 차이가 있는지 알아보자.

자료구조

자료구조는 말 그대로 자료(data)를 담는 구조이다. 자세히 말하면 컴퓨터 과학에서 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 책장을 예로 들어보면, 책장에 책을 꽂아 넣으려고 하는데 책을 알파벳 순서로 꽂아둘 것인지 아니면 책상에 쌓아 올려둘 것인지를 결정하는 것, 즉, 이런 데이터가 저장된 형태를 결정하는 것이 자료구조이다.

자료 구조의 분류

자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라 여러 가지 종류의 자료구조 중 하나를 선택할 수 있다. 자료구조의 종류로는 자료형의 따라 분류하는 단순 구조와 자료 간 관계가 1 대 1인 선형 구조, 1 대 다 혹은 다 대 다 구조인 비선형 구조, 마지막으로 파일 구조가 있다.

간단히 분류를 해보자면

구현에 따라

• 배열 : 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
• 튜플 : 둘 이상의 자료형을 묶음으로 다루는 구조이다.
• 연결 리스트 : 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
• 원형 연결 리스트 : 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
• 이중 연결 리스트 : 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
• 환형 이중 연결 리스트 : 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.
• 해시 테이블 : 개체가 해시값에 따라 인덱싱된다.

형태에 따라

<선형 구조>

• 스택 : 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
• 큐 : 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
• 환형 큐 : 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐이다.
• 덱 : 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.

<비선형 구조>

• 그래프 : 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
• 유향 그래프, 무향 그래프 : 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.
• 트리 : 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다.
• 이진 트리 : 자식이 최대 두 개인 트리.
• 힙 : 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.

알고리즘

알고리즘은 어떤 일을 해결하기 위한 방법이다. 자세히 말하면 수학, 컴퓨터과학 등의 분야에서 어떠한 문제를 풀어내기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다. 즉, 문제풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 자료구조 내에서 기본적인 연산을 하기 위한 프로그램 명령어의 집합을 의미하기도 한다. 다시 책장을 예로 들면, 내가 책을 찾아야 하는데 왼쪽 부터 찾을 것인지, 오른쪽부터 찾을 것인지, 무작위로 찾을 것인지를 결정하는 것이 알고리즘이다.

알고리즘의 분류

간단히 분류를 해보자면

• 구현 : 재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘 등.
• 설계 : 무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한정법, 확률적 알고리즘, 리덕션, 백트래킹 등.
• 최적화 문제 : 선형 계획법, 동적 계획법, 탐욕 알고리즘, 휴리스틱 함수 등.
• 이론적 분야 : 검색 알고리즘, 정렬 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 암호학적 알고리즘, 기계 학습, 데이터 압축 등.

자료구조와 알고리즘의 차이

자료구조 : 데이터를 어떠한 형태로 저장하고 관리할 것인지에 대한 방법.
그래서 자료구조는 어떻게 효율적으로 자료를 저장할 것인가에 대한 고민이 필요하다.

알고리즘 : 저장된 데이터를 찾거나 변형하거나 수정할 때 필요한 방법.
그래서 알고리즘은 문제를 해결하기 위한 절차에 대한 고민이 필요하다.

프로그램의 정의

프로그램의 일반적 정의는 컴퓨터에서 실행될 때 특정 작업을 수행하는 일련의 명령어들의 모음이다. 그런데 프로그램을 자료구조와 알고리즘의 관점에서 보자면
프로그램 = 자료구조 + 알고리즘 이라고 할 수 있다.

ex) 최대값 탐색 프로그램 = 배열 + 순차탐색