자료구조(1) - 자료구조, 알고리즘, 추상 데이터 타입(ADT)

프로그래밍을 공부를 하게 되면 무조건적으로 거쳐가는 과정이 자료구조이다.

그럼 왜? 배울까????????

그 이유는 자료구조가 단순한 “저장 방식”이 아니라, 문제를 얼마나 효율적으로 해결할 수 있는지를 결정하는 핵심 도구이기 때문입니다.

자료구조를 배우는 자세한 이유는 

• 성능 최적화: 시간과 메모리를 절약할 수 있음
• 알고리즘의 토대: 모든 알고리즘은 자료구조 위에서 동작함
• 문제 해결 능력 향상: 다양한 상황에 맞는 최적의 해결책을 선택할 수 있음

즉, 자료구조는 앞으로 하는 모든 것의 뼈대라고 볼 수 있다.

---

● 자료구조(Data Structure)란?

   일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체이다

    잉??? 딱 저 문장을 보면 무슨 소리지 라는 생각이 들고 쉽게 이해하긴 어려울 것이다.

 

이를 일상생활과 빗대어 설명을 하자면

식당이나 가정에서 그릇들을 쌓아서 보관하는 방법(스택(Stack)), 버스 정류장에서의 줄이나 마트 계산대의 줄을 보면 선 순서대로 먼저 온 사람이 먼저 탑승하는 방법(큐(Queue)), 여러 지점(정점, Vertex)과 도로(간선, Edge)를 표시하는 지도 (그래프(Graph)), 가족 족보나 회사 조직도(트리(Tree)) 등의 예시를 보면

 

즉, 자료구조는 "데이터를 어떻게 정리하고 꺼낼지에 대한 정리법" 이다.

 

※ 자료구조의 종류

• 스택(Stack)
• 큐(Queue)
• 연결 리스트(Linked List)
• 트리(Tree)
• 해시 테이블(Hash Table)

등 여러 구조가 있다.

---

● 알고리즘(Algorithm)이란?

   문제를 해결하기 위한 명확한 절차나 방법, 규칙적인 단계의 집합

 

이 또한 일상적인 비유를 해서 설명하자면

라면 끓이기 레시피 → "물을 끓인다 - 스프 넣는다 - 면 넣고 3분 끓인다",

길 찾기 → 집에서 학교 갈 때(늘 가는 방법처럼 or 문방구 갔다가 도서관 갔다가 가는 방법),

책상 정리  →  큰 물건 먼저 정리하고 작은 물건 정리 or 책 정리하고 필기구 정리 등,

책 찾기 → 도서관에서 책 찾을 때(처음부터 한 권씩 or 도서관이 가나다순으로 정리되어 있다면 중간부터 반씩 줄여가며 찾기) 등

 

즉, 알고리즘은 "문제를 어떻게 해결할 것인지 구체적인 방법과 절차"다

 

※ 알고리즘 조건(좋은 알고리즘)

• 입력 - 0개 이상의 입력 존재
• 출력 - 1개 이상의 출력 존재
• 명백성 - 명령어의 의미는 모호하지 않고 명확
• 유한성 - 반드시 종료
• 유효성 - 명령어들은 실행 가능한 연산

※ 알고리즘 기술 방법

1. 자연어(한글, 영어와 같은) - 약간의 모호성의 존재하여 명령어로 사용되는 단어들을 명백하게 정의
2. 흐름도(flowchart) - 도형을 사용하여 알고리즘 기술, 복잡해질수록 기술하기 어려움
3. 의사 코드(pseudo-code) - 자연어보다 더 체계적이고 프로그래밍 언어보다는 덜함
4. 프로그래밍 언어 - 제일 안성맞춤

▶ 자료구조와 알고리즘 관계

• 자료구조(Data Structure): 데이터를 어떻게 담아둘까? (도구/그릇)
• 알고리즘(Algorithm): 데이터를 어떻게 다룰까? (요리법)

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

---

● 추상 데이터 타입(Abstract Data Type; ADT)이란?

   데이터와 그 데이터에 대한 추상적인 연산들로 구성된 타입, 데이터나 연산이 무엇(what)인지는 정의되지만 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의 X

 

 

▶ 자료구조와 추상 데이터 타입의 관계

     자료구조는 추상 데이터 타입을 구체적(프로그래밍 언어)으로 구현한 것

  예시) 건축에 빗대어 설명

• 추상 데이터 타입(ADT) = 건축 설계도
• 자료구조(Data Structure) = 설계도 따라 건축한 실제 건물