샷건치며 배우는 자료구조 with C++, 1화

자료구조에 대해 알아봅시다.

읽어주세요

자료구조를 배우기 위해 위대한 항로(?)를 넘어 여기까지 오신 분들 환영합니다. 본 게시글은 자료구조를 공부하면서 복습 겸 정리하기 위해 작성하였습니다. 개인적으로 강좌 형식 및 장난을 섞어가며 작성하는 걸 좋아하기 때문에 진지한 게시글을 원하신다면 뒤로 가기를 눌러주세요.

C++ 언어를 기반으로 하고 있습니다. 다른 프로그래밍 언어를 사용 중이신 경우 개념(이론)을 배우는 데 큰 문제는 없지만, 실제 코드로 구현할 땐 생각보다 차이가 있을 수 있습니다.

업데이트

C 언어 구현 내용 제거
- 게시글의 내용이 너무 복잡해져 제거하였습니다.

게시글 개선을 위해 임시 숨김 처리

자료구조

자료구조^{Data Structure}는 데이터를 효울적으로 저장, 관리, 처리하는 방법을 의미합니다. 즉, 컴퓨터가 데이터를 더 빠르고! 더 효율적으로!! 처리할 수 있도록 설계된 구조를 말합니다.

선대의 컴퓨터 과학자들이 데이터를 효율적으로 사용하기 위해 ㅈ빠지는 연구를 통해 내려준 선물(?)입니다. 덕분에 우리는 딸깍 몇 번으로 개념을 적용해 데이터를 효율적으로 다룰 수 있죠.

자료구조가 왜 배워야하는 지 이해가 안 됩니다!

도서관에서 책을 찾는다고 가정해봅시다. 도서관에서 책을 무작위로 쌓아두면 원하는 책을 찾기 ㅈㄴ 어렵습니다. 일일이 하나씩 살펴보면서 책을 찾아야합니다. (탐색 과정)

도서관 측은 이러한 문제를 해결하기 위해 도서 번호를 이용한 배열 개념이나 제목 검색 방식을 도입했다고 해봅시다. 도서 번호를 통해 책이 있는 위치를 바로 찾아낼 수 있고, 제목 검색을 통해 유사한 책의 목록들을 나타내고 원하는 위치도 바로 찾을 수 있습니다. 도서 번호를 이용한 배열 개념과 제목 검색 방식이 바로 우리가 앞으로 배울 자료구조에 해당합니다. 참고로... 문제를 해결하기 위해 어떤 자료구조 개념을 사용할 지는 여러분의 판단입니다.

알고리즘과 헷갈리지 마세요!

자료구조를 배울 때 알고리즘과 헷갈리는 경우가 발생합니다. 생각보다 차이가 큰 개념인데 유사한 개념으로 퉁쳐서 외우는 경우가 있는 것 같습니다.

알고리즘^Algorithm(1)은 특정 문제를 해결하기 위한 절차(과정)를 의미합니다. 자료구조는 데이터를 효율적으로 저장하는 역할을, 알고리즘은 데이터를 효율적으로 처리하는 역할을 나타냅니다. 즉, 자료구조는 재료이고 알고리즘은 이를 활용하는 방법이라 생각하시면 되겠습니다. 아래의 예시를 보시면 이해가 가실겁니다.

Algorithm의 올바른 표기는 '알고리듬'이지만, 대부분의 경우 '알고리즘'으로 표기하고 발음하기 때문에 앞으로 '알고리즘'으로 작성합니다.

스파게티 요리

스파게티 요리로 비유해봅시다. 자료구조는 재료를 정리하고 저장하는 방법이고, 알고리즘은 이 스파게티를 만드는 과정이라고 볼 수 있습니다.

자료구조는 재료의 정리와 저장 역할을 합니다. 재료(토마토, 양파 등)를 각 칸에 정리하여 보관하고, 이를 고정된 위치에 보관합니다. 추후 배우게 될 배열 개념과 유사합니다.

알고리즘은 요리 과정입니다. 재료를 준비하고(초기화), 양파를 분할과 정복(Divide & Conquer)으로 썰고, 소스를 재귀(Recursion) 방식으로 계속 저어 완성합니다.

스파게티 요리를 예시로 들어서 좀 웃기긴 하지만 자료구조와 알고리즘 개념을 이해하는 데 큰 도움이 되리라 생각합니다. 재료를 찾기 어려운 곳에 둔다면(비효율적인 자료구조) 재료를 찾는 데 시간이 오래 걸리기 때문에 요리 시간이 길어집니다. 또한, 요리 순서가 잘못되면(비효율적인 알고리즘) 스파게티의 면이 툭툭 끊기거나 소스가 너무 묽어질 수도 있습니다. 효율적인 자료구조와 알고리즘을 사용하면 도내 최고 스파게티를 만들 수 있습니다.

추상 데이터 타입

추상 데이터 타입^{Abstract Data Type}은 자료구조의 개념을 정의하는 추상적인 모델입니다. 추상적이기 때문에 이 자료구조가 무엇을 할 수 있는 지만 정의하고, 이를 어떻게 구현할 지는 정의하지 않습니다. 사용자에겐 인터페이스를 공개(Public)하고, 내부 구현은 숨기는 추상화(Abstract) 개념입니다. 만화로 치면 콘티라 볼 수 있습니다.

ADT는 개념적인 사항이라 이렇게 저렇게 작성하라는 특정 표준이 없습니다. 즉, 작성하는 사람 마음이지만 아래의 사항을 준수하면 좋습니다. ADT는 프로그래밍 작업을 효율적으로 할 수 있도록 도와주는 개념이지 카오스를 야기하는 것이 아닙니다.

ADT의 목적 정의
1. 데이터의 구조
ADT가 제공하는 연산
1. 연산들이 어떻게 동작해야 하는 지 정의

ADT

ADT: stack
데이터:
    - 순서가 있는 요소들의 집합
    - 마지막에 들어온 것이 먼저 나가는 LIFO(후입선출) 원칙
연산:
    - push(item): 스택의 맨 위에 item 추가
    - pop(): 스택의 맨 위에 있는 item을 제거 후 반환
    - isEmpty(): 스택이 비어 있는 지 확인

추후 배우게 될 자료구조인데, 스택은 마지막에 들어온 요소가 가장 먼저 나가는 후입선출(Last In First Out) 원칙을 따르는 자료구조입니다. 위 ADT 연산에 스택의 가장 최근 아이템을 반환하는(제거 X) peek()을 추가할 수도 있습니다. 얼마나 정의할 지는 여러분 마음입니다.

ADT는 단지 추상화된 개념이고 실제 구현은 프로그래밍 언어마다 차이가 있습니다. C++ 언어에서는 이를 class로 구현하고 정의할 수 있습니다.