[Algorithm] 알고리즘 공부가 필요한 이유

독학으로 하는 코딩테스트 공부는 뭔가 부족해서, 알고리즘 강의를 듣기 시작했다.
무작정 시간복잡도에 대해 공부하다가 더 근본적인(?) why에 대해 먼저 정리하고 싶었다.
마침 유튜브에 니꼬쌤의 강의가 있어서
데이터구조와 알고리즘을 먼저 이해하고 알고리즘 공부를 하기로 했다.

초보 입장에서 알고리즘을 당장 배울 필요는 없다. 일단 구현을 해내는게 더 중요하기 때문.
하지만 일단 구현을 다 하고나서 버그도 없고 별다른 문제가 없는데
느릴때, 어떻게 최적화 해야할지 잘 모르겠을 때,
그때가 바로 알고리즘과 자료구조를 알아야 할 때이다.

알고리즘

여러개의 지시사항이며 단계들이라고 말할 수 있다.
어떤 액션을 수행하기 위해 필요한 절차이다.

자료구조

모든 작업에는 데이터가 필요하다.
백엔드는 데이터베이스를 가공해서 활용할 수 있도록 만들고
프론트엔드는 가공된 데이터를 보기 쉽게 정리해서 화면에 표현한다.

이때 이 데이터를 어떻게 정리해서 활용하는지에 따라 스피드가 달라진다.
어떤 데이터구조를 사용하느냐에 따라 달라지는 것이다.

데이터구조의 종류는 많다.
어떤 구조는 데이터 정렬에 최적화 되어있고, 어떤 구조는 검색에 최적화 되어있다.
각 데이터구조의 특징을 알고 나서
검색하고, 읽어오고, 추가하고, 삭제하는 상황에서 가장 잘 맞는 구조를 활용할 줄 알아야한다.

그 중 가장 심플한 데이터 구조는 Array이다.

Array

먼저 메모리 관점에서 배열이 어떤것인지 생각해보자.

메모리는 비휘발성과 휘발성 메모리가 있다.
비휘발성은 하드디스크 같이 데이터를 저장해두고 컴퓨터를 껏다켜도 데이터가 남아있게 하는 메모리이다.
휘발성 메모리는 RAM과 같이 컴퓨터를 껏다 켜면 초기화되는 메모리이다.

RAM의 풀네임을 처음 알게 되었다. Random Access Memory.
RAM은 여러개의 방을 가지고 있고, 각 방에는 주소가 있어서
순서에 상관없이 원하는 지점으로 바로 접근할 수 있다.
그래서 1000번째 방에 접근하든, 1번째 방에 접근하든 걸리는 시간은 동일하다.

(하드디스크는 실제로 디스크가 돌아가면서 순차적으로 데이터를 읽어온다고 한다. 신기..)

Array도 마찬가지 방식이다. 몇번째 인덱스의 값에 접근하든 걸리는 시간은 동일하다.

하지만 Array는 선언 시 배열의 크기를 정해서 선언해야하고, 크기의 수정이 불가능하며
중간 요소를 추가 및 삭제 시 공백이 생기지 않도록
그 뒤에 다른 요소들의 위치를 모조리 바꿔줘야하는 단점이 있다.
but 스크립트 언어는 배열의 크가 동적으로 증감되도록 만들어져 있기는하다.(시간복잡도가 늘어날 뿐)

Read : Array 자료 읽어오기

앞서 정리한 것과 같이 Array 자료는 Random Access가 가능하기 때문에
읽어오고싶은 데이터의 인덱스만 알고있으면 빠르게 접근이 가능하다.

Searching : Array 자료 검색하기

그냥 읽어오는 것과 달리, 원하는 데이터가 어디 있는지 모르는 경우이기 때문에
방을 하나하나 열어보며 원하는 데이터를 확인해야하는 과정이 필요하므로 느려진다.
만약 원하는 데이터가 처음에 있다면 빠르겠지만,
맨 뒤에 있는 경우 모든 방을 열고나서야 데이터를 찾을 수 있다.
심지어 모두 열어서 확인했는데 원하는 데이터가 없는 경우도 있을 수 있겠다.

이런 과정을 Linear Search(선형 검색) 라고 한다.
그래서 이런 배열 검색을 빠르게 하는 방법들도 있는데 그것은 천천히 확인해보자.

Insert : Array 자료에 추가하기

Array를 선언할때는 메모리 공간을 미리 확보해야한다. (길이를 정해줘야한다.)
선언한 array에 빈공간이 있다고 했을때,
데이터를 맨 끝에 추가하는 경우 그냥 빈공간에 데이터를 넣으면 된다.
하지만 중간에 넣는 경우,
그 자리를 차지하던 데이터와 뒤쪽 데이터들까지 전부 한칸씩 옮긴다음 데이터를 추가하게 된다.
그래서 맨앞의 자리에 데이터를 추가하는 경우가 가장 느리다고 보면 된다.

또한 배열의 길이만큼 데이터가 꽉 찼는데 추가해야하는 경우
필요한 만큼 더 긴 길이의 배열을 새로 선언하고, 기존 데이터를 옮겨온 후,
데이터를 추가하는 과정까지 필요해진다.

Delete : Array 요소 삭제하기

데이터를 추가하는 경우와 동일하다.
마지막 요소를 삭제하는 것은 빠르지만, 중간이나 처음 요소를 삭제해야하는 경우
다른 데이터들이 공백을 채우기 위해서 모두 움직여야(shift해야)한다.

그래서 검색을 해야하거나, Array의 처음이나 중간에 요소를 추가 혹은 삭제해야한다면
속도가 빠른 다른 데이터구조를 사용해주는 것이 좋다.

const arr = [1, 2];
arr.push(3); // arr 끝에 3 추가 [1, 2, 3]
arr.push(4, 5); // arr 끝에 여러 값 추가 [1, 2, 3, 4, 5]
arr.splice(2, 2); // 2번째 인덱스로부터 2개 요소 삭제 [1, 2, 5]
arr.splice(2, 0, 3); // 2번째 인덱스에 0개 삭제, 3 추가 [1, 2, 3, 5]
// splice로 값을 중간에 추가 및 삭제한다면
// 그 뒷 값을도 모두 자리를 옮겨야하기 떄문에 O(N)의 시간복잡도를 가진다.(선형증가)