Data structures and Algorithms

정보의 재현(representing)은 컴퓨터 과학의 기초이다. 흔히 컴퓨터의 목적은 빠른 계산에 있다고 생각하지만, 진정한 목적은 데이터의 저장과 정보의 검색에 있다. 그후에 "가능한 빠르게 처리"하는 목적이 부차적으로 따라온다. 컴퓨터가 아무리 빠르게 계산을 한다고 해도, 데이터의 저정과 검색이 효율적이지 못하다면 원하는 시간에 결과물을 얻을 수 없다. "데이터의 저정과 정보를 효율적으로 조작해서 빠른 시간에 원하는 결과물을 얻는 것". 우리가 데이터 스트럭처와 알고리즘을 공부하려는 이유다. 이 문서는 데이터를 효과적으로 처리하기 위한 데이터 스트럭처와 처리방식에 해당하는 알고리즘을 다룬다.

이 문서는 3개의 주요 목적이 있다.

1. 일반적으로 사용하는 데이터 스트럭처의 재현 : 이들 스트럭처에 대한 이해는 개발자에게 하나의 "툴킷"이 된다. 개발자는 다양한 종류의 문제들을 푸는데, 이 툴킷을 사용할 수 있다.
2. 각 데이터 구조를 다루는데 들어가는 비용과 이익의 트레이드오프(tradeoff)에 대한 개념을 익힌다. 각 데이터 구조를 설명하면서, 이들 구조가 어떤 일을 처리하기위 해서 차지하는 공간과 처리 시간을 검사 할 것이다.
3. 데이터 구조와 알고리즘의 효율성을 측정하는 방법을 살펴본다. 이러한 측정을 통해서 당면한 문제를 풀기 위한 적합한 데이터 구조와 알고리즘을 선택할 수 있다. 또한 새로운 데이터 구조에 대한 장점과 단점을 파악 할 수 있으며, 장점을 강화하고 단점을 보완한 새로운 데이터 구조와 알고리즘을 개발 할 수 있다.

문제를 해결 하는데에는 한 가지 이상의 방법이 있기 마련이다. 이들 방법 중에 어떤 것을 선택해야 할까. ? 이를 위한 컴퓨터 프로그램 개발의 핵심 개발 원칙은 아래와 같다.

1. 알고리즘는 쉽게 이해하고 코드로 만들 수 있으며 디버깅이 쉽도록 디자인 해야 한다.
2. 알고리즘은 컴퓨터의 자원을 효율적으로 사용 할 수 있도록 디자인 해야 한다.

이상적인 프로그램은 이 두가지 목표를 모두 달성해야만 한다. 이런 프로그램을 우리는 우아하다고(elegant) 부른다. 이런 점에서 본다면, 이 책에서 소개하고 있는 예제들은 별로 우아하지 않을 것이다. 왜냐하면 이 책의 목적은 1번 목표에 그다지 신경을 쓰지 않기 때문이다. 1번은 소프트웨어 엔지니어링과 관련된다. 이 책은 주로 2번의 원칙에 집중 할 것이다.

어떻게 소프트웨어가 효율적으로 작동하는지를 측정 할 수 있을까 ? 3장에서 우리는 점근적 분석(asymptotic analysis)을 이용해서 알고리즘과 컴퓨터 프로그램의 효율을 측정하는 방법을 살펴볼 것이다. 데이터 입력의 크기가 작으면 알고리즘의 효율과 관련 없이 빠르게 끝날 것이다. 이래서는 알고리즘의 효율을 측정할 수 없다. 점근적 분석은 입력의 크기를 충분히 크게 하는 방법으로 알고리즘의 효율을 분석 할 수 있다. 나머지 장들에서는 점근적 분석을 이용해서 알고리즘들에 대한 효율을 대략적으로 측정 할 것이다. 이러한 측정은 다른 알고리즘들을 서로 비교 할 수 있게 해주며, 같은 문제를 풀 때 어떤 알고리즘을 선택해야 할지를 알게 해준다.

