[자료구조] 배열

 

배열

 

---

 

# 자료 구조란

 

 자료 구조란 데이터를 조작하는 방법이다. 같은 코드를 작성하더라도 그 코드를 구현하는데에는 다양한 방법이 존재한다. 그리고 코드를 효율적으로 동작시키기 위해서는 그 중에서도 가장 빠른 코드를 작성해야 한다. 그렇다면 무엇이 '더 빠른 코드'인가? 코드의 실행 속도는 코드를 실행하는데 걸리는 시간으로 판단하지 않는다. 같은 코드라도 컴퓨터마다 그 실행 속도가 다르기 때문이다. 코드의 실행 속도는 '코드를 실행하기 위해 몇 단계가 필요한지'로 판단한다. 같은 기능을 구현하는 코드라도 5단계만에 실행이 완료되는 코드보다 3단계만에 실행이 완료되는 코드가 더 빠른 코드가 되는 것이다. 이를 시간 복잡도라고 한다.

 

 

# 배열

 

 배열은 가장 기초적인 자료 구조이다. 배열의 연산을 통해 코드가 자료 구조와 어떻게 상호작용하는지를 분석해보자. 대부분의 자료 구조는 4가지 연산을 사용한다.

 

1. 읽기 : 자료 구조 내의 특정 위치를 찾아보는 것. 배열에서는 특정 인덱스의 값을 찾아보는 것을 의미한다.

2. 검색 : 자료 구조 내의 특정 값을 찾는 것. 배열에서는 값이 배열 내에 있는지, 어떤 인덱스에 있는지 찾는 것을 의미한다.

3. 삽입 : 자료 구조에 새로운 값을 추가하는 것. 배열에서는 배열 내에 슬롯을 더 만들어 새 값을 추가하는 것을 의미한다.

4. 삭제 : 자료 구조에서 값을 제거하는 것. 배열에서는 배열의 값 중 하나를 제거하는 것을 의미한다.

 

 배열을 통해 읽기, 검색, 삽입, 삭제에 대해 알아보고 각각 얼마나 많은 단계가 필요한지 알아보자.

 

 

1. 읽기

 

 컴퓨터는 배열에 접근할 때 단 한 단계만에 접근할 수 있다. [a, b, c, d, e]라는 배열이 있을 때 프로그램이 2번 인덱스의 값을 달라고 하면 바로 배열의 인덱스 2로 가서 c라는 값이 있다고 알려준다. 이게 가능한 이유는 무엇일까?

 

 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다. 100번 메모리에 가달라고 하면, 바로 100번 메모리로 간다. 0번, 1번, ... 이렇게 하나하나 찾아가지 않는다. 또한, 컴퓨터는 메모리에 배열을 저장할 때, 배열이 시작되는 메모리 주소와 배열의 크기도 기억해놓는다. 따라서 우리가 배열의 3번째 원소를 찾고 싶다면, 컴퓨터는 바로 해당 배열이 시작되는 메모리 주소로 간 뒤 +3을 하여 값을 가져올 수 있는 것이다. 따라서 배열 속의 특정 원소를 읽는 것은 한 단계만에 가능하다.

 

 

2. 검색

 

 컴퓨터는 배열의 인덱스만 알고 그 속의 값은 알 수 없다. 그래서 검색은 단순 읽기와는 다르게 많은 단계가 필요하다. 따라서 특정 값을 찾고 싶다면 인덱스 0부터 하나하나 값을 확인해야 한다. 이렇게 컴퓨터가 한 번에 하나만 확인하는 방법을 선형 검색이라고 한다. 만약 찾고자 하는 원소가 배열의 가장 마지막에 있다면 어떻게 될까? 모든 원소를 검색해야 할 것이다. 따라서, N개의 원소가 있는 배열에서 선형 검색을 한다면 최대 N개의 단계가 필요하다.

 

 

3. 삽입

 

 배열에 추가적으로 원소를 삽입하는 것은 어느 위치에 삽입을 하냐에 따라 효율성이 달라진다. 배열의 가장 마지막에 원소를 삽입하는 것은 단 한 단계만에 가능하다. 위에서 언급했듯 컴퓨터는 배열이 저장된 위치와 배열의 크기를 알고 있기 때문에, 메모리 주소에 배열의 크기를 더해서 바로 원소를 추가할 수 있다. 그러나 배열의 중간 혹은 맨 처음에 원소를 삽입하고 싶다면 많은 단계가 필요하다.

 

 배열의 중간에 원소를 추가한다면, 원소를 추가할 빈 공간을 만들기 위해 다른 원소들을 뒤로 밀어야 한다. 만약 맨 앞에 새로운 원소를 추가하고 싶다면, 배열 내의 모든 값을 다 한 칸씩 뒤로 밀어야 한다. 따라서, N개의 원소가 있는 배열에서 원소를 추가할 공간을 만드는 단계가 최대 N단계, 그리고 원소를 추가하는 1단계까지 해서 최대 N+1단계가 필요하다. 

 

 

4. 삭제

 

  특정 원소를 삭제하는 것 자체는 한 단계만에 할 수 있지만, 삭제하고 난 뒤의 빈 공간을 없애기 위해 원소들을 한 칸씩 앞으로 옮겨야 한다. 만약 배열의 첫 번째 원소를 삭제하게 되면, 삭제하고 난 뒤 빈 공간을 메꾸기 위해 모든 원소들을 앞으로 한 칸씩 이동시켜야 한다. 따라서 N개의 원소가 있는 배열에서 원소를 삭제한다면 최대 N단계가 필요하다.

 

 

 이렇게 연산에 필요한 단계 수를 구한다면 자료 구조의 성능을 파악할 수 있다. 연산이 몇 단계인지 파악하고 시간 복잡도를 고려해야 프로그램을 효율적으로 동작시킬 수 있을 것이다.

 

---

 

참고 자료

책 '누구나 자료구조와 알고리즘 개정2판' 1장

https://youtu.be/NFETSCJON2M