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

이 책을 읽는 이유

알고리즘에 대한 이해 부족을 보완하기 위해서 시작했다. 약 8개월간 나름대로 꾸준히 알고리즘 문제를 풀었다고 생각했는데도 프로그래머스 기준 Level 1의 마지막 ~ Level 2의 중반에 다다르니 문제에 대한 근본적인 이해가 많이 부족해진다는 생각이 들었다. 어쩌면 길어지는 문제를 읽기 싫은 걸수도...

문제를 '그냥' 푸는 것이 아닌 내가 코드에 사용할 '자료구조'와 정확한 '풀이방법', '시간복잡도' 측면을 스스로 이해하고 문제에 적용하고 풀어야 추후 다양한 기업의 코딩 테스트를 대비하거나 코드를 작성할 때 프로그램 효율성을 체크하며 개발을 할 수 있을 거 같았다.

이력서 첨삭을 도와주셨던 멘토님께서 이 책을 추천해주셨고, 주 2회 정도, 1회 1장씩 읽고 이해하면서 벨로그에 요약해보려고 한다. 책의 내용을 그대로 쓰는 것보다 내가 이해한대로 메모하고, 코드 예시도 때에 따라서 javascript로 변형해서 올릴 수 있다. 또 추가적인 내용을 넣어둘 수도 있다. 그러니 혹시라도 이 글을 보시는 분이 계시다면 참고하시길!

[교보문고] 누구나 자료구조와 알고리즘 (개정2판)
[YES24] 누구나 자료구조와 알고리즘 (개정2판)

1.1 자료구조

코드 목표 3단계
1. 올바르게 돌아가도록 하자, 실제로 동작하게 하자. (코딩 입문 단계)
2. 유지보수성 향상 - 가독성, 조직, 코드 모듈 측면을 포함 (경험이 쌓인 SW 엔지니어)
3. 효율성 향상 - 더욱 빠르게 실행되도록 (고품질 코드)

자료구조 기본 연산
1. 읽기(read) : 자료구조 내 특정 위치의 값을 찾는 것
2. 검색(search) : 자료구조 내 특정 데이터가 있는지, 어디에 위치하는지 찾는 것
3. 삽입(add): 자료구조 내 새로운 값을 추가하는 것
4. 삭제(delete) : 자료구조에서 값을 제거하는 것

• 데이터 (Data) : 모든 유형의 정보를 망라하는 용어
• 자료구조 (Data Structure) : 데이터를 조직하는 방법

대량의 데이터를 처리해야 하는 프로그램에서 데이터를 어떻게 조직하여 사용하는지에 따라 실행 속도의 차이가 생긴다. 다양한 자료구조를 알고, 자료구조를 통해 프로그램 성능에 어떤 영향을 미칠지 알아야 하는 것이 소프트웨어 개발자가 갖춰야 할 능력이다.

1.2 배열

배열(Array)이란?
컴퓨터과학의 기초 자료구조 중 하나이자 데이터 원소들의 리스트

데이터	A	B	C	D	E	F	G
메모리 주소	101	102	103	104	105	106	107
인덱스	0	1	2	3	4	5	6

• 크기 : 배열 안에 데이터 원소가 얼마나 있는지
• 인덱스 : 배열 안에 특정 데이터 원소가 어디에 있는지

1.3 속도 측정

자료구조에서 연산이 얼마나 빠른지를 측정할 때에는 시간 관점이 아니라 얼마나 많은 단계가 필요한가의 관점에서 논해야 한다.

예를 들어 아래 두 코드에서 1번 함수의 경우 100번의 루프를, 2번 함수의 경우 50번의 루프를 돌게 된다. 그러므로 2번 함수가 더 적은 단계를 가지고 있기 때문에 더 빠르다고 할 수 있다.

function test1() {
	let num = 2;
  	
  	while (num <= 100) {
    	if (num % 2 === 0) console.log(num);
      	num += 1;
    }
}

function test2() {
	let num = 2;
  	
  	while (num <= 100) {
    	if (num % 2 === 0) console.log(num);
      	num += 2;
    }
}

코드의 속도를 단계로 측정하는 이유는 컴퓨터 프로그램에서 특정 연산이 정확히 $X$초가 걸린다고 단언할 수 없기 때문이다. 구형 하드웨어에서는 $X + Y$초, 신형 하드웨어에서는 $X - Y$초가 걸릴 수 있다.

