자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉜다. 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. (연결 방식의 가장 기본이 되는 자료형은 바로 다음 장에서 살펴보게 될 '연결 리스트'다.)

추상 자료형의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 한다. 예를 들어 큐는 배열로 구현하고 스택은 연결 리스트로 구현하는 식이다. (물론 반대의 경우도 충분히 가능하다.)

• 큐: 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다.
• 스택: 제한적으로 접근할 수 있는 나열 구조이다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다.

C언어를 기준으로 (C는 자료구조의 가장 기본적인 형태를 소개하기에 적합한 언어이므로) 배열에 대해 설명해보면, 배열은 크기를 지정하고 해당 크기만큼의 연속되 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기가 고정되어 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가능하다.

ex)
int arr[5] = {2,5,1,6,3};

앞서 배열이란 고정된 크기만큼의 연속된 메모리 할당이라고 말했다. 그러나 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다. 그렇다면 미리 크기를 지정하지 않고 자동으로 조정할 수 있다면 좋지 않을까? 이러한 고민을 해결하고자 크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열이 등장하였다. 파이썬에서는 리스트가 바로 동적 배열 자료형이다.

동적 배열의 원리는 간단하다. 미리 초기값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사하는 식이다.

문제1

세수의 합 - 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.

• 입력
  num = [-1,0,1,2,-1,-4]
• 출력
  [
  [-1,0,1], [-1,-1,2]
  ]

풀이1_브루트 포스

가장 먼저 브루트 포스로 풀이해보자. 배열을 반복하면서 모든 조합을 더해서 일일이 확인해보는 무차별 대입 방식인 브루트 포스로 문제를 해결할 수 있다. 언뜻보면 O(n^2)정도에 풀이가 가능해 보이지만 이 경우에는 타임 아웃이 발생해 풀리지 않을 수 있다.

앞뒤로 같은 값이 있을 경우, 이를 쉽게 처리하기 위해 먼저 다음과 같이 sort()함수를 사용해 정렬부터 한다.

nums.sort()

[-4, -1, -1, 0, 1, 2]
  i   j   k -------->
  i       j  k ----->
  i          j  k -->

위와 같은 방식으로 i,j,k 각각의 포인터가 계속 이동하면서 i+j+k=0을 찾아낸다. 중복된 값이 있을 수 있으므로 이 경우 다음과 같이 continue로 건너뛰도록 처리한다.

if i > 0 and nums[i] == nums[i-1]:
	continue

이제 전체 코드는 다음과 같다.

def three_sum1(nums:List[int]):
    result = []
    nums.sort()
    #브루트 포스 n^3반복
    for i in range (len(nums) - 2):
        #중복된 값 건너뛰기
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, len(nums)-1):
            if j > i + i and nums[j] == nums[j-1]:
                continue
            for k in range(j+1, len(nums)):
                if k > j + 1 and nums[k] == nums[k-1]:
                    continue
                if nums[i] + nums[j] + nums[k] == 0:
                    result.append([nums[i], nums[j], nums[k]])
    return result

틀린 부분은 없지만 예상대로 이 방식으로는 문제가 풀리지 않는다. 타임아웃으로 풀이에 실패한다. 이에 문제가 풀리 수 있도록 O(n^2) 이내로 최적화를 진행해보자.

풀이2_투 포인터의 합

i를 축으로 하고, 중복된 값을 건너뛰게 한 부분은 다음과 같이 앞서 풀이와 동일하다.

if i > 0 and nums[i] == nums[i-1]:
	continue

이제 중복이 아닌 경우 투 포인터로 풀이를 할 수 있다. 앞선 풀이와 차이점은 left, right로 설정하고 간격을 좁혀가며 sum을 계산하는 부분이다. 이 부분을 코드로 구현해보면 다음과 같다.

left, right = i+1, len(nums)-1
while(left < right):
    sum = nums[i] + nums[left] + nums[right]

투 포인터가 간격을 좁혀나가며 합 sum을 계산한다. 이제 다음 코드를 살펴보자. sum이 0보다 작다면 값을 더 키워야 하므로 left를 우측으로 이동하고, 0보다 크다면 값을 더 작게하기 위해 right를 좌측으로 이동한다.

