_5_ 자료구조 — 배열, 동적 배열

MJ Studio
알고리즘은 미친짓이다
8 min readMay 2, 2022

자료구조란 무엇인지 살펴보고 기본적인 배열 자료구조와 시간복잡도, 활용법에 대하여 알아봅시다.

자료구조란?

자료구조라 부르는 것은 흔히 데이터를 담는 그릇입니다. 우리가 흔히 아는 배열이나 리스트는 흔히 일차원으로 쭉 펼쳐진 그릇에 데이터를 담는 역할을 합니다. 배열 안에 다른 배열이 있음으로 2차원 배열처럼 격자처럼 볼 수 있기도 하지만요.

자료구조는 정말 무수히 많으며 각기 특화된 연산이 있습니다. 어떤 자료구조는 어떤 연산에 좀 더 빠른 시간복잡도를 가지며 문제에서 요구하는 연산이 삽입과 삭제가 빠른 자료구조라면 그걸 빠르게 지원하는 자료구조를 골라서 문제를 해결해야 합니다.

어떤 자료구조들은 다른 고급 자료구조들을 만드는 제물(?)이 되기도 합니다. 예를 들어, 트리 자료구조는 동적 배열을 이용해서도 구현되기도 합니다.

자료구조는 특정 알고리즘들에서 필수로 알아야 하는 개념이 되기도 합니다. 예를 들어, 그래프 탐색 방법의 하나인 BFS 같은 경우, 보통 큐 자료구조를 이용해 구현됩니다.

또한, 자료구조들은 어떤 연산들에 대해 동일하거나 혹은 더 빠른 시간복잡도를 보장한다면 대체될 수 있습니다. 예를 들어, 문제에서 어떤 수들을 가지고 삽입을 하며 가장 큰 수와 가장 작은 수를 빠르게 찾아내는 연산을 요구한다고 할 때, 내부적으로 Balanced Binary Search Tree로 구현된 Ordered Set(정렬 집합) 자료구조와 대충 배열로도 구현할 수 있는 Priority Queue(우선순위 큐)를 아무거나 사용해서 문제를 풀 수 있습니다.

하지만 이 경우 Priority Queue는 보통 그러한 연산에 최적화된 구현체를 갖기 때문에 가장 큰/작은 원소를 찾는 데 동일하게 O(logN)이 걸리더라도 조금 더 빠르게 문제를 해결할 수 있습니다. 그러면 문제의 분류에 Priority Queue가 붙지 Ordered Set이 붙진 않습니다.

정적 배열(Static Array)

배열은 굉장히 많은 자료구조에서 기반이 되는 흔한 자료구조입니다.

프로그래밍을 처음 배울 때 배열의 인덱스는 0부터 시작한다는 이유 때문에 굉장한 혼동이 옵니다. N개의 데이터가 있으면 인덱스는 [1, N]이 아닌 [0, N-1] 이 됩니다.

언어에 따라 모든 요소에 동일한 타입만 지정할 수 있기도 하고 이것저것 괴랄하게 다르게 지정할 수 있기도 합니다.

배열의 불변의 가장 강력한 기능 중 하나는 특정 인덱스의 원소를 O(1)로 참조할 수 있다는 것입니다.

이게 당연하다고 생각하면 안됩니다. 집합 자료구조 같은 경우 인덱스의 원소를 O(1)에 참조할 수 없습니다.

이건 기본적인 자료구조이므로 C언어로 작성된 코드를 봅시다.

이 코드에서 중요한건 이건 정적(static) 배열이기 때문에 처음에 딱 5개의 공간을 지정해서 만들었다는 것입니다.

보통 문제에서 N개의 수가 들어온다고 말해줍니다. N이 200이라고 해봅시다.

그럼 이렇게 우리가 쓸 공간들을 미리 할당해줄 수 있습니다. 왜냐면 우린 N≤200 이라는 것을 알고 있기 때문에 이 배열을 사용할 때도 다음과 같이 사용해줘도 되기 때문입니다.

어떤 테스트 케이스에서 N=100 이라도 문제가 되지 않습니다. 왜냐면 100개의 남는 공간이 생길지라도 어차피 N이라는 숫자를 알기에 N개만 공간을 쓰면 되기 때문입니다.

흔히 Out of Index 에러를 피하기 위해 대충 N≤200 이라면 자신의 습관에 따라 다음과 같이 정적 배열을 선언해대는 사람들도 많습니다. 자유롭게 선언해주시면 됩니다.

정적 배열의 단점은 일단 사용할 공간을 프로그램 시작 전에 정해서(코드로) 이 만큼 할당할 것이라고 지시를 해놔야 한다는 점입니다.

어떤 문제에서 다음과 같이 입력이 주어진다고 해봅시다.

1 ≤ T ≤100,000 개의 테스트 케이스가 주어지고 각 테스트 케이스는 1 ≤ N ≤ 200,000 개의 숫자가 들어온다.
단, 모든 테스트 케이스에서의 N의 합은 1,000,000를 넘지 않는다.

