DSA Interview Prep · 강의

배열 기초와 제자리 연산

Q: “배열 기초와 제자리 연산” 강의는 무료인가요?

네 — “배열 기초와 제자리 연산” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

Q: “배열 기초와 제자리 연산” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

인덱싱과 변경을 복습하고, 경계 초과 오류나 순회 중 리스트 수정처럼 배열 면접에서 자주 발생하는 함정을 살펴봅니다.

배열 기초와 제자리 연산은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

연속 메모리로서의 배열

내부적으로 파이썬 리스트는 동적 배열을 기반으로 합니다. 동적 배열은 요소가 연속된 주소에 저장되는 연속된 메모리 블록입니다. 이 구조 덕분에 인덱스를 사용한 임의 접근을 O(1)에 수행할 수 있습니다. 파이썬은 address = base + index × element_size를 즉시 계산합니다. 가운데에 요소를 삽입하거나 삭제하려면 이후의 모든 요소를 이동해야 하므로 O(n)의 비용이 듭니다. 이러한 비대칭성이 배열 면접에서 대부분의 절충 논의가 나오는 이유입니다.

nums = [10, 20, 30, 40, 50]
# O(1) random access
print(nums[2])       # 30
print(nums[-1])      # 50

# O(1) append (amortised)
nums.append(60)
print(nums)          # [10,20,30,40,50,60]

# O(n) insert at beginning
nums.insert(0, 0)    # shifts all elements right
print(nums)          # [0,10,20,30,40,50,60]

1씩 어긋나는 오류: 배열의 대표적인 버그

1씩 어긋나는 오류는 배열 문제에서 오답을 만드는 가장 흔한 원인입니다. 파이썬은 0부터 인덱싱하므로 마지막으로 유효한 인덱스는 len(arr) - 1입니다. 반복문을 작성할 때는 가장 작은 유효 입력(n=1 또는 n=2)으로 경계 조건을 확인하여 <가 필요한지 <=가 필요한지 결정하세요. 제출하기 전에 구체적인 예시로 경계를 항상 추적해 보세요.

def find_max(nums):
    # Use len(nums)-1 as last index
    max_val = nums[0]              # safe if n >= 1
    for i in range(1, len(nums)):  # start at 1, not 0
        if nums[i] > max_val:
            max_val = nums[i]
    return max_val

print(find_max([3, 1, 4, 1, 5]))  # 5
print(find_max([7]))               # 7  (single element)
# Would crash if we accessed nums[len(nums)]

두 포인터를 사용한 제자리 뒤집기

배열을 제자리에서 뒤집을 때는 양 끝에서 시작하는 두 포인터를 사용하고, 포인터가 만날 때까지 안쪽으로 이동하며 요소를 교환합니다. 추가 공간은 O(1), 시간은 O(n)이 필요합니다. left < right 조건을 엄격하게 사용하면 배열의 길이가 짝수든 홀수든 올바르게 동작합니다. 요소 수가 홀수이면 가운데 요소는 자동으로 제자리에 남습니다.

def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left  += 1
        right -= 1
    # Space: O(1)  Time: O(n)

a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a)  # [5, 4, 3, 2, 1]

b = [1, 2, 3]
reverse_inplace(b)
print(b)  # [3, 2, 1]  middle element unchanged

배열을 제자리에서 회전하기

배열을 k칸 오른쪽으로 회전할 때는 세 구간을 뒤집는 방식으로 제자리에서 처리할 수 있습니다. 먼저 전체 배열을 뒤집고, 처음 k개 요소를 뒤집은 다음, 나머지 n-k개 요소를 뒤집습니다. 이 방법은 시간 O(n), 공간 O(1)을 달성하므로 슬라이싱과 연결로 O(n)의 공간을 사용하는 방법보다 훨씬 효율적입니다. k ≥ n인 경우도 처리할 수 있도록 항상 k를 n으로 나눈 나머지로 줄이세요.