sum=0이면 정답이므로, 이 경우 결과를 리스트 변수 result에 추가한다. 추가한 다음에는 left, right를 한 칸 왼쪽으로 이동하고 다음으로 넘긴다.
얼핏 생각해보면 left 또는 right 둘 중 하나만 이동해야 하는 게 아닌가 싶지만 어차피 sum = 0 인 상황이므로 어느 한쪽만 이동하는 경우는 불가능하다. 나머지 값을 찾으려면 결국 둘 다 모두 움직여야 한다. 앞서 설명한 내용들을 모두 정리하면, 전체 코드는 다음과 같다.

def three_sum2(nums:List[List[int]]):
    result = []
    nums.sort()
    for i in range (len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i+1, len(nums)-1
        while(left < right):
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0:
                left += 1
            elif sum > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
    return result

문제2

자신을 제외한 곱 - 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.
주의: 나눗셈을 하지 않고 O(n)에 풀이하라.

• 입력: [1,2,3,4]
• 출력: [24,12,8,6]

이 문제에는 중요한 제약사항이 있다. '나눗셈을 하지 않고 O(n)에 풀이하라'는 점인데 이 말은 당장 머리속에 떠오르는 풀이법인, 미리 전체 곱셈 값을 구해놓고 각 항목별로 자기 자신을 나눠서 풀이하는 방법은 안된다는 뜻이기도 하다.

그렇다면 해결할 수 있는 방법으로는 자기 자신을 제외하고 왼쪽의 곱셈결과와 오른쪽의 곱셈 결과를 곱하는 것이다.

먼저 왼쪽부터 곱해서 result에 추가한다. 곱셈 결과는 그대로 res 리스트 변수에 담기게 되며, 마지막 값 곱셈을 제외하여 결과는 [1,1,2,6]이 된다. 코드로 구현하면 아래와 같다.

p = 1
for i in range(len(nums)):
	res.append(p)
    p *= nums[i]

이번에는 왼쪽의 곱셈 결과에 오른쪽 마지막 값부터 차례대로 곱해 나간다. p는 1부터 차례대로 점점 커지면서 4,12,24가 되고, 최종적으로 이 값이 왼쪽 곱셈 결과에 곱해져 res변수에는 정답인 [24,12,8,6]을 담게 된다. 전체코드는 다음과 같다.

def product_except_self(nums):
    res = []
    p = 1
    #왼쪽 곱셈
    for i in range(len(nums)):
        res.append(p)
        p *= nums[i]
    p = 1
    #왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
    for i in range(len(nums)-1, -1, -1):
        res[i] *= p
        p *= nums[i]
    return res

문제3

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

• 입력: [0,1,0,2,1,0,1,3,2,1,2,1]
• 출력: 6

가장 높이가 높은 막대를 한번 살펴보자. 이 그림에서 최대 높이는 3이지만 100이어도 관계는 없다. 막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않으면서 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 한다.

이처럼 최대 높이의 막대까지 각각 좌우 기둥 최대 높이 l_max, r_max가 현재 높이와의 차이만큼 물 높이를 더해간다.

volume += l_max - height[left]
volume += r_max - height[right]

이 경우 적어도 낮은 쪽은 항상 그만큼 채워질 것이기 때문에, 좌우 어느 쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터가 가운데로 점점 이동한다. 이렇게 하면 가장 높이가 높은 막대, 즉 '최대' 지점에서 좌우 포인터가 서로 만나게 되며 O(n)에 풀이가 가능하다.

if l_max <= r_max:
	volume += l_max - height[left]
	left += 1
else:
	volume += r_max - height[right]
	right -= 1

전체 코드는 다음과 같다.

def trap(height:List[int]):
    if not height:
        return 0
    volume = 0
    left, right = 0, len(height)-1
    l_max, r_max = height[left], height[right]
    while left < right:
        l_max, r_max = max(l_max, height[left]), max(r_max, height[right])
        if l_max <= r_max:
            volume += l_max - height[left]
            left += 1
        else:
            volume += r_max - height[right]
            right -= 1
    return volume