Junhyuk Yu

I will be an amazing person.

해당 내용은 ‘파이썬 알고리즘 인터뷰’ 책의 일부를 발췌하여 정리한 내용입니다.

배열

배열은 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.

자료구조는 크게 메모리 공간 기반의 연속방식과 포인터 기반의 연결방식으로 나뉘며, 그 중 배열은 연속 방식의 가장 기본이 되는 자료형이다. 고정된 크기만큼의 연속된 메모리 할당이다.

그런데 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많으며, 때로는 메모리 할당 영역이 너무 작거나 너무 클 수 있는 경우가 발생한다. 그럴 경우를 대비하여 자동으로 리사이징 하는 배열인 동적 배열이 등장했다. 파이썬에서는 리스트가 바로 동적 배열 자료형이다.

동작 배열의 원리는 초기값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 늘려주고 모두 복사하는 식이다. 대게는 더블링(Doubling)이라 하여 2배씩 늘려주게 되는 형식이다.

동적 배열은 정적 배열과 달리 크기를 지정할 필요가 없어 매우 편리하게 활용할 수 있으며, 조회 또한 기존의 배열과 동일하게 O(1)에 가능하다. 그러나, 더블링이 필요할 만큼 공간이 차게 되면 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사해야 하므로 O(n) 비용이 발생한다.

두 수의 합

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

  • 나의 풀이 : 배열을 2번 반복하면서 모든 조합을 더해 일일히 확인해보는 무차별 대입 방식인 브루트 포스
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        # nums의 길이에 해당되는 범위를 for문으로 사용
        for i in range(len(nums)):
            # i + 1부터 nums의 길이에 해당되는 범위를 for문으로 사용
            for j in range(i + 1, len(nums)):
                # i와 j 인덱싱의 숫자값 더한 값이 target과 같을 경우 해당 값 반환
                if nums[i] + nums[j] == target:
                    return [i, j]
  • 딕셔너리와 target - n을 이용한 풀이
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 딕셔너리 선언
        nums_map = {}

        # 인덱스와 벨류값 뽑아내기
        for i, num in enumerate(nums):
            # target - num 의 값이 nums_map에 존재할 경우
            if target - num in nums_map:
                # nums_map[key] = Value이므로, 매핑된 인덱스 값을 반환
                return [nums_map[target - num], i]
            # key 값은 할당된 숫자, Value는 인덱싱 숫자로 딕셔너리 만들기
            nums_map[num] = i

빗물 트래핑

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

  • 투 포인터를 최대로 이동
class Solution:
    def trap(self, height: List[int]) -> int:
        # 예외 케이스 작성
        if not height:
            return 0

        # 초기값 설정
        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]

        while left<right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
            # 더 높은 쪽을 향해 투 포인터 이동
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1

            else:
                volume += right_max - height[right]
                right -= 1
        
        return volume
  • 스택 쌓기
class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        volume = 0

        for i in range(len(height)):
            # 변곡점을 만나는 경우
            while stack and height[i] > height[stack[-1]]:
                # 스택에서 꺼낸다
                top = stack.pop()

                if not len(stack):
                    break

                # 이전과의 차이만큼 물 높이 처리
                distance = i - stack[-1] - 1
                waters = min(height[i], height[stack[-1]]) - height[top]

                volume += distance * waters

            stack.append(i)
        return volume

세 수의 합

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

  • 나의 풀이(브루트 포스)
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 정답값을 받을 리스트 선언
        array = []
        # 편의상을 위해 정렬 추가
        nums.sort()

        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 + 1 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 i != j and i != k and j !=k and nums[i] + nums[j] + nums[k] == 0:
                        array.append([nums[i], nums[j], nums[k]])

        return array

위 풀이로 간단한 수는 통과가 되지만 많은 수의 테스트 케이스의 경우 타임아웃이 된다. 해당 브루트 포스의 시간 복잡도는 O(n^3)이 되므로 비효율적이다.

  • 투 포인터로 합 계산
