[자료구조] 배열 (array)

자료구조는 크게

• 메모리 공간 기반의 연속 방식
• 포인터 기반의 연결 방식

으로 나뉜다.

 

오늘 다루는 배열은 "메모리 공간 기반의 연속 방식"에 속하는 자료구조이다.

다음 시간에 다루는 연결리스크(linked list)는 "포인터 기반의 연결 방식"에 속하는 자료구조이다.

 

배열이란 무엇인가?

배열의 정의 : 같은 타입의 변수들이 연속된 메모리 공간에 위치하고 있는 자료구조

 

배열의 장점

• 검색 성능이 좋다 ( 어느 위치이든 O(1)으로 조회 가능하다 )
• 인덱스를 이용하여 무작위 접근 가능하다 (순차접근 하지 않아도 괜찮다)
• 순차접근을 하더라도 linked list에 비해 속도 빠르다.

배열의 단점

• 자료의 삽입과 삭제가 비효율적이다.
  • 삽입하는 경우, 삽입하려는 위치 이후의 모든 원소를 복사/붙여넣기 해야한다.
  • 삭제하는 경우, 삭제한 위치 이후의 모든 원소를 앞으로 당겨야 한다.
• 크기가 고정되어 있다.

 

C언어에서의 배열은 고정된 크기의 연속된 메모리 공간을 할당한다.

하지만 실제 데이터에서는 전체 사용량을 미리 가늠하기가 쉽지 않다.

필요한 메모리공간보다 작은 크기의 공간을 할당한다면, 나중에 새로운 크기의 메모리를 재할당하여 복사하여야 하는 비효율성이

필요한 메모리공간보다 큰 크기의 공간을 할당한다면, 사용하지 않는 공간이 낭비된다는 문제가 있다.

이러한 문제점을 해결하고자 나오게 된 것이 "동적 배열"이다.

 

동적 배열은 미리 초깃값을 작게 잡아 배열을 생성하고,

데이터가 추가되면서 다 채워지려고 하면 늘려주고 이전의 데이터를 넓어진 공간으로 복사하는 방식이다.

대개는 더블링이라 하여, 배열의 크기를 늘려줄 때 이전 크기의 2배로 늘려주게 된다. (반드시 그러한 것은 아니다)

 

이러한 동적 배열은 정적 배열과 달리 크기를 지정할 필요가 없어 매우 편리하게 사용할 수 있고, 조회 성능 역시 O(1)이다.

하지만 중간중간 더 큰 배열로 옮겨주는 과정에서 O(n)의 비용이 발생한다.

최악의 경우 데이터 삽입에 대한 비용을 O(n)이지만, amortized insertion time에 따르면 여전히 삽입 성능은 O(1)이다.

 

 

---

배열에서 two-pointer를 활용한 문제가 다수 존재하였다 + 인덱스를 활용하는 문제

two-pointer 문제풀이는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략이다.

범위를 좁혀 나가기 위해서는 일반적으로 배열이 정렬되어 있을 때 더 유용하다.

 

# https://leetcode.com/problems/3sum/discuss/404887/Python3-solution-extend-from-sum-2
# two pointer 이용한 풀이 (추천)
def solution_2(nums: List[int]) -> List[List[int]]:
    nums.sort() # 정렬
    result = set()

    for i in range(len(nums)-2):
        left_ptr = i+1
        right_ptr = len(nums)-1
        while left_ptr < right_ptr:
            sum_val = nums[i]+nums[left_ptr]+nums[right_ptr]
            if sum_val == 0:
                result.add((nums[i], nums[left_ptr], nums[right_ptr]))
                left_ptr += 1
                right_ptr -= 1
            elif sum_val < 0:
                left_ptr += 1
            else:
                right_ptr -= 1
    return list(result)