배열

자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉜다. 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. 연결 방식의 가장 기본이 되는 자료형은 연결 리스트이다. 추상 자료형의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 한다. 예를 들어 스택은 연결 리스트로 구현하고, 큐는 배열로 구현하는 식이다. 물론 반대의 경우도 가능하다.

배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당 받는 작업을 수행하는 자료형이다. 크기가 고정되어 있고 한번 생성한 배열은 크기를 변경하는 것이 불가능하다. C언어 기준으로 int형 배열의 경우에는 4바이트의 간격으로 배열의 원소들이 연속적으로 주소를 할당하고 있다.

배열은 연속적으로 존재하기 때문에 어느 위치에나 O(1)에 조회가 가능하다. 각 원소들의 크기와 원하는 인덱스를 알고 있다면 주소값을 계산하여 바로 접근이 가능하다.

동적 배열

앞서 배열은 고정된 크기만큼의 연속된 메모리 할당이라고 설명하였다. 그러나 실제 데이터는 전체 크기를 가늠하기 힘든 경우가 많다. 너무 적은 영역을 할당하여 모자라거나, 너무 많은 영역을 할당하여 메모리 낭비를 하기도 한다. 이러한 문제를 해결하기 위해 크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열이 등장하였다.

파이썬에서는 리스트가 바로 동적 배열 자료형이다. 대부분의 동적 프로그래밍 언어들은 정적 배열 자체가 없다. 파이썬 역시 정적 배열은 따로 제공하지 않고 동적 배열만 제공한다.

동적배열의 원리는 미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 늘려주고 모두 복사하는 방식이다. 이를 더블링이라고 부르는데, 그 이유는 크기를 2배씩 늘리기 때문이다. 언어마다 더블링의 비율은 조금씩 다르다.

파이썬의 더블링은 0, 4, 8, 16, 25, 35, 46, 58, ...의 비율로 진행된다. 초반에는 2배씩 증가하지만 전체적으로는 약 1.125배의 증가이다.

동적 배열은 정적 배열과 달리 크기를 지정할 필요가 없어 매우 편리하게 활용할 수 있고, 조회 또한 기존의 배열과 동일하게 O(1)에 가능하다. 그러나 더블링이 필요할 만큼 공간이 차게 되면 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업이 필요하기 때문에 O(n)의 비용이 발생한다. 이는 최악의 경우로 분할 상환 분석에 따른 입력 시간은 O(1)이다.

LeetCode 1.Two Sum

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.

Solution 1 브루트 포스로 계산

이 문제는 매우 쉽지만 최적화 할 수 있는 방법이 여러가지 숨어있다. 브루트 포스는 배열을 2번 반복하면서 모든 조합을 더해서 일일이 확인해보는 무차별 대입 방법이다. 이렇게 모든 경우를 모두 비교하며 정답을 찾으면 정답을 반환한다. 이는 비효율적이지만 구현이 쉽다. 시간 복잡도는 O(n^2)이다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j]==target:
                    return [i, j]

4044ms나 소요된 것을 확인할 수 있다.

Solution 2 in을 이용한 탐색

모든 조합을 비교하지 않고 타겟에서 첫번째 값을 뺀 값이 존재하는지 탐색하는 문제로 변경하여 생각해보고 풀어보았다. in의 시간 복잡도는 O(n)이기 때문에 Solution 1과 마찬가지로 시간 복잡도는 O(n^2)가 나오지만 in 연산이 훨씬 더 가볍고 빠르기 때문에 시간은 더 적게 소요된다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i,n in enumerate(nums):
            complement = target - n
            if complement in nums[i+1:]:
                return [nums.index(n), nums[i+1:].index(complement) + (i + 1)]

885ms로 Solution 1의 4044ms보다 훨씬 더 빠르게 소요된 것을 알 수 있다.

Solution 3 첫번째 수를 뺀 결과 키 조회

이번에는 시간 복잡도를 개선하여 속도를 개선시켜볼 것이다. 비교나 탐색 대신 한 번에 정답을 찾을 수 있는 방법에 대해 생각해보았다. 타겟에서 첫번째 수를 빼면 두번째 수를 바로 알아낼 수 있다. 두번째 수를 키로 하고 기존의 인덱스는 값으로 바꿔 딕셔너리로 저장한다면 나중에 두번째 수를 키로 조회해 정답을 즉시 찾아낼 수 있다. 다음으로 타겟에서 첫번째 수를 뺀 결과를 키로 조회해보면 두번째 수의 인덱스를 즉시 조회할 수 있다. 딕셔너리는 해시 테이블로 구현되어 있기 때문에 조회는 O(1)에 가능하다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        for i, num in enumerate(nums):
            nums_map[num] = i
        for i, num in enumerate(nums):
            if target-num in nums_map and i!=nums_map[target-num]:
                return [i, nums_map[target-num]]

시간 복잡도가 O(n)으로 개선됨에 따라 60ms 밖에 걸리지 않는 것을 확인할 수 있다.

Solution 4 조회 구조 개선

딕셔너리 저장과 조회를 2개의 for문으로 각각 처리했던 방식을 좀 더 개선하여 이번에는 하나의 for문으로 합쳐 처리해본다. 전체를 모두 저장할 필요 없이 정답을 찾게 되면 함수를 종료한다. 그러나 두번째 값을 찾기 위해 매번 비교해야 하므로 Solution 3에 비해 성능의 큰 이점이 있지는 않다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        for i, num in enumerate(nums):
            if target-num in nums_map:
                return [nums_map[target-num], i]
            nums_map[num]=i

Solution 5 투 포인터 이용

이 문제를 투 포인터로 해결할 수 있는지 확인해보았다. 우선 왼쪽 포인터와 오른쪽 포인터의 합이 타겟보다 크다면 오른쪽 포인터를 왼쪽으로 이동시키고, 작다면 왼쪽 포인터를 오른쪽으로 이동시키면서 값을 조정하는 방식이다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums)-1
        while not left == right:
            if nums[left]+nums[right] < target:
                left+=1
            elif nums[left]+nums[right] > target:
                right-=1
            else:
                return [left, right]

이렇게 투 포인터로 코드를 작성하니 이해하기도 쉽고 코드도 간결하다. 시간복잡도도 O(n)이고 불필요한 연산 또한 없기 때문에 성능이 매우 좋을 것으로 예상된다. 그러나 이 문제는 nums가 정렬된 상태가 아니기 때문에 위와 같은 코드로 해결할 수 없다. 투 포인터를 사용하기 위해서는 정렬을 해야 하는데 정렬을 할 경우 인덱스가 모두 섞여버리기 때문에 이 문제에서 원하는 답을 얻을 수 없게 된다.

Result

브루트 포스로 계산		4044ms
in을 이용한 탐색		885ms
첫번째 수를 뺀 결과 키 조회	60ms
조회 구조 개선		52ms
투 포인터			풀이 불가

이번 문제는 파이썬으로 아무 문제가 없었지만 어떤 문제들은 언어 별로 타입아웃이 발생하는 경우가 있다. 예를 들면 동일한 알고리즘을 사용했음에도 C++이나 고는 통과되는데 파이썬은 타임 아웃이 발생하는 경우이다. 이럴 경우에는 상황을 잘 판단하여 다른 언어로 다시 작성해야 한다.

To be continue ...