[Data Structure] 자료구조 및 알고리즘 정의와 자료구조의 종류

---

자료구조와 알고리즘

 

자료구조는 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장에 관한 것이다. 예를 들어, 선입선출 방식이 필요한 데이터가 있다면 이러한 데이터를 효율적으로 관리하기 위해 큐(queue)라는 선입선출형 자료구조를 활용할 수 있다.

알고리즘은 문제를 해결하는 절차나 방법을 자세히 설명하는 과정이다. 자연어, 흐름도(flow chart), 슈도코드(pseudo-code), 프로그래밍 언어 등으로 표현할 수 있다. 효율적인 알고리즘을 설계하기 위해서는 시간 복잡도와 공간 복잡도 등을 고려해야 한다.

프로그램은 이러한 자료구조(혹은 자료)와 알고리즘이 결합된 결과물이다. 예를 들어 계산기 프로그램을 만든다고 가정하자. 계산기 프로그램을 개발하기 위해서는 우선 계산에 필요한 데이터 구조를 정의해야 한다. 연산자와 피연산자를 저장하고 처리하기 위해 후입선출 방식의 자료구조인 스택(stack)을 사용할 수 있다. 또한, 중위 표기법으로 입력된 수식을 후위 표기법으로 변환하는 알고리즘이 필요하다. 이를 통해 컴퓨터가 연산자 우선순위를 정확하게 판단하여 올바른 계산 결과를 도출할 수 있다. 마지막으로, 이렇게 설계한 자료구조와 알고리즘을 프로그래밍 언어로 구현하여 실제로 동작하는 프로그램을 완성한다. 이처럼 자료구조와 알고리즘은 프로그램 개발의 핵심 요소이며, 효율적이고 안정적인 소프트웨어를 만드는 데 필수적이다.

 

---

추상자료형 (ADT)

 

추상 자료형(abstract data type)은 데이터의 형태와 그 데이터에 대한 연산을 추상적(수학적)으로 정의한 것이다. 따라서 데이터와 연산이 무엇인지는 명확하게 정의되지만, 그것들을 컴퓨터에서 어떻게 구현할지는 정의하지 않는다. 이러한 '어떻게'에 관한 부분은 자료구조와 알고리즘의 영역으로 넘어간다.

추상자료형은 객체 지향 프로그래밍에서의 클래스 개념과 유사하다고 할 수 있다. 객체 지향 프로그래밍에서는 추상화(abstraction)와 정보 은닉(information hiding)을 통해 사용자에게 중요한 정보는 강조하고, 구현의 세부 사항은 숨긴다. 이러한 맥락에서 추상 자료형은 클래스와 비슷한 역할을 한다.

 

---

자료구조의 종류

 

• 선형 자료구조

데이터가 일대일로 연결되어 있는 자료구조를 선형 자료구조라고 한다. 배열, 연결 리스트, 스택, 큐, 덱 등이 이에 해당한다. 예를 들어 배열은 데이터가 연속적으로 나열된 형태로, 각 요소는 앞뒤로 하나씩의 데이터와 연결되어 있다. 스택, 큐, 덱 등도 마찬가지로 데이터가 순차적으로 연결되어 있어 선형 구조를 이룬다.

• 비선형 자료구조

데이터가 일대다 또는 다대다로 연결되어 있는 자료구조를 비선형 자료구조라고 한다. 트리, 그래프 등이 이에 포함된다. 트리를 예로 들면, 트리는 계층적인 구조로서 하나의 노드가 여러 개의 자식 노드와 연결될 수 있다. 특히 이진 트리에서는 각 노드가 최대 두 개의 자식 노드를 가진다. 그래프도 각 노드가 여러 개의 다른 노드와 복잡하게 연결되어 있어 비선형 구조를 형성한다.