누구나 자료 구조와 알고리즘 : http://www.yes24.com/Product/Goods/61941073
컴퓨터 프로그램은 데이터를 입력받아 조작하고 반환하는 게 전부.
자료구조란 데이터를 조직하는 방법.
이 책이 가르치고자 하는 핵심
데이터를 어떻게 조직하는가에 따라 프로그램의 실행 속도는 천차만별일 수 있다!
1.1 배열 : 기초 자료 구조
자료 구조의 기본적인 4가지 연산
- 읽기 : 자료 구조 내 특정 위치를 찾아 값을 읽어오는 것.
- 배열에서는 특정 인덱스의 값을 찾아보는 것.
- 검색 : 자료 구조 내에서 특정 값을 찾는 것.
- 배열에서는 특정 값이 어떤 인덱스에 있는지 알아보는 것.
- 삽입 : 자료 구조에 새로운 값을 추가하는 것 .
- 삭제 : 자료 구조에서 값을 제거하는 것.
연산이 얼마나 '빠른가'를 측정할 때는 순수하게 시간 관점에서 연산이 얼마나 빠른가가 아니라 얼마나 많은 단계가 필요한지를 논해야 한다.
Why?
누구도 어떤 연산이 정확히 얼마나 걸린다고 딱 잘라 말할 수 없다. 하드웨어의 성능에 따라 연산 수행 시간은 달라질 수 있기 때문이다.
1.2 읽기
컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션(격자판)
컴퓨터 메모리 내 각 셀에는 이렇게 특정 주소가 있다.
컴퓨터는 주소만 알고 있으면 해당 메모리 셀에 한 번에 접근할 수 있다.
배열의 요소는 각각 메모리 셀 주소를 가지고 있기에 배열 읽기는 한 단계 만에 끝나는 연산이다.
1.3 검색
컴퓨터는 배열의 인덱스 하나하나에 접근하면서(선형 검색) 검색해나가기 때문에 N개의 셀로 이뤄진 배열은 최대 N개의 단계가 필요하게 된다.
1.4 삽입
배열 삽입에서 최악의 시나리오, 즉 단계가 가장 많아지는 경우는 데이터를 배열의 제일 처음 인덱스에 삽입하는 경우이다.
삽입하기 위해서는 배열의 각 요소를 한칸씩 옮겨 삽입할 데이터를 위해 빈 셀을 만들어주어야한다. 그런데 제일 처음 인덱스에 삽입된다면 모든 배열의 요소가 한 칸씩 옮겨져야한다. 그래서 N개를 포함하는 배열에서 최악의 시나리오일 때 삽입을 위해 N + 1단계가 걸린다.(마지막에 데이터를 삽입하는 것도 하나의 단계이다.)
1.5 삭제
요소 5개를 포함하는 배열이라면 1단계는 요소 하나의 삭제에 그리고 나머지 단계들은 남은 요소들을 옮기는데 사용된다. 그래서 요소 N개를 포함하는 배열에서 삭제에 필요한 최대 단계 수는 N단계이다.
1.6 집합: 단 하나의 규칙이 효율성을 바꾼다
집합은 중복 값을 허용하지 않는 자료 구조.(자바스크립트에서는 집합이 Set이라는 이름으로 지원된다.)
배열과 유일하게 달라지는 연산은 '삽입'이다.
요소 N개의 집합이라면...
- 중복되지 않는 값인지 검사하는데 최대 N단계 소요
- 삽입하는데 최대 N+1 단계 소요
결국 최악의 시나리오의 경우 집합에서의 삽입은 2N + 1 단계가 소요된다.