[C로 만드는 자료구조]자료구조 포스팅을 시작하면서

자료구조 & 알고리즘

프로그램에서 데이터를 표현하는 것을 자료 구조라고 합니다. 일반적으로 프로그램을 자료구조 + 알고리즘 이라고 표현을 할 수 있죠.

일반적인 자료구조와 알고리즘을 모두 가지고 있는 프로그램을 예시를 들어보겠습니다.

위의 소스와 같이 한 프로그램은 자료구조와 알고리즘이 있다는 것을 확인 할 수 있고 데이터 표현을 자료구조(배열)을 통해서 하고 있으며  더하는 방식의 데이터처리(알고리즘)를 하고 있다는 것을 확인 할 수 있습니다.

그럼 자료구조에 대해서 알아보겠습니다.

자료구조

그렇다면 자료 구조의 정확한 의미는 무엇일까요? 그리고 왜 사용할까요? 자료구조는 데이터의 특성에 따라 분류, 구성, 저장하는 모든 작업을 의미합니다. 또 이렇게 분류, 구성을 함으로써 데이터를 효율적으로 사용할 수 있게 만들어 주는 것입니다. 마치 어질러징 방에서 뭔가를 찾는거 보다 미리 종류별로 분류를 한다음 찾는게 더 쉬운것과 같은 것입니다.

자료구조는 다음과 같이 분류가 됩니다.

각 자료구조 별 간단한 특징을 알아보겠습니다.

• 선형구조
  
  
• 리스트 : 순서가 정해진 목록
• 스텍 : 나중에 입력한 것을 먼저 출력하는 LIFO(Last In, First Out, 후입선출) 구조
• 큐 : 먼저 들어온 일 부터 순서대로 처리 FIFO(First In, First Out, 선입선출) 구조
  
  
• 비 선형구조
  
  
• 그래프 : 서로 다른 노선들 사이에 연결 관계가 설정, 최단 경로
• 트리 : 뿌리와 가지로 구성
  
  

위와 같이 나타낼 수 있습니다. 자료구조만 함으로 파일구조는 제외시키고 단순구조는 일반적으로 많이 쓰기 때문에 따로 포스팅은 하지 않겠습니다.

알고리즘

알고리즘이란 컴퓨터로 문제를 풀기위한 단계적인 절차를 의미합니다. 알고리즘이 되기 위해서는 몇가지 조건이 필요한데 알고리즘의 조건에 대해서 알아보겠습니다.

• 알고리즘의 조건
  
  
• 입력 : 0개 이상의 입력이 존재하여야함
• 출력 : 1개 이상의 출력이 존재하여야함
• 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 함
• 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 함
• 유효성 : 각 명령어들은 실행 가능한 연산이어야 함

알고리즘의 기술은 여러가지로 할 수 있지만 보통은 자연어, 흐름도, 유사코드, 프로그래밍등으로 기술할 수 있습니다.

추상 데이터 타입 (ADT : Abstract Data Type)

데이터 타입은 데이터 집합과 연산의 집합을 의미합니다. 예를 들면 데이터로는 3.14, 5, 4, -0.4 등이 있으며 연산 집합에는 + - / * 등이 있습니다. 그렇다면 ADT는  추상 데이터 타입을 의미하는데 이는 무엇을 의미할까요?

ADT란 새로운 데이터 타입을 추상적(수학적)으로 정의한 것을 의미합니다. 또 데이터나 연산이 무엇인가는 정의가 되지만 데이터나 연산을 어떻게 구현할 것인지는 정의되지 않습니다.

ADT의 정의

겍체 : ADT에 속하는 객체

연산 : 객체 사이의 연산

예를 들면 1~10 까지의 자연수들을 이용하여 계산을 하거나 비교하거나 하는데 이를 위한 함수들이 zero() is_zero(), add(x,y)등이 있다고 가졍하겠습니다. 이렇다면 이중에서 1~10까지의 자연수를 우리는 객체라고 읽고 zero(), is_zero(), add(x,y)등의 새로운 기능을 하는 함수(또는 데이터 타입)을 우리는 연산  또는 ADT라고 부릅니다.