def rotate(nums, k):
    n = len(nums)
    k %= n  # handle k >= n

    def rev(l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1; r -= 1

    rev(0, n-1)    # reverse all
    rev(0, k-1)    # reverse first k
    rev(k, n-1)    # reverse rest

a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a)  # [5, 6, 7, 1, 2, 3, 4]

요소를 제자리에서 제거하기

중복 요소나 대상 값을 제자리에서 제거할 때는 다음으로 유효한 요소를 써야 할 위치를 추적하는 쓰기 포인터를 사용합니다. 읽기 포인터가 앞으로 이동하며 탐색하고, 유효한 요소를 찾으면 쓰기 위치에 복사한 뒤 두 포인터를 모두 이동합니다. 이는 '요소 제거', '정렬된 배열에서 중복 제거', '0 이동'과 같은 LeetCode 문제의 핵심 패턴입니다.

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write  # new length

nums = [3, 2, 2, 3]
new_len = remove_element(nums, 3)
print(nums[:new_len])  # [2, 2]

nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
new_len2 = remove_element(nums2, 2)
print(nums2[:new_len2])  # [0, 1, 3, 0, 4]

0 이동: 읽기-쓰기 포인터

0이 아닌 요소의 순서를 유지하면서 배열의 모든 0을 배열의 끝으로 이동합니다. 읽기-쓰기 포인터 방식은 각 0이 아닌 요소를 쓰기 위치에 배치한 다음 뒷부분을 0으로 채웁니다. 또 다른 방식은 0을 뒤쪽으로 밀어내기 위해 교환하며, 두 번째 채우기 순회 없이도 순서를 유지합니다. 두 방식 모두 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.

def move_zeroes(nums):
    write = 0
    # Move all non-zeroes to front
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
    # Fill rest with zeroes
    while write < len(nums):
        nums[write] = 0
        write += 1

a = [0, 1, 0, 3, 12]
move_zeroes(a)
print(a)  # [1, 3, 12, 0, 0]

제곱한 뒤 제자리에서 정렬하기

정렬된 정수 배열(음수를 포함할 수 있음)이 주어졌을 때, 각 원소의 제곱을 정렬된 순서로 담은 배열을 반환합니다. 단순한 방식은 제곱한 뒤 정렬하므로 O(n log n)입니다. 최적의 투 포인터 방식은 정렬된 입력의 양 끝에서 가장 큰 제곱이 나온다는 사실을 활용합니다. 가장 왼쪽과 오른쪽 원소의 절댓값을 비교하고 결과를 오른쪽에서 왼쪽으로 채우면 O(n) 시간에 해결할 수 있습니다.

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1  # fill from the right
    while left <= right:
        l_sq = nums[left]  ** 2
        r_sq = nums[right] ** 2
        if l_sq > r_sq:
            result[pos] = l_sq
            left += 1
        else:
            result[pos] = r_sq
            right -= 1
        pos -= 1
    return result

print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]

피벗 찾기와 분할

네덜란드 국기 문제는 세 개의 포인터를 사용해 배열을 세 구간(피벗보다 작음, 피벗과 같음, 피벗보다 큼)으로 제자리에서 분할합니다. 이는 퀵 정렬의 핵심 하위 단계이며 LeetCode의 'sort 색상' 문제를 해결하는 방법입니다. low 포인터 앞의 요소가 피벗보다 작고 high 포인터 뒤의 요소가 피벗보다 크다는 불변식을 유지하는 것이 알고리즘을 이끌어 갑니다.

def sort_colors(nums):
    # Dutch national flag: 0s, 1s, 2s
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1  # don't advance mid: new nums[mid] unexamined

a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a)  # [0, 0, 1, 1, 2, 2]

반복 중 배열 요소 수정