이처럼 시간은 연산을 실행하는 하드웨어적 부분에서 생각했을 때 항상 바뀌는 것이므로, 시간 대신 코드가 수행하는 계산 단계(step)로 코드의 속도를 측정하는 것이 연산 속도의 핵심이며 이는 시간 복잡도(Time Complexity)라고 부른다.

1.4 읽기

배열을 선언할 때, 컴퓨터는 사용할 수 있는 메모리 공간 중 연속으로 사용 가능한 부분을 찾아 사용자가 사용할 배열로 지정한다.

예를 들어, 아래와 같이 배열을 선언했을 경우 컴퓨터는 연속적으로 사용 가능한 메모리 공간을 찾고, 해당 공간(연속된 메모리 주소를 가지고 있는 공간)에 값을 할당한다.

let array = ['A', 'B', 'C', 'D', 'E', 'F', 'G'];

🧐 그렇다면 배열의 특정 인덱스에 있는 값을 읽을 때, 컴퓨터는 어떻게 동작할까?

1. 컴퓨터는 기본적으로 모든 메모리 주소에 한 번에 접근할 수 있다.
2. 컴퓨터는 배열을 할당할 때 어떤 메모리 주소에서 시작하는지 기록해둔다. (= 배열의 첫 번째 값 찾기)

배열의 첫 번째 값이 아닌 $N$번째 값을 찾을 때에는 '덧셈'을 수행한다. 인덱스 5에 위치한 값을 찾고싶을 때, 인덱스 0의 메모리 주소에 5를 더하여 해당 인덱스에 접근합니다.

이렇듯 배열에서 특정 위치의 값을 읽어내는 것은 메모리 주소와 인덱스를 통해 바로 접근이 가능하기 때문에 $O(1)$의 시간복잡도를 가진다.

1.5 검색

👩🏻‍💻 내가 알고 있는 값이 해당 배열에 있는지 알아보고, 어디에 위치하는지 찾고싶어!

위와 같이 배열에 특정 값이 존재하는지 알아보고, 어떤 인덱스에 위치하는지 찾는 것을 검색(search)이라고 한다.

검색은 읽기와 효율성 측면에서 큰 차이를 가진다. 컴퓨터는 특정 메모리 주소에 쉽게 접근할 수 있고, 인덱스를 통해 배열의 특정 인덱스에 접근하여 값을 알아낼 수 있지만 특정 값(데이터)만으로 해당 메모리 주소에 접근할 수 없어 배열의 처음부터 값을 찾을 때까지 검색해야 하기 때문이다.

만약 배열에 $N$개의 데이터가 있다고 가정했을 때, 그 중 특정 값을 찾기 위해 배열을 선형검색하는데 걸리는 최대 단계는 $N$개이다. 그러므로 배열 검색의 기본 시간복잡도는 $O(N)$이다.

선형 검색 (Linear Search)
컴퓨터 한 번에 하나의 셀을 확인하는 방법

1.6 삽입 (추가)

배열에 새로운 데이터를 삽입(add)하는 것은 배열의 어디에 삽입하는가에 따라 효율성의 차이가 있다. 컴퓨터가 배열을 만들 때 시작하는 메모리 주소를 기억하고 있는 것처럼, 배열의 크기도 함께 기억하고 있다.

즉 배열에 마지막에 데이터를 추가할 때, 시작 메모리 주소에서 배열의 크기만큼 더하여 마지막 메모리 주소를 계산하고, 그 다음 메모리 주소에 새로운 데이터를 할당한다. 이는 한 단계로 이루어져 있다.

A	B	C	D	E
0	1	2	3	4

A	B	C	D	E	F
0	1	2	3	4	5

😧 그런데 저는 배열의 처음이나 중간에 새 데이터를 넣고싶은데요?

이 경우에는 삽입할 공간을 만들기 위해 다른 데이터들을 이동시켜야 한다. 즉 실행 단계가 늘어나게 된다.

A	B	C	D	E
0	1	2	3	4

인덱스 2번 위치에 새로운 데이터 Z 를 추가하기 위해서는 다음과 같은 과정이 필요하다.

A	B	C	D	E
0	1	2	3	4	5

A	B	C	D		E
0	1	2	3	4	5

A	B	C		D	E
0	1	2	3	4	5

