[자료구조] 배열 (Array)

배열은 인덱스와 값을 대응하여 관리하는 자료구조 입니다. 데이터를 저장할 수 있는 공간은 인덱스로 관리되므로 데이터에 한 번에 접근할 수 있습니다. 그리고 인덱스를 통해 빠른 탐색이 가능하며, 동적으로 크기 조절이 가능합니다. (feat. python)

 

 

1. 2차원 배열 코드 (feat. python)

# 2차원 배열을 비스트로 표현
arr = [[1, 2, 3, 4], [5, 6, 7, 8]]

# arr[2][3]에 저장된 값을 출력
print(arr[2][3])

# arr[2][3]에 저장된 값을 15로 변경
arr[2][3] = 15

 

 

2. 리스트 컴프리헨션

# 크기가 3 * 4인 리스트를 선언하는 예
arr = [[i] * 4 for i in range(3)]  #[[0,0,0,0],[1,1,1,1],[2,2,2,2]]

 

 

3. 배열 연산의 시간 복잡도

배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있습니다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1) 입니다.

맨 뒤에 데이터를 삽입할 경우, 데이터를 맨 뒤에 삽일할 때는 마지막 인덱스에 임의접근을 하여 삽입되므로 시간 복잡도는 O(1) 입니다. 그련데 맨 앞 혹은 중간에 삽입할 경우, 삽입한 데이터 뒤에 있는 데이터 개수만큼 뒤로 미는 연산을 해야 하기 때문에 시간 복잡도는 O(N)이 됩니다.

 

 

4. 배열 사용 시, 고려할 점

할당할 수 있는 메모리 크기를 확인해야 합니다.
배열에 데이터가 너무 많으면 런타임에서 할당에 실패할 수 있습니다.
중간에 데이터 삽입이 많은지 확인해야 합니다.
배열은 선형 자료구조이므로 처음이나 중간에 데이터를 삽입하면 시간 복잡도가 높아집니다.

 

 

5. 배열이 메모리에 저장되는 상태

실제 메모리에 2차원 배열이 저장될 때는 아래와 같이 데이터를 1차원으로 공간에 할당합니다.

 

 

6. 배열 예제

# 두개 뽑아서 더하기
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 solution() 함수를 완성하세요. (중복 제외)

- numbers의 길이는 2이상 100이하 입니다.
- numbers의 모든 수는 0이상 100이하 입니다.
- 입력 : [2, 1, 3, 4, 1]
- 출력 : [2, 3, 4, 5, 6, 7]

 

numbers1 = [2, 1, 3, 4, 1]
numbers2 = [5, 0, 2, 7]

# solution_v1
def solution_v1(numbers):
   numbers_result = []
   for idx1, num1 in enumerate(numbers):
      for idx2, num2 in enumerate(numbers):
         if(idx1 != idx2):
            numbers_result.append(num1 + num2)
   return list(set(sorted(numbers_result)))

# solution_v1
def solution_v2(numbers):
   numbers_result = []
   for i in range(len(numbers)):
      for j in range(i+1, len(numbers)):
         numbers_result.append(numbers[i] + numbers[j])
   return sorted(set(numbers_result))
   
# 결과 확인
def measure_time(func, arr):
   start_time = time.time()
   result = func(arr)
   end_time = time.time()
   return end_time - start_time, result

result_time, result = measure_time(solution_v2, numbers1)
print(result_time, result)

 

solution_v1 보다 solution v2가 성능이 더 좋습니다.

왜 좋은지에 대해 한 번 생각해보면 좋을 것 같고, 불필요한 순회를 줄였다고 생각해주시면 좋을 것 같습니다!