누구나 자료 구조와 알고리즘(개정2판) 1장

1. 자료 구조가 중요한 까닭

자료 구조: 자료를 조직하고 저장하는 방법이다. 자료(데이터)를 어떻게 조직하느냐에 따라 프로그램의 실행 속도는 천차만별로 달라질 수 있다.

ex. 책장에 책을 어떻게 진열할 것인가?
연도 순, 알파벳 순, 가로 정렬 등등

자료 구조와 다르게, 알고리즘은 원하는 책을 어떤 방법으로 찾을 것인가?

 

1.2. 배열

번호(인덱스)와 번호에 대응하는 값들로 이루어진 자료 구조를 나타낸다. 인덱스가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.

자료 구조에 사용되는 4가지 기본 연산이 있다.

• 읽기: 자료 구조 내 특정 위치를 찾아보는 것. 배열에서는 특정 인덱스의 값을 찾아보는 것을 뜻한다.
• 검색: 자료 구조 내 특정 값을 찾는 것. '사과'가 과일 목록에 있는지, 어떤 인덱스에 있는지 알아보는 것을 뜻한다.
• 삽입: 자료 구조에 새로운 값을 추가하는 것.
• 삭제: 자료 구조에서 값을 제거하는 것.

1.3. 속도 측정

그렇다면 연산의 속도를 어떻게 측정할까?
연산이 얼마나 '빠른가'를 측정할 떄는 순수하게 시간 관점에서 연산이 얼마나 빠른가가 아니라 얼마나 많은 단계가 필요한지를 논해야 한다. 왜 연산의 속도를 단계로 측정해야 될까? 어떤 연산이 정확히 5초 걸린다고 단정할 수 없기 때문이다. 같은 연산도 슈퍼 컴퓨터에서는 훨씬 빠를 수도 있기 때문이다.
반면, 계산 단계는 컴퓨터 사양에 관계없이 계산 단계가 적으면 적을수록 항상 빠를 것이다.
이 책에서는 연산에 걸리는 단계수를 속도, 시간 복잡도, 효율성, 성능 이라는 용어와 같은 의미로 사용한다.

1.8. 집합

집합은 중복 값을 허용하지 않는 자료 구조다. 집합의 종류는 다양하지만 여기서는 배열 기반 집합을 다룬다. 집합은 중복 데이터가 없어야 할 때 유용하다.
배열에서 맨 끝에 데이터를 삽입하는 경우 1단계 만에 값을 끝에 삽입하면 되지만, 집합에서는 이 값이 이미 집합에 들어있는지 검색부터 해야 한다. 즉 N개의 원소가 있는 집합이 있다면 값이 집합에 없음을 확인하는 데 N단계의 검색과 실제 삽입에 1단계를 쓰는 N+1단계가 필요하다.
값을 집합의 맨 앞에 삽입하는 최악의 시나리오일 때 컴퓨터는 N개를 검색해서 집합이 그 값을 포함하지 않음을 확인한 후, 또 다른 N단계로 모든 데이터를 오른쪽으로 하나씩 옮겨야 하며, 마지막 단계에서 새 값을 삽입하는 총 2N+1단계가 필요하다.