A	B		C	D	E
0	1	2	3	4	5

A	B	Z	C	D	E
0	1	2	3	4	5

마지막 공간을 만들어 E를 옮기고, 빈 자리에 D를 옮기고, 다시 빈 자리에 C를 옮기고... 인덱스 2 위치가 비게될 때까지 데이터를 이동시켜야 한다. 만약 배열의 맨 앞에 데이터를 추가하고 싶은 경우에는 배열 내 모든 값을 전부 한 셀씩 이동해야 한다.

$N$개의 데이터를 가지고 있는 배열에서 새로운 데이터를 추가하기 위해서는 $N$번의 단계가 필요하다. 그러므로 배열에 데이터를 추가할 때 시간복잡도는 $O(N)$이다.

1.7 삭제

배열에서 특정 값을 제거할 때, 컴퓨터는 배열의 인덱스를 통해 원하는 값에 바로 접근이 가능하기 때문에 원하는 데이터를 찾아 삭제한다.

A	B		D	E
0	1	2	3	4

오직 '삭제'만 했을 경우 기술적으로 1단계로 이루어져 있지만, 값을 삭제한 이후 특정 셀이 비어있게 된다. 연속된 메모리 공간을 가지고 있는 배열의 자료구조 특성상 배열 중간에 빈 공간이 있을 경우 이는 효율적이지 않기 때문에 남은 데이터를 이동시켜야 한다. 즉, 추가 단계가 필요하다.

A	B	D		E
0	1	2	3	4

A	B	D	E
0	1	2	3

🥲 가장 처음에 있는 데이터를 삭제하게 되면...

삽입과 마찬가지로 배열의 첫 번째 데이터를 삭제하게 되면 0번째 인덱스가 비어있게 되므로, 남아 있는 모든 원소를 왼쪽으로 하나씩 이동시켜 빈 공간을 채워야 한다. 만약 원소가 5개인 배열에서 1단계는 원소 삭제, 남은 원소를 이동시키는데 4단계를 거치게 된다.

만약 $N$개의 원소를 포함하는 배열이 있다면, 배열을 삭제하는데 필요한 단계는 총 $N$단계가 되므로 배열 삭제의 시간복잡도는 $O(N)$이다.

1.8 집합

집합(Set)이란?
중복 값을 허용하지 않는 자료구조

배열 기반의 집합에서 읽기, 검색, 삭제는 배열의 시간복잡도와 동일하지만 삽입은 다르다.

배열에서 새로운 데이터를 추가할 때, 배열의 가장 마지막에 추가하는 경우 필요한 단계는 1단계이다. 그러나 집합에서는 새로 삽입하려는 데이터가 이미 집합에 포함되어 있는지 체크해야 한다.

컴퓨터는 배열이나 집합에서 어디에 어떤 값이 있는지 바로 알 수 없기 때문에 삽입하려는 값이 이미 있는지 알기 위해서는 '검색'이 선행되어야 한다. 즉, 집합에서 모든 삽입에는 먼저 검색 단계가 실행된다.

특히 집합의 맨 앞에 새로운 데이터를 삽입하는 경우, $N$개의 요소를 검색하여 해당 데이터가 없음을 확인하고, 다시 $N$개의 요소를 전부 한 셀씩 이동시켜 새로운 공간을 만든다. 그리고 값을 삽입한다. (총 $2N + 1$ 단계 소요)

🤔 그럼 집합은 언제 사용해야 효율적인 걸까?

중복 데이터를 없애야 하는 경우 집합을 사용하는 것이 정답이다. 하지만 중복 제거의 요구사항이 없다면 집합에서 삽입하는 것보다 배열에서 삽입하는 것이 효율적이므로 배열을 사용하는 것이 좋다.

요약

• 배열이란 컴퓨터과학의 기초 자료구조 중 하나이자 데이터 원소들의 리스트이다.
• 배열 읽기의 시간복잡도는 $O(1)$이다.
• 배열 검색의 시간복잡도는 $O(N)$이다.
• 배열 삽입의 시간복잡도는 $O(N)$이다.
• 배열 삭제의 시간복잡도는 $O(N)$이다.
• 집합은 배열과 유사하지만 삽입의 경우 검색 단계가 추가된다.
• 프로그램의 요구사항을 바탕으로 매순간 적합한 자료구조를 사용해야 한다.