주교재
『C++로 쉽게 풀어쓴 자료구조』, 천인국ㆍ최영규 지음, 생능 출판사
공부 범위 : 챕터 1 자료구조와 알고리즘
1.1 자료구조
자료구조
데이터를 효율적으로 사용하기 위해 정리하고 조직화하는 구조. 크게 두 가지로 나눌 수 있다. 정수, 실수, 문자와 같이 보통 프로그래밍 언어에서 기본적으로 제공하는 단순 자료구조와 여러 자료구조가 복합적으로 구성된 복합 자료구조가 있다. 이중에서 복합 자료구조는 다시 선형 구조와 비선형 구조로 나눌 수 있다.
선형 자료구조
자료들이 순서대로 나열되는 구조로 배열과 연결리스트, 큐, 덱 등이 있다. 데이터에 접근하는 방식은 순서 접근과 직접 접근 두 가지가 있다. 순서 접근 방법은 일정한 시작점을 기준으로 특정 방향으로 이동하여 원하는 자료를 찾고, 직접 접근 방법은 인덱스를 이용해 어떤 요소든 한번에 접근할 수 있다. 일부 선형 자료구조는 접근이 가능한 항목이 맨앞 또는 맨뒤로 제한된다.
비선형 자료구조
자료들이 선형 순서보다 복잡한 연결을 갖는다. 트리와 그래프가 이에 속한다. 두 자료구조 모두 나무의 뿌리에서 특정 가지를 찾아가는 경로를 생각하면 이해하기 쉽다. 단순한 직선이 아니라 갈림길이 존재한다는 점에서 탐색의 시간을 줄이거나 경로를 탐색하는 데에 이용되기도 한다.
1.2 알고리즘
프로그램과 알고리즘
사전적으로 “어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합”을 의미한다[1]. 사용하는 프로그래밍 언어와 무관하게 문제를 해결하는 절차 그 자체를 정의한다.
알고리즘이 알고리즘으로 사용되기 위해서는 다음의 5가지 조건이 필요하다.
(1) 입력 : 0개 이상의 입력이 존재해야 한다.
(2) 출력 : 1개 이상의 출력이 존재해야 한다.
(3) 명백성 : 각 명령어의 의미가 명확해야 한다.
(4) 유한성 : 한정된 수의 단계 후에 반드시 종료되어야 한다.
(5) 유효성 : 각 명령어는 실행 가능한 연산이어야 한다.
프로그램은 자료구조와 알고리즘의 조합으로 이루어진다. 책에서는 프로그램에 사용할 자료구조를 정하면 알고리즘이 정해진다고 설명했다.
알고리즘 기술 방법
알고리즘을 표현하는 방법은 4가지이다.
(1) 자연어
인간이 쓰는 말로 알고리즘을 서술한다. 쓰기는 편하지만 모호하지 않게 서술하도록 신경써야 한다.
(2) 흐름도
책의 설명에 따르면 명확하게 표현할 수 있지만 알고리즘이 복잡해지면 흐름도도 복잡해지는 단점이 있다고 한다.
(3) 유사 코드(pseudo-code)
자연어와 프로그래밍 언어의 중간 쯤 되는 서술 방식이다. 알고리즘의 표현에 흔히 사용한다고 한다. 특정 언어의 문법에 구애받지 않으면서도 프로그래밍 언어와 비슷하고, 실제 프로그래밍 언어로 서술할 때의 여러 가지 문제점을 가릴 수 있다. 문제점을 가린다고 해서 나쁜 건 아니고, 자잘한 프로그래밍 언어의 문법에 신경쓰지 않고 알고리즘만의 흐름에 집중할 수 있게 해준다. 대입 연산자와 등호의 의미가 실제 프로그래밍 언어가 다소 다르다는 점에 주의해야 한다.
(4) 특정 프로그래밍 언어
책의 설명으로는 알고리즘을 가장 정확히 표현할 수 있는 방법이라고 한다. 세 번째 방법과 달리 자잘한 문법에도 신경써야 하기 때문에 알고리즘 이해에는 방해가 될 수 있다.
1.3 추상 자료형
추상화
복잡한 자료, 모듈, 시스템 등을 간략화하고 핵심적인 개념이나 기능을 간추려 낸다. 간단히 말해 복잡한 것을 단순하게 보이게 만드는 것을 말한다.
추상 자료형
자료형을 추상화한 것이다. 자료나 그 연산이 무엇인지는 정의하지만 그것을 어떻게 구현할지는 정의하지 않는다. 추상 자료형을 정의할 때는 데이터를 먼저 정의하고 나서 연산을 정의한다. 연산에는 연산의 이름, 매개변수, 수행하는 기능 등을 서술한다.
추상 자료형을 프로그램으로 구현할 때는 사용자에게 인터페이스만을 공개한다. 이렇게 하면 나중에 프로그램의 내부적 구조나 구현 등이 바뀌어도 사용자는 변함없이 프로그램을 사용할 수 있다. 이런 식으로 내부 구현과 사용자를 분리하는 것이 추상화의 요점이다.
1.4 알고리즘의 성능 분석
효율적인 알고리즘은 실행 시간이 짧고 메모리를 적게 사용하는 알고리즘이다. 보통은 메모리보다 실행 시간을 우선한다.
실행 시간 측정 방법
알고리즘의 실행 시간을 알기 위해 알고리즘을 실제 프로그램으로 작성하여 직접 실행 시간을 측정하는 방법이 있다. 주로 clock() 함수를 이용한다고 한다. 측정은 편하지만 이 방법에는 문제가 좀 있다. (1) 알고리즘을 실제로 구현해야 하고, (2) 비교 대상이 되는 알고리즘을 모두 같은 컴퓨터에서 실행해야 하고, (3) 사용한 소프트웨어도 동일해야 하고(보통 컴파일 방식 언어가 인터프리터 방식 언어보다 실행 속도가 빠르다), (4) 실험해보지 않은 입력 데이터에 대해서는 동일한 실행 시간을 주장할 수 없다.
문제가 생각보다 많지만 다행히도 하드웨어 기기를 사용하지 않고도 알고리즘의 실행 시간을 계산할 수 있는 다른 방법이 있다.
알고리즘의 복잡도 분석 방법
이 부분에 대해서는 다음 글을 참고하자.
[자료구조] Big-O와 이진 탐색 트리 https://dapin1490.github.io/satinbower/posts/it-bin-search-tree/
1.5 자료구조 표기법
ADT - Class Diagram - C++ 구현
이 책에서는 자료구조를 세 단계에 걸쳐 표현한다. 추상 자료형 ADT로 개념을 정의하고, UML 클래스 다이어그램으로 구조를 설계하고, C++ 클래스로 해당 자료구조를 구현한다. 이 책은 STL 라이브러리를 사용하기보다는 직접 클래스를 구성하고 각 자료구조를 구현하는 것에 더 중점을 두어 설명하고 있지만 나는 가능한 한 STL 라이브러리를 이용해 공부할 생각이다. 그러니 교재의 코드는 STL 라이브러리로 대체하지 못한 경우에 주로 쓰게 될 것이다.
UML Diagram
UML : Unified Modeling Language, 통합 모델링 언어의 약자
책에서는 소프트웨어 개발에서 시스템의 구조와 상호작용, 컴포넌트 관계, 업무 흐름 등을 표현하는 통합된 객체지향개발 표준통합 모델링 언어라고 정의하고 있다. 너무 복잡하니 어떤 모델을 서술하는 일관된 표현 방식이라고 생각하자. 여기서는 클래스를 나타내는 데 사용한다. 기호와 화살표 등이 다 의미가 있긴 한데, 이에 대해서는 각자 책을 직접 보자.
참고 자료
[1] 네이버 국어사전 - 알고리즘 https://ko.dict.naver.com/#/entry/koko/b925552564c544f4bb5b3db6970b2e29