[자료구조/C] 자료구조와 알고리즘, 추상자료형(ADT, abstract data type)

프로그램 = 자료구조 + 알고리즘

자료구조(data structure)

프로그램에서 자료를 정리하여 보관하는 구조(배열, 스택, 큐...)

알고리즘(algorithm)

• 컴퓨터로 문제를 해결하기 위한 단계적인 절차
• 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 기술한 것
• 특정한 일을 수행하는 명령어들의 집합

알고리즘의 조건

• 입력 : 0개 이상의 입력이 존재해야 한다
• 출력 : 1개 이상의 출력이 존재해야 한다
• 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다
• 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다
• 유효성 : 각 명령어들은 실행 가능한(프로그래밍 언어로 바꿀수 있는) 연산이어야 한다.

자료형

: 데이터 + 데이터 간에 가능한 연산

출처 : C언어로 쉽게 풀어쓴 자료구조

추상 자료형(ADT, abstract data type)

• 자료형을 추상적, 수학적으로 정의한 것
• 즉, 사용자에게 중요한 정보는 강조되고(데이터나 연산이 무엇인지 정의) 구현 세부사항(데이터나 연산을 어떻게 컴퓨터 상에서 구현할 것인지)은 정의되지 않은 자료형 => 정보 은닉 (what O how X)
• 객체와 함수가 정의됨
• 데이터나 연산이 무엇인지만 명시하기 때문에 여러 가지 방법으로 구현될 수 있다.