최근, 이직을 결정하게 됐다. 22년 8월부터 약 1년 6개월간 Computer Vision에 관련된 Task들을 해결하는 Data Scientist로써 근무를 해왔지만, 주된 관심사가 NLP와 추천 시스템이다보니 이직이라는 큰 결심을 하게 되었다. 나의 지식들을 점검하고 빈 공백을 채우기 위해 자료구조부터 다시 학습을 시작하려 한다. 게시물은 다음의 책을 참고하여 공부하며 작성됐다. 정리를 위한 자료는 직접 만들었다(사용 Tool : Excalidarw).
제목 : 자료구조와 알고리즘 with 파이썬
지은이 : 최영규
출판사 : 생능북스
1. 스택(Stack)이란?
스택(Stack)은 기본적으로 후입선출(LIFO - Last In, First Out)의 원리를 가지고 있는 자료구조다. 자료의 입출력이 단방향으로 이루어진다. 스택의 자료의 입출력이 이루어지는 부분을 스택의 "상단(Top)"이라고 부른다.
스택에 저장된 자료들은 "요소"라고 부른다. 가장 먼저 들어온 요소는 가장 나중에 나오기 때문에 가장 하단에 위치한다.
스택은 활용 예시는 다음과 같다.
- 웹 브라우저의 "이전 페이지로 이동"
- 한글, 파워포인트 등의 "되돌리기(Undo)"
여기서 스택이 어떻게 활용되는 지 궁금할 수 있다. 웹 브라우저에서 "이전 페이지로 이동" 기능의 동작 예시를 보면서 이해해보자.
먼저, 'Main' 페이지에서 다른 페이지로 이동할 때, 'Main' 페이지의 URL이 스택에 저장된다.
이제 '이전 페이지로 이동' 버튼을 클릭하면, 스택에 저장된 'Main' 페이지의 URL이 반환되면서 'Main' 페이지로 이동한다. 이 때, 스택에 저장되어 있던 'Main' 페이지의 URL은 반환과 동시에 삭제된다.
※ 짚고 넘어가기 ※
기본 자료형(Primitive Data Type) vs 참조 자료형(Reference Data Type) vs 추상자료형(Abstract Data Type)
본격적으로 스택을 구현해보기에 앞서서 자료형에 대한 개념을 짚고 넘어가보자.
보통 프로그래밍을 배울 때, 모든 변수나 상숫값에 대해 정해진 자료형(Data Type)이 있으며, 대부분의 프로그래밍 언어에서 별다른 처리없이 사용할 수 있는 기본 자료형(Primitive Data Type)을 제공한다고 배운다.
e.g. Python's Primitive Data Type > int→정수, float→실수, str→문자열 ... etc
하지만, 기본 자료형만으로는 문제 해결을 위한 프로그램에 있어서 한계가 있다. 앞서 예시로 들었던 "이전 페이지로 이동"기능을 구현한다고 할 때, 스택을 기본 자료형으로 제공한다면 훨씬 수월하게 기능 구현이 가능할 것이다. 대신, 대부분의 프로그래밍 언어는 이러한 경우를 대비하기 위해 사용자가 새로운 자료형을 정의해 사용할 수 있도록 지원한다.
이 때, 새로운 자료형을 정의하가 위해 자료형에 대한 내용을 중요하고 필수적인 특징들만 골라서 단순화 하는 작업이 필요하다. 이 작업을 "추상화(Abstraction)"라고 한다. 이런 추상화를 거쳐 정의한 자료형을 "추상 자료형(ADT - Abstraction Data Type)"이라고 한다.
ADT는 데이터의 모델을 정의하기 위해 사용되며, 해당 데이터 모델의 구현 방법에 대해서는 관심을 두지 않는다. ADT는 데이터의 타입(어떤 자료들을 자룰 수 있는지)과 그 타입에 적용할 수 있는 연산을 정의한다.
e.g. 추상 자료형의 예시
- 자바에서의 예시 : 추상 클래스, 인터페이스 등
> 'ArrayList', 'HashSet', 'HashMap' 을 통해 구현되는 인터페이스 'List', 'Set', 'Map'
- 파이썬에서의 예시 : 사용자 정의 추상 클래스, 기본 추상 클래스(ABCs) 등
> 'List', 'Tuple', 'Dictionary' 등을 통해 구현되는 'Iterable', 'Sequence', 'Mapping' 클래스 등(3가지 모두 'collections' 모듈을 통해 제공
예시를 보고 더 헷갈릴 수 있다. 하지만 예시를 보기보다 단순하게 "ADT는 데이터의 타입과 그 타입에 적용할 수 있는 연산이 정의된 클래스"라고만 이해해도 괜찮다. 잠시 후에 스택을 클래스로 구현해본다면 '아! 이게 추상 자료형이구나!'할 수 있기 때문이다.
그렇다면 참조 자료형(Reference Data Type)은 무엇일까? 사실, Python에서는 명시적인 참조 자료형 구분이 없기 때문에(굳이 따진다면 List, Dictionary, Class Instace 등이 참조 자료형에 속한다.) 굳이 알 필요는 없다. 가볍게 읽고 넘어가고, 이해가 되지 않는다면 무시해도 괜찮다.
참조 자료형(Reference Data Type)은 객체의 메모리 주소를 참조하는데 사용되는 데이터 타입이다. 이는 기본 자료형(Primitive Data Type)과 대비되며, 객체(Object)나 인스턴스(Instance)를 가리키는 용도로 사용된다.
e.g. 참조 자료형의 예시
- 자바에서의 예시 : 클래스, 인터페이스, 배열 등
> 'String', 'Array', 사용자 정의 클래스 등의 객체들은 모두 참조 자료형을 사용하여 메모리의 객체를 참조
이제 요약해보자.
참조 자료형은 메모리 상의 객체를 가리키는데 사용되는 반면, 추상 자료형은 데이터의 타입과 해당 데이터에 적용할 수 있는 연산의 추상적인 정의를 제공한다. 자바와 파이썬 모두 이 두 가지 개념을 사용하긴 하지만, 구체적인 사용 방법과 명칭에 있어서 차이가 있다. 타입 시스템적 측면에서 참조 자료형과 기본 자료형의 구분이 명확한 자바와 달리, 파이썬에서는 모든 것이 객체이기 때문에 더 동적으로 다루어져 참조 자료형을 명시적으로 제공하지는 않는다. 추상 자료형은 두 언어 모두에서 중요한 역할을 하며, 프로그래머가 데이터 구조를 더 추상적으로 다룰 수 있게 하는 도구다.