1.2 알고리즘이란 무엇인가¶
1.2.1 알고리즘의 정의¶
알고리즘(algorithm)은 유한한 시간 안에 특정 문제를 해결하는 명령 또는 작업 단계의 집합이며, 다음과 같은 특성을 갖는다.
- 문제가 명확하고 입력과 출력이 분명하게 정의되어 있다.
- 실행 가능하며, 유한한 단계와 시간, 메모리 공간 안에서 완료할 수 있다.
- 각 단계의 의미가 명확하여 입력과 실행 조건이 같으면 항상 같은 출력을 얻는다.
1.2.2 자료 구조의 정의¶
자료 구조(data structure)는 데이터를 구성하고 저장하는 방식으로, 데이터의 내용, 데이터 사이의 관계, 데이터를 조작하는 방법을 포함한다. 자료 구조는 다음과 같은 목표를 고려하여 설계한다.
- 컴퓨터 메모리를 절약하도록 공간 사용량을 최대한 줄인다.
- 데이터 접근, 추가, 삭제, 갱신 등의 연산을 최대한 빠르게 수행한다.
- 알고리즘이 효율적으로 실행되도록 간결한 데이터 표현과 논리적 정보를 제공한다.
자료 구조를 설계하는 과정에는 수많은 절충이 따른다. 어느 한 측면을 개선하려면 다른 측면을 양보해야 할 때가 많다. 두 가지 예를 살펴보자.
- 연결 리스트는 배열보다 데이터를 추가하거나 삭제하기가 편리하지만, 데이터에 접근하는 속도는 느리다.
- 그래프는 연결 리스트보다 더 풍부한 논리적 정보를 제공하지만, 더 많은 메모리 공간이 필요하다.
1.2.3 자료 구조와 알고리즘의 관계¶
아래 그림(1-4)과 같이 자료 구조와 알고리즘은 밀접하게 연결되어 있다. 그 관계는 다음 세 가지 측면에서 살펴볼 수 있다.
- 자료 구조는 알고리즘의 토대다. 자료 구조는 알고리즘에 체계적으로 저장된 데이터와 이를 조작하는 방법을 제공한다.
- 알고리즘은 자료 구조에 생명력을 불어넣는다. 자료 구조 자체는 데이터 정보만 저장하며, 알고리즘과 결합해야 특정 문제를 해결할 수 있다.
- 같은 알고리즘도 서로 다른 자료 구조를 바탕으로 구현할 수 있지만, 실행 효율은 크게 달라질 수 있다. 따라서 적절한 자료 구조를 선택하는 것이 중요하다.
그림 1-4 자료 구조와 알고리즘의 관계
자료 구조와 알고리즘은 아래 그림(1-5)의 조립 블록에 비유할 수 있다. 블록 한 세트에는 여러 부품뿐 아니라 자세한 조립 설명서도 들어 있다. 설명서를 따라 차례대로 조립하면 멋진 블록 모형을 만들 수 있다.
그림 1-5 블록 조립
구체적인 대응 관계는 아래 표(1-1)와 같다.
표 1-1 자료 구조와 알고리즘을 블록 조립에 비유하기
| 자료 구조와 알고리즘 | 블록 조립 |
|---|---|
| 입력 데이터 | 조립하기 전의 블록 |
| 자료 구조 | 모양, 크기, 연결 방식 등 블록의 구성 형태 |
| 알고리즘 | 블록을 원하는 형태로 조립하는 일련의 작업 단계 |
| 출력 데이터 | 완성된 블록 모형 |
자료 구조와 알고리즘은 프로그래밍 언어에 종속되지 않는다. 이 때문에 이 책에서는 여러 프로그래밍 언어로 작성한 구현을 제공할 수 있다.
관례적으로 사용하는 줄임말
실제로 이야기할 때는 ‘자료 구조와 알고리즘’을 흔히 ‘알고리즘’이라고 줄여 부른다. 예를 들어 널리 알려진 리트코드의 알고리즘 문제는 실제로 자료 구조와 알고리즘 두 분야의 지식을 함께 평가한다.