컴퓨터는 해마다 빨라지고 있다. 프로그램의 효율성은 중요도가 점점 떨어지고 있다. 이런 생각을 할 수도 있겠다. 프로세서는 계속 빨라지고 있으며, 메모리는 점점 커지고 가격까지 내려가고 있다.

우리는 더욱 강력한 컴퓨터로 개발을 하고 있다. 하지만 컴퓨터가 강력해 질 수록 더욱 복잡한 문제가 우리의 발목을 잡고 있다. 데이터의 쌓이는 양은 컴퓨터 발전의 속도를 뛰어넘고 있다. 사용자들은 더 정교하고 아름다운 인터페이스를 요구하고 있으며 현실과 구분되지 않는 가상의 정보를 요구하고 있다.

문제가 복잡해지면서 더욱 강력한 컴퓨터가 필요한 상황인데, 컴퓨터는 충분히 강력하지 않다. 언젠가는 컴퓨터가 충분히 강력해 질 수 있겠지만 그게 언제가 될지는 모른다. 결국 프로그램을 더 효율적으로 만드는게 필요하다.

설상가상으로 복잡해지는 업무들은 우리가 일상생활에서 경험할 수 있는 그런 것들이 아니다. 오늘날의 컴퓨터 과학자들은 일반적인 생각으로는 이해하기 힘든 상황들을 이해해서 프로그램 디자인에 반영을 해야 한다. 따라서 프로그램 디자인의 원리를 이해할 수 있도록 철저한 훈련을 받아야만 한다.

일반적으로 데이터 스트럭처는 데이터와 데이터를 처리하기 위한 오퍼레이션의 모음으로 설명할 수 있다. 심지어 integer이나 floating point number 형태로 저장된 데이터도 (간단한)데이터 스트럭처로 볼 수 있다. 더 일반적으로 사람들은 어떤 목적으로 가지고 특정한 형태로 모인 데이터 아이템의 집합으로 데이터 스트럭처를 이해하기도 한다. 예를들어 integer 값으로 구성된 sort list가 이런 정류의 데이터 스트럭처라고 볼 수 있다.

이들 데이터 아이템은 적절한 크기의 공간에 자장을 해야 하며, 필요 할 때 찾아서 출력 하고 값을 수정하고 연산을 수행해야 한다. 적절한 데이터 스트럭처를 만들었느냐에 따라서 프로그램의 수행 속도가 결정되는데, 그 차이는 몇초에서 몇시간이 될 수도 있다.

문제를 풀 때 사용할 수 있는 자원은 무한이 아니기 때문에, 효율적인 방법을 찾기 위해서는 자원의 제약(resource constraints)을 고려해야만 한다. 대표적인 자원제약은 데이터를 저장하기 위해서 사용할 수 이는 공간의 크기와 문제를 수행하는데 허용 할 수 있는 시간이다. 당연하지만 기존에 알려진 솔류션 보다 더 적은 자원을 사용 하면 더 좋은 솔류션이 될 수 있다.

1. 문제를 해결하기 위해서 데이터에 가해지는 기본적인 연산을 분석한다. 예를 들어 데이터 스트럭처에 아이템이 추가 될 수 있는지 혹은 삭제되는지, 데이터를 찾아야 하는지 등등을 확인해야 한다.
2. 각 연산을 위한 자원 제약을 정의한다.
3. 1과 2의 요구사항을 만족하는 데이터 스트럭처를 선택한다.

위 세개의 단계를 거쳐서 적절한 데이터 스트럭처를 선택하는게 소프트웨어 디자인의 핵심적인 부분이다. 첫번째 관심사는 데이터와 연산의 수행이고 다음 관심사는 데이터가 어떻게 재현되는지이다. 마지막으로 최종 구현이다.

자원의 제약은 애플리케이션이 데이터에 대해서 어떤 작업을 하는지에 따라서 결정이 된다. 데이터에 대한 입력, 삭제, 검색등의 작업이 필요한지, 작업이 필요하다면 어느 시점에서 작업이 일어나는지 등이다. 데이터 스트럭처를 결정 할 때는 작업에 대한 아래의 세가지 사항을 검토해야 한다.

