[자료구조 1] 배열과 리스트는 각각 언제 사용해야 할까?

가장 기본적인 배열(Array)과 리스트(List)의 특징을 정리해봅니다. 그리고 각각 어떤 상황에 사용하면 좋을지를 알고리즘 문제를 통해 알아보겠습니다.

배열 (Array)

이미 많이 사용해보셨을 테니 특징부터 정리해보겠습니다.

위 그림과 같이 비슷한 특징을 가진 데이터들은 흔히 배열로 저장합니다. 이는 컴퓨터 메모리 상에 실제로 순서대로 저장됩니다.

그래서 우리는 첫번째의 메모리 주소만 알고 있으면 모든 데이터의 값을 바로 접근할 수 있습니다. [첫번째 주소 + 데이터 타입의 크기 * 인덱스 번호]의 위치에 원하는 데이터가 있으니까요. 즉 검색하는 것은 O(1) 이므로 아주 빠릅니다.

하지만 배열에 새로운 데이터를 추가하거나 삭제하고 싶은 경우 메모리 상의 주소를 모두 바꾸어야 합니다. (최악의 경우) 왜냐하면 배열은 메모리상에 순서대로 저장한 자료구조이기 때문에 데이터가 변경되면 다른 데이터의 물리적 위치도 영향을 받기 때문입니다. 즉 O(N)으로 상대적으로 느린 연산이 됩니다.

아래 그림을 참고하시면 이해가 되실 것입니다.

그럼 리스트는 무엇이 다를까요?

리스트 (List)

리스트를 보통 연결리스트(Linked List)라고 부릅니다.

그림처럼 구조는 약간 다르지만 배열과 똑같이 데이터의 묶음을 저장하는 용도로 리스트를 사용합니다. 하지만 리스트는 배열의 단점이 되었던 추가/삭제 연산 성능을 해결하기 위한 자료구조입니다.

메모리 상의 주소를 순서대로 저장하는 것이 아니라 아무 메모리에나 저장하고 대신에 기존 데이터에 부가 정보로 다음 데이터의 주소를 저장합니다. 그렇게 하면 추가/삭제를 해도 전체 데이터 구조가 변하지 않습니다. 즉 추가/삭제 연산이 O(1)이 됩니다.

반면에 5번째 데이터를 찾고 싶으면 처음 주소지에서 다음 데이터의 주소를 건너는 연산이 4번 수행되어야 합니다. 만약 마지막 데이터를 찾으려면 모든 데이터를 한번씩 봐야 합니다. 즉 검색의 연산은 배열보다 느린 O(N)이 됩니다.

배열과 리스트 비교

각각의 특징을 보면 알겠지만 장단점이 명확합니다.

배열: 배열의 끝에서만 추가/삭제 연산을 하거나 추가/삭제 연산이 없는 경우 사용
리스트: 추가/삭제 연산이 많이 필요한 경우 사용

직접 문제를 풀어보면서 배열과 리스트의 차이를 느껴보겠습니다.

예제: 조세푸스 문제

유명한 문제인 조세푸스 문제를 풀어보려고 합니다.

문제 요약: N명의 사람이 있고, K번째 사람을 계속 없앨 때 없어지는 순서 구하기

문제 링크:: 조세푸스 문제(https://www.acmicpc.net/problem/1158)

자세한 문제 설명은 위 링크로 들어가셔서 확인하시고 직접 풀어보세요!

저는 배열과 리스트로 접근해본 결과를 정리하겠습니다.

풀이

배열로 접근하면?

K번째 사람을 제거하고 N-1명의 사람을 다시 순서대로 배열을 저장하는 것을 N번 반복하면 쉽게 풀 수 있습니다.

삭제를 N번 반복하기 때문에 O(N^2)입니다. 문제의 제약조건도 N<=5000 이므로 이 문제를 이렇게 풀어도 됩니다.

아래 코드처럼 구성하면 됩니다.

for (int i = 0; i < N; i++)
{
   int array_size = N - i;
   // 제거
   printf("%d", arr[(K - 1) % array_size]);

   // 제거된 후 배열 재생성
   int start_index = K;
   for (int k = 0; k < N - 1 - i; k++)
      tmp[k] = arr[(start_index + k) % array_size];
   
   // 원래 arr로 복사
   for (int k = 0; k < N - 1 - i; k++)
      arr[k] = tmp[k];
}

리스트로 접근하면?

리스트의 처음 주소부터 시작해 순회를 돌면서 K번째 사람을 제거합니다.

즉 제거하는 데는 O(1)이기 때문에 K번째 사람을 찾는 O(K) 시간이 걸립니다. 이를 N번 반복해야 하기 때문에 O(NK)입니다. 마찬가지로 시간제한에도 문제 없습니다.

std::list<int>::iterator current = list.begin();
for (int i = 0; i < N; i++)
{
   // K번째로 이동
   for (int k = 0; k < K - 1; k++)
   {
      current++;
      if (current == list.end()) current = list.begin();
   }

   // 삭제
   printf("%d", *current);
   current = list.erase(current);
   if (current == list.end()) current = list.begin();
}

이 문제는 위 두 가지 방법으로 모두 해결할 수 있습니다. 하지만 K가 크면 배열을, N이 크면 리스트를 써야 합니다.

물론 조세푸스 문제는 동적계획법을 이용한 O(N) 등 더 빠른 알고리즘이 많이 있습니다.

좋은 예제를 찾기가 어려웠는데 조세푸스 문제로 설명을 많이 하길래 배열과 리스트를 써보면서 비교해봤습니다. 차이점이 잘 와닿으셨을지는 모르겠네요.