이렇다고 했을 때 다음과 같이 코드를 짜봅시다.

겉보기엔 문제가 없어보입니다.

하지만 이는 보통 시간 초과(TLE)로 이어집니다. 왜냐하면 T가 100,000 이라고 생각해봤을 때 매번 길이 200,000를 가진 배열을 만들어대기 때문입니다.

변수를 선언하는 과정도 시간이 듭니다. 보통 O(1) 이라고 보시면 될 것 같습니다.

이 문제를 해결하는 방법은 그냥 다음과 같이 계속해서 변수를 초기화하지 않거나,

이제 다음에 배울 필요한 만큼만 공간을 할당할 수 있는 동적 배열을 사용하면 됩니다!

동적 배열(Dynamic Array)

동적 배열은 앞서 언급한대로 프로그램의 런타임 때 변수에서 알고있는 정수길이만큼 배열을 사용할 공간의 크기를 동적으로 할당할 수 있는 자료구조입니다.

이 뿐만 아니라 원소의 삽입과 삭제도 가능합니다!

정적 배열과 동적 배열의 시간복잡도/공간복잡도 차이는 거의 없다고 보시면 됩니다.(하지만 극한의 최적화가 필요하다면 N차원 배열에서는 동적 배열이 좀 더 느리고 정적 배열이 미세하게 더 빠릅니다.)

자신의 언어에서 사용되는 동적 배열은 흔히 접하셨을 겁니다. PS뿐만 아니라 개발에도 흔히 사용되는 자료구조이기 때문입니다.

C++에선 보통 std::vector나 Python에선 그냥 리스트, Java에선 ArrayList 를 쓰기도 합니다.

동적 배열은 자료구조의 크기를 런타임때 정할 수 있다는 장점도 있지만, 강력한 기능인 삽입과 삭제를 지원한다는 장점도 있습니다.

하지만 치명적인 단점이 존재하는데, 바로 배열의 맨 뒷부분에서만 삽입과 삭제가 가능하다는 것입니다.

정확히 말하면 배열의 맨 뒷부분에선 삽입과 삭제는 O(1)이 걸리고 다른곳에서는 O(N)입니다.

동적 배열은 인덱스 0부터 1, 2, 3에 계속해서 원소들을 넣거나 빼는 자료구조입니다.

다음과 같은 그림을 봅시다. 6개의 데이터를 담고 있는 동적 배열입니다.

여기서 하나를 추가해보겠습니다.

제일 뒤에 추가를 하는 과정은 그냥 바로 덧붙일 수 있으니까 바로바로 할 수 있겠죠? 그래서 O(1) 입니다.

반대로 다시 제일 뒤의 삭제도 O(1) 입니다.

이를 각 언어별 코드로 봅시다. 일단 파이썬을 볼까요?

파이썬의 리스트에서 왜 원소를 추가하는 함수의 이름이 appendpop 일까요? 그리고 왜 insert 라고 따로 인덱스를 넘겨주어서 원소를 삽입하는 함수를 따로 만들어두었을까요?

그건 바로 appendpop 은 제일 마지막 원소를 삽입하고 삭제하기 위한 특별한 함수이기 때문입니다.

그럼 중간에 원소를 추가하거나 삭제하는 것은 왜 O(N) 일까요?

우리가 2 뒤에 6을 추가하고 싶다고 합시다. 어떻게 해야할까요?

동적 배열도 그냥 배열이기 때문에 갑자기 2와 3사이를 찢어버린 후 6을 넣고 다시 봉합하거나 이런 것들이 불가능합니다. 따라서 대략 다음과 같이 진행된다고 생각할 수 있습니다.

일단 뒤에 3개를 뺍니다.

그리고 우리가 넣으려던 원소인 6을 push(append 등이라고 불림) 합니다.

이제 다시 3, 4, 5를 제일 뒤에 붙여주면 우리가 원하는 형태가 나올 것입니다.

일련의 과정에서 총 행해지는 연산은 O(N)번 입니다. 가장 앞에 있는 부분에서 삽입이 일어난다면 대략 N번 정도 pop을 하고 N번 정도 push를 해야하는 것 아셨나요?

이를 파이썬에선 다음과 같이 insert로 할 수 있습니다.

C++은 std::vector를 다음과 같이 쓸 수 있고,

https://gist.github.com/6260ef15f41abc719541dd531bb537a7

https://gist.github.com/6260ef15f41abc719541dd531bb537a7

Java는 대략 다음과 같습니다.

연습 문제

배열의 연습 문제는 별게 없습니다. 연습 문제를 푸는 것도 좋지만, 직접 배열의 연산들인 제일 뒤의 push, pop 중간에서의 insert, remove 같은 것들을 자신의 언어에서 사용법을 익히고 시간복잡도를 숙지하는 것이 중요합니다.

--

--