자료구조 - 배열

배열

가장 기본적인 자료 구조

nums = [1, 2, 3, 4, 5, 6]

 

배열에서 주의할 점 : 첫 번째 원소의 인덱스는 [1]이 아니라 [0]이라는 것.

배열의 공간복잡도 = O(N). 배열의 크기만큼 차지하기 때문에.

 

배열 인덱싱

nums[2]
# nums의 3번째 원소를 뜻함

nums = [1, 2, 3, 4, 5]
nums[2:5]    # [2, 3, 4]
# nums의 인덱스 2부터 (5-1)인 4까지. 2~4까지 해당하는 부분배열

nums = [1, 2, 3, 4, 5]
nums[len(nums)-1]     # 인덱스가 [4]인 마지막 원소 5
# nums의 마지막 원소

nums[-1]
# 이것 또한 배열의 마지막 원소

 

배열의 Big-O 시간복잡도

1. 인덱스를 알 때 : O(1)

어떤 배열 nums에서 그 인덱스를 알고, 인덱스에 해당하는 원소를 꺼내는 동작의 시간복잡도는 O(1). 

nums = [1, 2, 3, 4, 5, 6]
nums[2]    # 3

# Big-O 시간복잡도 = O(1)

이렇게 nums[i]를 호출하는 동작의 시간복잡도는 O(1)로, nums의 크기에 상관없이 항상 상수값의 Big-O를 가짐.

 

2. 인덱스를 모를 때 = 하나씩 검사 : O(N)

어떤 배열 nums에서 인덱스를 몰라서 그 원소를 직접 찾아서 꺼내려면, nums의 원소를 하나씩 다 검사를 해서 그 원소가 있는지를 확인해야 되잖아. 물론, 배열을 처음부터 찾아보다가 운이 너무 좋아서 빨리 찾아지는 경우도 있겠지만, 그건 Big-O 시간복잡도에는 영향을 미치지 않음. 그 정도는 가장 큰 차수의 계수정도로 해당되는 거기때문에 걍 무시.

nums = [1, 2, 3, 4, 5, 6]
if 5 in nums:    # nums 안에 5가 있는지 하나씩 꺼내서 확인해

# Big-O 시간복잡도 = O(N)

 

3. 배열을 전부 순회할 때 : O(N)

2번과 마찬가지로, 하나씩 다 꺼내는 거니까 시간복잡도는 O(N).

nums = [1, 2, 3, 4, 5, 6]
for num in nums:

# Big-O 시간복잡도 = O(N)

 

4. 자료 끝에 원소를 추가할 때 : O(1)

nums의 크기가 크든 작든, 맨 뒤의 인덱스만 알면 바로 추가할 수 있기 때문.

nums = [1, 2, 3, 4, 5, 6]
nums.append(7)

# Big-O 시간복잡도 = O(1)

 

5. 자료의 중간에 원소를 추가할 때 : O(N)

insert(인덱스, 삽입할 데이터) 함수로 해당하는 인덱스에 가서 원소를 삽입하고, 그 뒤부터 원래 자리에 있던 원소들을 뒤로 미뤄줘야함. 이 미뤄주는 행위 때문에 배열의 크기인 N에 비례해서 시간복잡도가 O(N)이 됨.

nums = [1, 2, 3, 4, 5, 6]
nums.insert(3, 9)

# Big-O 시간복잡도 = O(N)

 

 

문자열

배열의 한 종류. 문자들의 배열.

tempString = "abcdef"    # 배열의 형태로 바꿔보면 -> [a, b, c, d, e, f] 
for ch in tempString:    # 인덱스도 마찬가지로 ->     0  1  2  3  4  5

 

2차원 배열 

행렬과 비슷. 인덱싱의 원리도 배열의 원리를 그대로 따라감.

nums = [[1, 2, 3, 4, 5]\    
       [6, 7, 8, 9, 10]\
       [11, 12, 13, 14, 15]\
       [16, 17, 18, 19, 20]]
       
"""
한줄한줄 큰 덩어리의 인덱스를 i라고 하고
하나하나 작은 원소들의 인덱스를 j라고 해
그래서 원소 하나의 인덱스는 nums[i][j]로 표기

ex. 5라는 원소는 nums[0][4]
    첫번째 줄이기 때문에 index 0 -> i = 0
    맨끝에 있어서 index 4 -> j = 4