APSS는 알고리즘문제해결전략 스터디의 이름입니다.
정리를 스랙에서만 하다가 정리가 잘 안되는 것 같아서 velog에 남기겠습니다.
2권에서 1권보다 기본적인 내용이 나오는 것 같네요. 가볍게 정리하고 가겠습니다.
(이미 다알지만 복습해서 숙지한다는 개념으로 ㄱㄱ)
동적배열
파이썬, 타입스크립트 위주로 프로그래밍하다보니 동적배열의 개념이 당연시되어가고 있었던 것 같네요. 배열의 큰 문제 중 하나는 처음에 배열을 선언할 때 배열의 크기를 지정해야하며, 그 이상의 자료를 집어넣을 수 없다는 점입니다.
이와 같은 문제를 해결하기위해 고안된 것이 자료의 개수가 변함에 따라 크기가 변동되는 동적배열(dynamic array)입니다. 저희 파이썬이나 자바스크립트도 밑단은 어차피C++로 구현되어있기 때문에 사실상 동적배열을 쓰고 있는 것입니다.
이름만 봐서는 새로운 자료구조처럼 보이지만 사실상 일반 배열에서 확장된 개념입니다.
배열의 기본적인 특성을 이어받습니다.
- 원소들은 메모리의 연속된 위치에 저장됩니다.
- 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.(임의 접근이 가능)
그리고 동적배열은 추가 특성을 가지고 있습니다.
- 배열의 크기를 변경하는 resize()연산이 가능합니다. 이 동작을 수행하는데는 배열의 크기 N에 비례하는 시간이 걸립니다.
- 주어진 원소를 배열의 맨끝에 추가함으로써 크기를 1 늘리는 append()연산을 지원합니다. 이 동작을 수행하는데는 상수 시간이 걸립니다.
위와 같은 특성(연산)을 구현하기 위해서 동적배열은 동적으로 새로운 배열을 할당받아서 사용합니다. 새로운 크기의 배열을 할당받고 기존의 배열을 복사하는 작업을 하기때문에 O(N)의 시간이 걸리게됩니다.
동적배열의 재할당 전략
이 부분은 append를 어떻게 구현하느냐에 대한 내용이고 조금내용이 딥하기 때문에 추후에 다시 기록하겠습니다.
정리
동적배열은 배열의 단점(길이가 고정적)을 보안하기위해 확장된 개념입니다. 대부분 표준라이브러리로 구현되어있습니다. C++의 Vector, java or c#의 ArrayList 내부적으로는 배열을 사용하기 때문에 배열과 거의 다를 것없는 속도를 제공합니다.
연결 리스트
연결리스트는 참 기본적인 내용인 것 같으면서도 깊게들어가면 어려운 문제들도 많더군요. 면접에서도 단골문제이구요. 이 참에 정리한번 해보겠습니다.
배열의 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에 원소를 삭제하는 것은 시간이 오래 걸리는 작업입니다. 해당 위치 뒤에 있는 원소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야 하기 때문이죠. 평균적인 경우 이 작업은 원소 개수에 선형 비례하는 시간이 걸리게 됩니다.
이와 같은 문제를 해결하기위해 고안된 자료구조가 연결리스트(linked list)입니다. 연결 리스트를 사용하면 특정 위치에 있는 원소의 삽입, 삭제를 상수 시간에 해결할 수 있습니다.
연결리스트는 배열과 아주 다른 형태를 가지고 있습니다. 배열에서는 메모리의 연속된 위치에 각 원소들이 저장되어 있다면, 연결 리스트는 원소들이 메모리 여기저기 흩어져있고 각 원소들이 이전과 다음 원소를 가리키는 포인터를 가지고 있는 방식으로 구현됩니다.(양방향 연결리스트일 경우)
위와 같이 형태의 특성과 탄생이유를 통해 각 자료구조의 장단점을 말할 수 있어야합니다. 그래야 해당 자료구조를 안다고 할 수 있습니다. 저도 대기업 기술면접에서 쉬운내용임에도 불구하고 당황했던 기억이 있습니다.
연결리스트 다루기
배열과 달리 연결리스트에서는 메모리 여기저기에 노드들이 흩어져 있기 때문에 특정 위치의 값을 찾기가 쉽지않습니다. 연결 리스트에서 i번째 노드를 찾아내려면 리스트의 머리에서부터 시작해서 포인터를 따라가며 다음 노드를 찾을 수 밖에 없습니다. 결과적으로 i번째 노드를 찾는데 드는 시간은 리스트의 길이에 선형 비례하게 됩니다.
즉, 배열처럼 상수시간내에 임의의 원소에 접근하기 어렵다는 말입니다.
반면, 다른 노드들의 순성를 유지하면서 새로운 노드를 삽입하거나 기존의 노드를 삭제하는 작업은 아주 간단합니다.(상수시간내에 이루어집니다.)
이와 같이 동적배열과 링크드리스트는 서로 보완하는 관계로 자주 사용됩니다.
동적배열과 연결리스트의 비교
동적배열과 연결 리스트의 가장 큰차이점은 삽입과 삭제, 그리고 임의의 원소에 접근하는데 드는 시간입니다.
삽입과 삭제를 할 일 없거나, 배열의 끝에서만 하면 될 경우에 동적배열이 거의 항상 더 좋은 선택입니다. 임의의 원소에 빠르게 접근할 수 있을 뿐더러, 원소들이 메모리에 연속해 배치되어 있다는 점이 CPU캐시의 효율을 더 높여주기 때문입니다.
그와 반대로 중간 원소를 삽입삭제할 일이 많을 경우, 링크드리스트가 적절하죠.