class Solution:
    def threeSum(self, nums: List[int]) -> 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

🤔 투 포인터란?

여러 가지 방식이 있지만, 대개 시작점과 끝점을 기준으로 하는 문제 풀이 전략을 뜻한다. 일반적으로 배열이 정렬되어 있는 문제 풀이에 유용하다. ‘세 수의 합’ 문제에서 투 포인터 풀이를 통해서 기존 O(n^3) 풀이를 O(n^2)으로 풀이하는 해법을 제시하였다. 사실 투 포인터에 대해서는 아직까지 명확하게 정의된 것이 없다. 투 포인터는 알고리즘 풀이와 관련해 등증한 실질적인 풀이기법으로, 일반적인 알고리즘 교과서에는 등장하지 않기 때문이다.

배열 파티션 I

n 개의 페어를 이용한 min(a, b)의 합을 만들 수 있는 가장 큰 수를 출력하라.

Input: nums = [1,4,3,2]
Output: 4
설명 : 
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
n은 2가 되며, 최대 합은 4이다.

풀이

  • 나의 풀이
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        # 숫자 정렬
        nums.sort()
        # 최소값을 받을 리스트 선언
        answer = []
        # 포인터 설정
        no_zero, no_one = 0, 1

        for i in range(len(nums)):
            # 예외 처리 구문을 넣어 리스트 밖의 범위가 나올 경우 무시하고 진행
            try:
                answer.append(min(nums[no_zero], nums[no_one]))
            except IndexError:
                continue

            no_zero += 2
            no_one += 2
        # 최소값 받은 리스트들의 합
        return sum(answer)
  • 오름차순 풀이
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        pair = []
        nums.sort()

        for n in nums:
            # 앞에서부터 오름차순으로 페어를 만들어서 합 계산
            pair.append(n)
            if len(pair) == 2:
                sum += min(pair)
                pair = []

        return sum
  • 짝수 번째 값 계산

정렬된 상태에서는 짝수 번째에 항상 작은 값이 위치하기 때문에 이를 이용해서 풀이를 진행한다.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        nums.sort()

        for i, n in enumerate(nums):
            # 짝수 번째 값의 합 계산
            if i % 2 == 0:
                sum += n

        return sum
  • 파이썬 다운 방식

슬라이싱을 활용하변 한줄로도 풀이가 가능하다.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])

자신을 제외한 배열의 곱

배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라. 단, 나눗셈은 하지 않도록 주의한다.

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

풀이

  • 왼쪽 곰셈 결과에 오른쪽 값을 차례대로 곱셈
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

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

주식을 사고 팔기 가장 좋은 시점

한 번의 거래로 낼 수 있는 최대 이익을 산출하라.

Input: prices = [7,1,5,3,6,4]
Output: 5
설명 : 1일 때 사서 6에 팔면 5의 이익을 얻는다

풀이

  • 브루트 포스 풀이
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0

        for i, price in enumerate(prices):
            for j in range(i, len(prices)):
                max_price = max(prices[j] - price, max_price)

        return max_price

하지만 위 풀이는 안타깝게 타임 아웃으로 풀 수 없다.

  • 저점과 현재 값과의 차이 계산
class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        profit = 0
        min_price = sys.maxsize

        # 최소값과 최댓값을 계속 갱신
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)

        return profit

🤔 최댓값과 최솟값

최댓값과 최솟값의 초기값을 지정하는 방법이 있다. 초기값들을 설정하려면 최대값의 경우 시스템에서 가장 낮은 값을, 최소값은 시스템에서 가장 높은 값을 지정해줘야 바로 교체 될 수 있다. 앞선 문제에서 활용한 sys 이외에도 여러 방법이 존재한다.

# sys
mx = -sys.maxsize
mn = sys.maxsize

# float
mx = float('-inf')
mn = float('inf')

You may also enjoy