• 모든 데이터 아이템들이 프로그램이 시작 할 때 입력 되는지. 아니면 프로그램 실행 중에 insert 될 수 있는지. 초기에 데이터를 읽고 여기에 대한 수정이 없는 애플리케이션이라면 단순한 데이터 스트럭처를 사용한다. 반면 동적으로 데이터가 수정되는 애플리케이션이라면 복잡한 데이터 스트럭처를 사용해야 한다.
• 데이터가 삭제될 수 있는가 ? 만약 그렇다면 더 복잡해 질거다.
• 데이터가 순서를 가지고 있거나 혹은 검색과 같은 작업을 수행해야 하는가 ? 검색과 같은 랜덤엑세스 작업이 필요하다면 가장 복잡한 데이터 스트럭처를 사용하게 될 거다.

각 데이터 스트럭처는 비용과 이점을 가지고 있다. 다시 말해서 장점과 단점을 가지고 있다는 이야기다. 모든 경우에 대해서 가장 효율적인 데이터 스트럭처는 없다. 만약 모든 면에서 우수한 알고리즘이 있다면, 알고리즘은 열등한 알고리즘과 우수한 알고리즘으로 양분될 것이고 열등한 알고리즘을 사용할 일은 아예 없을 것이다. 이 문서에서는 다양한 데이터 스트럭처와 알고리즘을 제시하고, 각 예제에 대해서 어떤게 최선인지를 선택하게 될 거다. 때때로 어떤 예제들은 의외의 결과를 보여주기도 할 건데, "단순하고 별로 효율적이지 않아 보이는 데이터 스트럭처가 어떤 경우에는 매우 효율적으로 작동"하는 걸 볼 수 있기 때문이다.

데이터 스트럭처는 데이터를 저장하기 위한 공간과 작업을 수행하기 위한 시간을 필요로 하며, 여기에 더하여 프로그래밍을 위한 노력을 필요로 한다. 각 문제는 사용 가능한 공간과 시간에 제약을 가지고 있다.

문제의 해법은 문제의 특성을 주의 깊게 확인 한 후, 데이터와 데이터를 향한 기본적인 연산들이 공간과 시간에 어떤 영향을 미치는지를 분석해서 적절한 데이터 스트럭처를 탐색해나가면서 찾을 수 있다.

2 티어로 구성된 은행 서비스를 예로 들어보자. ATM(Automated teller machines) 혹은 은행직원은 고객의 대여, 인출, 입금 요청을 받은 다음, 고객 계좌에 접근해서 계좌정보를 업데이트한다. 또한 제한되는 시간동안 제공되는 특수한 서비스를 처리하기도 한다. 직원이나 ATM은 작업을 처리하기 위해서 약간의 시간을 소비한다. 계좌의 개설이나 폐쇄와 같은 작업에는 (고객의 관점에서)30분 넘는 시간이 걸리기도 한다.

데이터베이스 관점에서 보자면 ATM 트랜잭션은 데이터베이스를 수정하지 않는 다는 것을 알 수 있다. 단지 Add와 Remove만 있을 뿐이다. 수정이 없으므로 단지 계좌레코드에 추가/삭제 내역만 기록하는 것으로 작업을 처리 할 수 있다. 계정을 추가하는 경우에는 데이터베이스에 작업이 필요하므로 어느 정도 시간이 필요할 것이다. 반면 계좌 폐쇄의 경우에는 시간이 걸리지 않을 것이다. 현재 남아 있는 돈을 꺼내고, 폐쇄 됐다는 표시만 하면 되기 때문이다. 은행 관점에서는 업무시간 이후에 혹은 월별 계정 관리 시간에 폐쇄 표시된 계정을 정리해주면 된다.

이제 은행을 위한 데이터 스트럭처를 선택해 보자. 고객 계좌 관리 시스템의 경우, 삭제에는 거의 비용이 들지 않으며 별로 신경 쓸 필요가 없다. 하지만 검색에는 많은 자원이 필요하다. 따라서 검색에 효율적으로 작동하는 데이터베이스 스트럭처를 선택해야 한다.

