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

코드 품질의 다양한 척도

• 코드 유지 보수성 즉, 가독성, 조직, 코드 모듈성 같은 측면을 포함.
• 코드 효율성.

const printNumbersVersionOne = () => {
	let number = 2;
	while (number <= 100){
		if(number % 2 === 0) {
			console.log(number);
			number++;
	}
}
}

const printNumbersVersionTwo = () => {
	let number = 2;
	while(number <= 100){
		console.log(number)
		number += 2;
	}
}

• 첫 번째 버전은 루프를 100번 돌고 끝나지만 두 번재 루프는 50번만 돈다.
• 따라서 첫 번째 버전이 두 번재 버전보다 두 배 더 많은 단계를 거치기 때문에 두 번째 함수가 더 빨리 실행된다.

1-1 자료구조

데이터란? : 일반적으로 모든 유형의 정보를 망라하는 용어이며 가장 기초적인 수와 문자열로 이뤄진다.

자료구조? : 데이터를 조직하는 방법

const x = "Hello! "
const y = "How are you "
const z = "today?"

console.log(x+y+z);

const array = ["Hello! ", "How are you ", "today?"]
console.log(array[0],array[1],array[2]);

1-2 배열: 기초 자료 구조

배열? : 컴퓨터 과학에서 기초적인 자료 구조 중 하나. 데이터 원소들의 리스트.

배열의 크기? : 배열에 데이터 원소가 얼마나 들어있는지 알려준다.

배열의 인덱스? : 특정 데이터가 배열의 어디에 있는지 알려주는 숫자.

1-2-1 자료 구조 연산

대부분의 자료 구조는 네 가지 기본 방법을 사용한다.

읽기? : 자료 구조 내 특정 위치를 찾아보는 것. 배열에서는 특정 인덱스의 값을 찾아보는 것을 뜻한다.

검색? : 자료 구조 내에서 특정 값을 찾는 것. 어떤 인덱스에 있는지 알아보는 것.

삽입? : 자료 구조에 새로운 값을 추가하는 것. 배열 내에 슬롯을 더 만들어 새 값을 추가하는 것을 뜻한다.

삭제? : 자료 구조에서 값을 제거하는 것. 배열에서는 배열의 값 중 하나를 제거하는 것을 뜻한다.

1-3 속도 측정

연산이 얼마나 빠른가를 측정할 대는 순수하게 시간 관점에서 연산이 얼마나 빠른가가 아니라 얼마나 많은 단계가 필요한지를 논해야 한다.

1-4 읽기

컴퓨터는 딱 한 단계로 배열에서 읽을 수 있다. 배열 내 특정 인덱스에 한 번에 접근해서 볼 수 있기 때문이다.

컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이라 할 수 있다.

• 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다.
• 컴퓨터는 배열을 할당할 대 어떤 메모리 주소에서 시작하는지도 기록해 둔다. 그래서 배열의 첫 번째 원소를 찾으라고 요청하면 적절한 메모리 주소로 바로 가서 찾는다.
• 컴퓨터는 어떤 인덱스에 있는 값이든 간단한 덧셈을 수행해 찾을 수 있다.

1-5 검색

배열 검색은 배열에 특정 값이 있는지 알아본 후, 있다면 어던 인덱스에 있는지 찾는 것이다

읽기? : 컴퓨터에 인덱스를 제공하고 그 인덱스에 들어 있는 값을 반환하라고 요청한다.

검색? : 컴퓨터의 값을 제공하고 그 값이 들어 있는 인덱스를 반환하라고 요청한다.

• 인덱스에서 읽기는 컴퓨터가 어떤 인덱스든 바로 가서 인덱스에 있는 값을 찾을 수 있으니 매우 빠르다
• 이와 달리 검색은 컴퓨터가 특정 값으로 바로 갈 수 없으니 오래 걸린다

선형 검색? : 검색 연산, 즉 컴퓨터가 한 번에 한 셀씩 확인하는 방법

• N개의 셀로 이뤄진 배열은 선형 검색에 최대 N개의 단계가 필요하다고 말할 수 있다.

검색인 읽기보다 덜 효율적이다. 읽기는 배열이 얼마나 크든 항상 한 단계만 걸리지만 검색에는 많은 단계가 걸릴 수 있다.

1-6 삽입

배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다.

배열이 메모리 주소 1010에서 시작하고 크기가 5면 마지막 메모리 주소가 1014가 된다. 따라서 그 뒤에 항목을 삽입하면 다음 메모리 주소인 1015에 항목을 추가한다는 뜻.

컴퓨터는 새 값을 삽입할 메모리 주소를 계산할 수 있고, 이는 한 단계면 된다.

배열 삽입에서 최악의 시나리오, 즉 삽입에 가장 많은 단계가 걸리는 시나리오는 데이터를 배열의 맨 앞에 삽입할 때다. 배열의 앞에 삽입하면 배열 내 모든 값을 한 셀씩 오른쪽으로 옮겨야 하기 때문이다.

1-7 삭제

배열의 삭제는 특정 인덱스의 값을 제거하는 과정.

원소 삭제에서 최악의 시나리오는 배열의 첫 번째 원소를 삭제하는 것이다. 이렇게 되면 인덱스 0이 비게 되고, 남아 있는 모든 원소를 왼쪽으로 이동시켜 빈 공간을 채워야 한다.

1-8 집합

집합은 중복 값을 허용하지 않는 자료 구조다

배열 기반 집합? : 값들의 단순 리스트로 배열과 거의 비슷하다.

배열 기반 집합과 일반적인 배열 간 유일한 차이점은 집합은 중복 값의 삽입을 절대 허용하지 않는다는 점이다.

배열 기반 집합은 중복 금지라는 제약이 추가된 배열이다. 중복을 허용하지 않는 기능이 유용하기는 하나 이 간단한 제약으로 인해 네 주요 연산 중 하나에서 집합의 효율성이 크게 달라진다

집합의 끝에 삽입하려면 원소 N개에 대해 최대 N+1 단계가 필요하다.

• 검색에 N단계
• 삽입할 공간을 만드는데 N단계
• 삽입하는데 1단계

삽입이 일반적인 배열보다 집합에서 느리다는 이유만으로 집합을 쓰지 말아야 한다면 물론 아니다. 중복 데이터가 없어야 할 때는 집합이 답이다. 하지만 이러한 요구사항이 없다면 집합 삽입보다 배열 삽입이 더 효율적이므로 배열이 나을 수 있다.

1-9 마무리

자료 구조의 성능 측정은 연산에 필요한 단계 수를 구하는 게 핵심이다.