반복하는 동안 요소 값은 안전하게 수정할 수 있지만(예: 방문한 요소를 표시하기 위해 -1을 곱할 수 있습니다), for 반복문 안에서 리스트의 길이는 절대 변경하면 안 됩니다. 안전한 인코딩 방법으로, 하나의 정수에 두 값을 임시로 인코딩할 수 있습니다(예: 부호 비트 사용). 이렇게 하면 추가 공간을 할당하지 않고 각 요소에 불리언 값 하나를 더 사용하는 것처럼 처리할 수 있습니다. 이는 '배열에서 사라진 모든 수 찾기'와 같은 문제에 등장합니다.

def find_disappeared(nums):
    # Mark visited by negating the value at the index
    for n in nums:
        idx = abs(n) - 1
        if nums[idx] > 0:
            nums[idx] *= -1  # mark as seen
    # Indices with positive values are missing
    return [i + 1 for i, v in enumerate(nums) if v > 0]

print(find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))
# [5, 6]  -- O(n) time, O(1) extra space

배열 면접 패턴 점검 목록

배열 문제를 코딩하기 전에 다음 생각의 점검 목록을 확인해 보세요:

배열이 정렬되어 있나요? (투 포인터와 이진 탐색을 사용할 수 있습니다)
요소의 범위가 제한되어 있나요(예: 1..n)? (인덱스를 활용한 기법을 사용할 수 있습니다)
제자리 처리가 필요한가요? (읽기-쓰기 포인터 또는 교환을 사용합니다)
모든 쌍이 필요한가요, 아니면 하나만 필요한가요? (중첩 반복문을 사용해도 되는지에 영향을 줍니다)
경계 사례: 빈 배열, 요소 하나, 모든 값이 같은 경우

코드를 작성하기 전에 이 질문에 답하면 디버깅 시간을 크게 줄일 수 있습니다.

def max_profit(prices):
    # Pattern: single scan, track running minimum
    # Time: O(n), Space: O(1)
    if not prices: return 0  # edge case: empty
    min_price = prices[0]
    max_prof  = 0
    for price in prices[1:]:  # start at index 1
        max_prof  = max(max_prof, price - min_price)
        min_price = min(min_price, price)
    return max_prof

print(max_profit([7, 1, 5, 3, 6, 4]))  # 5
print(max_profit([7, 6, 4, 3, 1]))     # 0

카다네 알고리즘: 최대 부분 배열

카다네 알고리즘은 합이 최대인 연속 부분 배열을 O(n) 시간과 O(1) 공간에 찾습니다. 매 단계에서 현재 부분 배열을 확장할지 새로 시작할지 결정합니다: current = max(num, current + num). current + num이 num만 사용하는 경우보다 작다면 현재 부분 배열이 합을 낮추고 있는 것이므로 새로 시작합니다. 전체 최댓값은 진행하는 동안 계속 갱신합니다.

def max_subarray(nums):
    current = global_max = nums[0]
    for n in nums[1:]:
        current    = max(n, current + n)  # extend or restart
        global_max = max(global_max, current)
    return global_max

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6  (subarray [4, -1, 2, 1])
print(max_subarray([-1, -2, -3]))
# -1  (all negative: take the least negative)

빠른 확인

이 레슨에서 배운 자료 구조 및 알고리즘 & 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.

학습 내용 요약

이 레슨에서는 다음을 배웠습니다: 배열은 O(1)의 임의 접근을 제공하지만 중간 삽입과 삭제에는 O(n)이 필요하므로, 이 비대칭성을 알아야 알고리즘을 올바르게 선택할 수 있습니다. 또한 읽기-쓰기 포인터 패턴은 O(1) 공간으로 O(n) 시간에 요소를 제자리에서 제거하거나 값을 이동합니다. 그리고 부호 비트 인코딩과 인덱스를 표시로 활용하는 기법을 사용하면, 그렇지 않으면 보조 배열이 필요한 문제를 O(1) 공간으로 해결할 수 있습니다. 다음에는 누적 합과 누적 합계를 살펴봅니다.

자주 묻는 질문