계좌의 기록은 고객의 계좌에 유일하게 부여되는 계좌번호로 접근 할 수 있다. 이러한 요구사항에 적합한 데이터 스트럭처로 9장에서 살펴볼 해시(hash)가 적당하다. 해시테이블은 exact match 검색에 관한한 극강의 효율을 보여준다. 또한 삽입도 효과적으로 지원한다. 삭제도 효과적으로 수행 할 수 있는데, 다만 너무 많은 삭제가 일어날 경우 약간의 성능 저하가 발생 할 수 있다. 이런 문제는 주기적으로 해시테이블을 재 구성하는 것으로 해결 할 수 있다. ATM 거래에 영향을 미치지 않아야 하므로 재구성 작업은 업무시간 이후에 수행 할 수도 있다.

앞 절에서 "data item"과 "데이터 스트럭처"를 다루긴 했지만 이들에 대한 정의는 하지 않았다. 이번 절에서는 용어에 대한 정의를 하고 데이터 구조를 선택하기 위한 3단계 방법에 대해서 살펴보겠다. 이러한 단계를 구축하는 이유는 컴퓨터 프로그램의 막대한 복잡성을 단순화 하기 위함이다.

타입(Type)은 값(value)의 모음이다. 예를들어 불리언(Boolean)타입은 true 혹은 false 값 중 하나로 구성된다. Integer 역시 타입이다. Integer는 값에 다른 서브파트를 포함하지 않는 단순한 타입이다. 반면 은행의 계좌 레코드에는 이름, 주소, 계좌번호와 같은 여러개의 정보 조각으로 구성이 된다. 이런 종류의 타입을 aggregate 타입 혹은 composite 타입이라고 부른다. Data item은 타입으로 부터 꺼낸 정보의 조각 혹은 레코드다. 데이터 아이템은 타입의 멤버라고 부르기도 한다.

Data type은 타입과 타입을 조작하기 위한 동작들의 모음이다. 예를들어 interger 변수는 integer 데이터타입의 멤버이고, 덧셈은 integer 데이터 타입에 대한 동작이다.

컴퓨터 프로그램은 데이터 타입의 논리적인 개념을 실제 작동하도록 구현을 하는데, 개념과 구현사이에는 차이가 존재한다. 예를 들어 리스트 데이터 타입은 하나의 개념이지만 프로그램상에서는 링크드 리스트와 배열기반 리스트등 다양한 구현이 있을 수 있다. 이렇게 리스트 데이터 타입은 링크드 리스트 혹은 배열로 구현할 수 있는데, 배열 조차도 여러가지 구현이 있을 수 있다. 컴퓨터 프로그래밍에서 배열은 메모리의 연속된 블럭을 의미한다. 각 블럭에는 고정된 길이의 값이 존재한다. 이렇게 보면, 배열은 그 자체가 물리적인 데이터 스터럭처의 구현이라고 볼 수도 있다. 하지만 배열은 색인(index)로 참조할 수 있는 논리적인 데이터 타입(일반적으로 균질한)들의 모음이라고 볼 수도 있는데, 이는 배열도 다른 여러가지 방법으로 구현할 수 있음을 의미한다.

Abstract data type(ADT)는 소프트웨어 컴포넌트에서 사용하는 데이터 타입의 실현체다. ADT의 인터페이스는 타입과 타입에 대한 조작으로 구성이 된다. 각 조작(operation)이 하는 일은 입력과 출력에 의해서 결정이 된다. ADT의 데이터 타입에 대한 세부 구현 사항은 ADT를 사용하는 유저로 부터 숨겨져서 외부로부터의 접근으로 부터 보호한다. 이 개념을 encapsulation(캡슐화)라고 한다.

데이터 스트럭쳐는 ADT에 의해서 구현이 된다. Java와 같은 객체지향 언어는 class의 형식으로 구현을 한다. Class가 없는 Go언어는 struct를 이용해서 구현을 하는데, 개념상 java와 별 차이가 없다. Go언어에서 ADT의 각 조작은 메서드로 구현을 한다.