다이나믹 프로그래밍

• 다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다.

• 다이나믹 프로그래밍은 중복된 하위 문제들의 결과를 저장해뒀다가 풀이한다. 따라서 중복되지 않은 문제들은 다이나믹 프로그래밍으로 풀지 않는다.

• 다익스트라 알고리즘은 다이나믹 프로그래밍과 그리디 알고리즘 둘 다 해당하는 경우인데, BFS시 항상 최단 경로를 찾고 탐욕 선택 속성을 갖는 그리디 알고리즘이면서, 이미 계산한 경로는 저장해두었다가 활용하며 중복된 하위 문제들을 푸는 다이나믹 알고리즘이기도 하다.

최적 부분 구조

• 서울에서 부산까지 가는 최단 경로를 찾는다고 할때, 서울에서 대구까지 가는 최단 경로와 대구에서 부산까지 가는 최단 경로를 선택하면 풀 수 있다.
• 이처럼 문제의 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 구조를 최적 부분 구조라고 한다.

다이나믹 프로그래밍 방법론

• 방법론은 크게 상향식과 하향식으로 나뉜다. 일반적으로 상향식을 타뷸레이션, 하향식을 메모이제이션이라고 구분해 부르기도 한다.
• 상향식: 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다. 타뷸레이션이라고 부르며 일반적으로 이 방식만을 다이나믹 프로그래밍으로 지칭하기도 한다.
• 하향식: 하위 문제에 대한 정답을 계산했는지 확인하며 문제를 자연스러운 방식으로 풀이한다. 이 방식을 메모이제이션이라고 한다.

피보나치 수열의 상향식과 하향식

• 상향식

def fib(n):
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

• 하향식

def fib(n):
    if n <= 1:
        return n
    if dp[n]:
        return dp[n]
    dp[n] = fib(n -1) + fib(n - 2)
    return dp[n]

피보나치 수열

• 피보나치 수를 구하라.
• 피보나치 수열을 구하는 가장 기본적인 풀이 알고리즘의 수도코드는 다음과 같다.

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

풀이 1. 메모이제이션

• 앞서 설명에서 다이나믹 프로그래밍의 하향식 풀이로 정리한 것이 메모이제이션 풀이이다. 한번 계산한 수는 더이상 계산하지 않으므로 n이 5일 때, fib(2)와 fib(3)은 한번만 계산하게 되어 매우 효율적이다.

class solution:
    dp = collections.defaultdict(int)

    def fib(n):
        if n <= 1:
            return n

        if self.dp[n]:
            return self.dp[n]
        self.dp[n] = self.fib(n - 1) + self.fib(n - 2)
        return self.dp[n]

풀이 2. 타뷸레이션

class solution():
    dp = collections.defaultdict(int)

    def fib(n):
        self.dp[1] = 1

        for i in range(2, n + 1):
            self.dp[i] = self.dp[i - 1] + self.dp[i - 2]
        return self.dp[n]

풀이 3. 두 변수만 사용해서 풀이

• 공간 복잡도를 O(n)에서 O(1)로 줄일 수 있고 시간 복잡도는 동일한 O(n)이다.

def fib(n):
    x, y = 0, 1
    for i in range(0, n):
        x, y = y, x + y
    return x

0 -1 배낭문제

• 그리디 알고리즘으로 풀었던 배낭문제를 짐을 쪼갤 수 없는 0 - 1 배낭문제로 변경하면 그리디 알고리즘으로 풀 수 없어진다. 이 경우 모든 경우의 수를 계산해야 하며, 이렇게 모든 경우의 수를 계산하는 문제에서 다이나믹 프로그래밍은 위력을 발휘한다.

def zero_one_knapsack(cargo):
    capacity = 15
    pack = []

    for i in range(len(cargo) + 1):
        pack.append([])
        for c in range(capacity + 1):
            if i == 0 or c == 0:
                pack[i].append(0)
            elif cargo[i - 1][1] == c:
                pack[i].append(
                    max(
                        cargo[i - 1][0] + pack[i - 1][c - cargo[i - 1][1]], pack[i - 1][c]
                    ))
            else:
                pakc[i].append(pack[i - 1][c])

최대 서브배열

• 합이 최대가 되는 연속 서브 배열을 찾아 합을 리턴하라

예제

• 입력: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
• 출력: 6

풀이 1. 메모이제이션

• 앞에서부터 계속 값을 계산하면서 누적 합을 계산한다. 이전 값을 계속 더해나가되 0이 이하가 되면 버린다. 어차피 최댓값을 찾는데 0 이하인 값은 굳이 서브 배열에 포함할 이유가 없기 때문이다.

def solution(nums):
    for i in range(1, len(nums)):
        nums[i] += num[i - 1] if nums[i - 1] > 0 else 0
    return max(nums)

풀이 2. 카데인 알고리즘

• 이전 풀이에서는 매번 계산해서 넣기만 하고 마지막에 max()를 전체 계산해서 가져오게 했지만 카데인 알고리즘은 매번 best_sum을 계산한다.

def solution(nums):
    best_sum = -sys.maxsize
    current_sum = 0
    for num in nums:
        current_sum = max(num, current_sum + num)
        best_sum = max(best_sum, current_sum)

    return best_sum

계단 오르기

• 당신은 계단을 오르고 있다. 정상에 도달하기 위해 n계단을 올라야 한다. 매번 각각 1계단 또는 2계단씩 오를 수 있다면 정상에 도달하기 위한 방법은 몇 가지 경로가 되는지 계산하라.

예제

• 입력: 3
• 출력: 3

풀이 1. 재귀 구조 브루트 포스

• n개의 계단을 오르는 방법의 수는 (n - 1)계단을 오르고 1 계단을 오르는 방법의 수와 (n - 2)계단을 오르고 2 계단을 오르는 방법의 수를 더한 것과 같으므로 피보나치 수와 비슷한 방법으로 풀이할 수 있다.
• 그러나 이 방법은 타임아웃으로 풀리지 않는다.

def solution(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return solution(n - 1) + solution(n - 2)

풀이 2. 메모이제이션

class solution:
    dp = collections.defaultdict(int)

    def climbStairs(n):
        if n <= 2:
            return n

        if self.dp[n]:
            return self.dp[n]

        self.dp[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
        return self.dp[n]

집도둑

• 당신은 전문 털이범이다. 어느 집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에 바로 옆집은 훔칠 수 없고 한 칸 이상 떨어진 집만 가능하다. 각 집에는 훔칠 수 있는 돈의 액수가 입력값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라.

예제

• 입력: [1, 2, 3, 1]
• 출력: 4

풀이 1. 재귀구조 브루트포스

• 바로 옆집은 훔칠 수 없으니 현재 집과 옆집 숫자 중의 최댓값을 구하고, 한 집 건넛집까지의 최댓값과 현재 집의 숫자값과의 합을 구해서 두 수 중 더 높은 값이 정답이 된다.

def rob(nums):
    def _rob(int):
        if i < 0:
            return 0
        return max(_rob(i - 1), _rob(i - 2) + nums[i])
    return _rob(len(nums) - 1)

풀이 2. 타뷸레이션

• 알고리즘은 동일하지만 이미 계산한 값은 dp에 저장하고 두번 이상 계산하지 않는다.

def rob(nums):
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)

    dp = collections.OrderedDict()
    dp[0], dp[1] = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i -1], dp[i - 2] + nums[i])

    return dp.popitem()[1]

분할 정복

• 분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다.
• 분할 정복은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다.

분할정복 수도 코드

function F(x):
    if F(x)가 간단 then:
        return F(x)를 계산한 값

    else:
        x를 x1, x2로 분할
        F(x1)과 F(x2)를 호출
        return F(x1), F(x2)로 F(x)를 구한 값

과반수 엘리먼트

• 과반수를 차지하는 절반을 초과하는 엘리먼트를 출력하라

예제

• 입력: [3, 2, 3]
• 출력: 3

풀이 1. 다이나믹 프로그래밍

• 한 번 카운트를 계산한 값은 저장해서 재활용한다.

def solution(nums):
    counts = collections.defaultdict(int)
    for num in nums:
        if counts[num] == 0:
            counts[num] = nums.count(num)

        if counts[num] > len(nums) // 2:
            return num

풀이 2. 분할 정복

• 쪼갠 후 과반수 후보군에 해당하는 엘리먼트만 리턴하면서 계속 위로 올려주면 최종적으로 정답이 남게 된다.

def solution(nums):
    if not nums:
        return None
    if len(nums) == 1:
        return nums[0]

    half = len(nums) // 2
    a = solution(nums[:half])
    a = solution(nums[half:])

    return [b, a][nums.count(a) > half]

풀이 3. 파이썬다운 방식

• 정렬하여 가운데를 지정하면 반드시 과반수 이상인 엘리먼트일 것이다.

def solution(nums):
    return sorted(nums)[len(nums) // 2]

괄호를 삽입하는 여러가지 방법

• 숫자와 연산자를 입력받아 가능한 모든 조합의 결과를 출력하라

예제

• 입력: "2-1-1"
• 출력: [0, 2]

풀이 1. 분할 정복을 이용한 다양한 조합

• *, -, + 연산자가 등장할 때 좌/우 분할을 하고 각각 계산 결과를 리턴한다.
• 연산자를 기준으로 재귀로 left, right로 계속 분할하고 분할된 값은 compute() 함수로 계산한 결과를 extend()로 확장한다.

def solution(input):
    def compute(left, right, op):
        result = []

        for l in left:
            for r in right:
                result.append(eval(str(l) + op + str(r)))
        return result

    if input.isdigit():
        return [int(input)]

    results = []
    for index, value in enumerate(input):
        if value in '-+*':
            left = solution(input[:index])
            right = solution(input[input + 1:])

            results.extend(compute(left, right, value))

    return results

그리디 알고리즘

• 그리디 알고리즘으 글로벌 최적을 찾기 위해 각 단계에서 로컬 취적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다.

• 그리디 알고리즘이 잘 작동하는 문제들은 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들이다.

• 탐욕 선택 속성이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말한다.

• 최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다.

• 이 두가지 조건을 만족하지 않더라도 그리디 알고리즘은 정답을 근사하게 찾는 용도로 활용할 수 있으며 대부분의 경우 계산 속도가 빠르므로 매우 실용적이다.

• 다이나믹 프로그래밍이 하위 문제에 대한 최적의 솔루션을 찾은 다음 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택을 한다면 이에 반해 그리디 알고리즘은 각 단계마다 로컬 최적해를 찾는 문제다.

배낭 문제

• 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고 각각 짐의 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제다.
• 배낭 문제는 짐을 쪼갤 수 있는 분할 가능 배낭 문제(그리디 알고리즘으로 해결)과 짐을 쪼갤 수 없는 경우인 0-1 배낭문제(다이나믹 프로그래밍으로 해결)로 나뉜다.
• 분할 가능 배낭 문제의 경우 단가가 높은 짐부터 차례대로 채워나가면 된다. 짐을 (가격, 무게)의 튜플 리스트로 정의하고 단가를 계산해 역순으로 정렬한다. 그 후 단가 순으로 그리디 알고리즘으로 계산하면 된다.

def solution(cargo):
    capacity = 15
    pack = []
    # 단가 계산 역순 정렬
    for c in cargo:
        pack.append((c[0] / c[1], c[0], c[1]))
    pack.sort(reverse=True)

    # 단가 순 그리디 계산
    total_value = 0
    for p in pack:
        if capacity - p[2] >= 0:
            capacity -= p[2]
            total_value += p[1]
        else:
            fraction = capacity / p[2]
            total_value += p[1] * fraction
            break

    return total_value

동전 바꾸기 문제

• 동전의 액면이 10원, 50원, 100원처럼 증가하면서 이전 액면의 배수 이상이 되면 그리디 알고리즘으로 풀 수 있다.
• 그러나 만약 다른 나라에 갔더니 80원짜리 동전이 더 있다고 하면 그리디하게 풀 수 없다. 160원을 거슬러줄 때 80원짜리 2개가 정답이지만 그리디 알고리즘은 100원부터 선택하게 될 것이기 때문이다.

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

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

예제

• 입력: [7, 1, 5, 3, 6, 4]
• 출력: 7
• 설명: 1일 때 사서 5일 때 팔아 4의 이익을 얻고, 3일 때 사서 6일 때 팔아 3의 이익을 얻는다. 둘을 합하면 7이 된다.

풀이 1. 그리디 알고리즘

• 내리기 전에 팔고 오르기 전에 사는 식으로 몇번이든 사고팔고를 반복한다.
• 다음번 값이 현재보다 오르는 경우에 항상 이익을 취하는 형태로 매번 단계마다 이익을 취하는 탐욕 구조로 구현할 수 있다.

def solution(prices):
    result = 0
    # 값이 오르는 경우 매번 그리디 계산
    for i in range(len(prices) - 1):
        if prices[i + 1] > prices[i]:
            result += prices[i + 1] - prices[i]
    return result

풀이 2. 파이썬다운 방식

def solution(prices):
    # 0보다 크면 무조건 합산
    return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))

키에 따른 대기열 재구성

• 여러 명의 사람들이 줄을 서 있다. 각각의 사람은 (h, k)의 두 정수 쌍을 갖는데, h는 그 사람의 키, k는 앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들에 수를 뜻한다. 이 값이 올바르도록 줄을 재정렬하는 알고리즘을 작성하라.

예제

• 입력: [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
• 출력: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

풀이 1. 우선순위 큐 이용

• 우선순위 큐는 그때그때의 최소 또는 최댓값을 추출하기 때문에 그리디에 어울리는 대표적인 자료구조라 할 수 있다.
• 첫번째 값이 큰 순서대로 추출되는 최대 힙 형태로 풀이할 수 있고 두 번째 값은 삽입되는 인덱스로 활용할 수 있다.

def solution(people):
    heap = []
    # 키 역순, 인덱스 삽입
    for person in people:
        heapq.heappush(heap, (-person[0], person[1]))

    result = []
    # 키 역순, 인덱스 추출
    while heap:
        person = heapq.heappop(heap)
        result.insert(person[1], [-person[0], person[1]])

    return result

태스크 스케줄러

• A에서 Z로 표현된 태스크가 있다. 각 간격마다 CPU는 한 번의 태스크만 실행 할 수 있고, n번의 간격 내에는 동일한 태스크를 실행할 수 없다. 더 이상 태스크를 실행할 수 없는 경우 아이들 상태가 된다. 모든 태스크를 실행하기 위한 최소 간격을 출력하라.

예제

• 입력: task = ["A", "A", "A". "B". "B". "B"], n = 2
• 출력: 8

풀이 1. 우선순위 큐 사용

• 이 문제 역시 우선순위 큐를 이용해 그리디하게 풀 수 있는 문제지만 아이템을 추출한 이후에는 매번 아이템 개수를 업데이트해줘야 한다. 간결한 방식을 풀어보기 위해 Counter 모듈을 사용해 코드를 구현해보자.

def solution(tasks, n):
    counter = collections.Counter(tasks)
    result = 0

    while True:
        sub_count = 0
        for task, _ in counter.most_common(n + 1):
            sub_count += 1
            result += 1

            counter.subtract(task) # 한개 씩 개수 줄이기
            # 0 이하인 아이템을 목록에서 완전히 제거
            counter += collections.Counter()

        if not counter:
            break

        result += n - sub_count + 1

    return result

주유소

• 원형으로 경로가 연결된 주유소 목록이 있다. 각 주유소는 gas[i]만큼의 기름을 갖고 있으며, 다음 주유소로 이동하는 데 cost[i]가 필요하다. 기름이 부족하면 이동할 수 없다고 할 때 모든 주유소를 방문할 수 있는 출발점의 인덱스를 출력하라.
• 출발점이 존재하지 않는 경우 -1을 출력하라.

예제

• 입력: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
• 출력: 3

풀이 1. 한 번 방문

• 전체 기름의 양이 전체 비용보다 클 경우 반드시 전체를 방문할 수 있는 출발점이 존재한다. 이 문제에는 출발점이 유일하다는 제약이 있으므로 반드시 한군데만 존재한다.
• 이 문제는 한 번 이상은 반드시 성립되지 않는 지점이 존재한다. 성립되지 않는 지점이 있을 때 그 앞은 전부 출발점이 될 수 없다.

def solution(gas, cost):
    # 모든 주유소 방문 가능 여부 판별
    if sum(gas) < sum(cost):
        return -1

    start, fuel = 0, 0
    for i in range(len(gas)):
        # 출발이 안되는 지점 판별
        if gas[i] + fuel < cost[i]:
            start = i + 1
            fuel = 0
        else:
            fuel += gas[i] - cost[i]
    return start

쿠키 부여

• 아이들에게 1개씩 쿠키를 나눠줘야 한다. 각 아이마다 그리드 팩터를 가지고 있으며 이는 아이가 만족하는 최소 쿠키의 크기를 말한다. 각 쿠키는 크기를 갖고 있으며 크기가 그리드 팩터보다 커야 아이가 만족하며 쿠키를 받는다. 최대 몇 명의 아이들에게 쿠키를 줄 수 있는 지 출력하라.

예제

• 입력: [1, 2, 3], [1, 1]
• 출력: 1
• 설명: 두 번째 아이부터는 크기 2 이상의 쿠키가 필요하지만, 갖고 있는 최대 크기는 1이기 때문에 1명의 아이에게만 줄 수 있다.

풀이 1. 그리디 알고리즘

def solution(g, s):
    g.sort()
    s.sort()

    child_i = cookie_j = 0
    # 만족하지 못할 때까지 그리디 진행
    while child_i < len(g) and cookie_j < len(s):
        if s[cookie_j] >= g[child_i]:
            child_i += 1
        cookie_j += 1

    return child_i

슬라이딩 윈도우

• 슬라이딩 윈도우란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다.
• 정렬된 배열을 대상으로 하는 투 포인터와 달리 슬라이딩 윈도우는 정렬 여부와 관계 없이 활용된다는 차이가 있다.

최대 슬라이딩 윈도우

• 배열 nums가 주어졌을 때 k 크기의 슬라이딩 윈도우를 오른쪽 끝까지 이동하면서 최대 슬라이딩 윈도우를 구하라.

예제

• 입력: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
• 출력: [3, 3, 5, 5, 6, 7]

풀이 1. 큐를 이용한 최적화

• 슬라이딩 윈도우에서 최댓값을 추출하려면 어떠한 알고리즘이든 결국 한번 이상은 봐야하기 때문에 O(n)의 시간이 든다.
• 따라서 가급적 최댓값 계산을 최소화하기 위해 이전의 최댓값을 저장해뒀다가 한칸씩 이동할 때 새 값에 대해서만 더 큰 값인지 확인하고 최댓값이 윈도우에서 빠지게 되는 경우만 다시 전체를 계산하는 형태로 개선한다.

def solution(nums, k):
    result = []
    window = collections.deque()
    current_max = float('-inf')
    for i, v in enumerate(nums):
        window.append(v)
        if i < k - 1:
            continue

        # 새로 추가된 값이 기존 최댓값보다 큰 경우 교체
        if current_max == float('-inf'):
            current_max = max(window)
        elif v > current_max:
            current_max = v

        result.append(current_max)

        # 최댓값이 윈도우에서 빠지면 초기화
        if current_max == window.popleft():
            current_max = float('-inf')
    return result

부분 문자열이 포함된 최소 윈도우

• 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라

예제

• 입력: S = "ADOBECODEBANC", T = "ABC"
• 출력: "BANC"

풀이 1. 투 포인터, 슬라이딩 윈도우로 최적화

• 우측으로 슬라이딩 윈도우를 이동시키면서 좌우 포인터의 크기를 좁혀 나가는 투 포인터로 풀이할 수 있다.

def solution(s, t):
    need = collections.Counter(s)
    missing = len(t)
    left = start = end = 0

    # 오른쪽 포인터 이동
    for right, char in enumerate(s, 1):
        missing -= need[char] > 0
        need[char] -= 1

        # 필요 문자가 0이면 왼쪽 포인터 이동 판단
        if missing == 0:
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1

            if not end or right - left <= end - start:
                start, end = left, right
                need[s[left]] += 1
                missing += 1
                left += 1
        return s[start:end]

풀이 2. Counter로 좀 더 편리한 풀이

• 필요한 문자의 개수를 직접 계산하지 않고 Counter의 기능을 이용해 풀이한다. missing == 0 대신 Counter의 AND 연산으로 비교한다.

def solution(s, t):
    t_count = collections.Counter(t)
    current_count = collections.Counter()

    start = float('-inf')
    end = float('inf')

    left = 0
    # 오른쪽 포인터 이동
    for right, char in enumerate(s, 1):
        current_count[char] += 1

        # AND 연산 결과로 왼쪽 포인터 이동 판단
        while current_count & t_count == t_count:
            if right - left < end - start:
                start, end = left, right
            current_count[s[left]] -= 1
            left += 1

    return s[start:end] if end - start <= len(s) else ''

• 그러나 아쉽게도 이 풀이는 너무 느리게 실행된다. Counter끼리 AND 연산으로 비교하는 과정이 내부적으로 매우 무거운 연산이기 때문이다.

가장 긴 반복 문자 대체

• 대문자로 구성된 문자열 s가 주어졌을 때 k번만큼의 변경으로 만들 수 있는, 연속으로 반복된 문자열의 가장 긴 길이를 출력하라.

예제

• 입력: s = "AAABBC", k = 2
• 출력: 5
• 설명: B를 A로 각각 2번 변경하면 길이 5인 AAAAA를 만들 수 있다.

풀이 1. 투 포인터, 슬라이딩 윈도우, Counter를 모두 이용

• 이 문제는 오른쪽 포인터가 계속 우측으로 이동한다는 점에서 슬라이딩 윈도우 문제이지만 왼쪽 포인터를 계속 좁혀서 범위를 조절해 나간다는 점에서는 투포인터와 결합된 문제이다.
• 오른쪽 포인터에서 왼쪽 포인터 위치를 뺀다음, 윈도우 내 출현 빈도가 가장 높은 문자의 수를 뺀 값이 k와 같을 수 있는 수 중 가장 큰 최댓값이라 정의할 수 있다.

def solution(s, k):
    left = right = 0
    counts = collections.Counter()
    for right in range(1, len(s) + 1):
        counts[s[right - 1]] += 1
        # 가장 흔하게 등장하는 문자 탐색
        max_char_n = counts.most_common(1)[0][1]

        # k 초과시 왼쪽 포인터 이동
        if right - left - max_char_n > k:
            counts[s[left]] -= 1
            left += 1
    return right - left

• 길이의 최댓값을 구하는 과정은 생략할 수 있다. 최댓값이 된 상태에서는 오른쪽 포인터가 한 칸 이동하면 왼쪽 포인터도 따라서 이동하게 되면서 값은 바뀌지 않기 때문이다.

비트 조작

부울 연산자

• AND, OR, NOT은 기본 부울 연산자로, 연산들을 서로 결합하거 조합해 다른 보조 연산을 만들어 낼 수 있다. 대표적으로 XOR이 보조 연산에 해당한다.
• XOR은 단순한 보조 연산을 넘어 디지털 논리 게이트에서 매우 중요한 위치를 차지한다.

비트 연산자

True & False # AND
True | False # OR
True ^ False # XOR
~True

• 비트 연산자 ~는 부울 변수에 적용하면 True는 1로 간주되어 -2가 된다.

2의 보수

• 2의 보수는 컴퓨터가 음수를 저장하기 위해 일반적으로 취하는 여러 방법 중 하나이다.
• 4비트로 숫자를 표현할 때, 양수만 저장한다면 0부터 15까지 0000~1111로 저장하면 되지만 음수도 저장하기 위해선 비트의 절반을 쪼개서 음수 몫으로 할당하고 맨 앞 비트를 부호 비트로 사용한다(MSB). 즉, 양수의 경우 0xxx를 사용하고 음수의 경우 1xxx를 사용한다.
• 4비트로 2의 보수를 표현하기 위해선 비트마스크 MASK를 이용한다. 비트마스크는 자릿수 만큼의 최댓값을 표현한 값이다.

MASK = 0xF
bin(-1 & MASK)
# >>> '0b1111'

• 파이썬은 내부적으로 부호를 별도 필드로 갖고 있으며 비트 연산이 필요할 때만 2의 보수로 변환하는 작업을 한다.

5 & -4
# >>> 4

bin(0b0101 & 0b1100)
# >>> 0b100

2의 보수 수학연산

• 2의 보수 수학 연산은 가산 역 연산이라 부를 수 있다. 양수를 음수로, 음수를 양수로 바꾸는 작업을 말한다. 비트 연산자 NOT을 이용한 후 1을 더하면 된다. 즉 0111의 2의 보수 연산은 1000 + 1 = 1001이 된다.

bin(0b0101 ^ ~0b1100)
# >>> '-0b1010'

• 이 값이 0b0110이 아닌 이유는 입력값이 4비트 포맷이 아니기 때문에 오버플로가 발생했기 때문이다. 4비트 포맷에선 0b1100은 -4를 뜻하는데 양수 12를 가정했기 때문에 문제가 발생했다.

bin(0b00000101 ^ 0b11110011)
# >>> '0b11110110'

• 8비트 포맷으로 바꿔서 적용하면 XOR 값이 정확히 출력된다. 이 값은 -10이다. 앞서 결과였던 -0b1010도 -10이므로 동일하다.

싱글 넘버

• 딱 하나를 제외하고 모든 엘리먼트는 2개씩 있다. 1개인 엘리먼트를 찾아라.

예제

• 입력: [2, 2, 1]
• 출력: 1

풀이 1. XOR 풀이

• 단 1개의 엘리먼트를 찾는 데 적당한 연산자는 XOR이다. XOR은 입력값이 서로 다르면 True, 같으면 False가 되는 논리 게이트 연산자다. 이를 10진수에 적용하면 다음과 같은 결과를 확인할 수 있다.

0 ^ 0
# >>> 0
4 ^ 0
# >>> 4
4 ^ 4
# >>> 0

• XOR은 두번 등장한 엘리먼트는 0으로 초기화되고 한 번만 등장하는 엘리먼트는 그 값을 온전히 보존한다. 즉 배열의 모든 값을 XOR하면 단 한 번만 등장하는 엘리먼트만 그 값이 남게 된다.

def solution(nums):
    result = 0
    for num in nums:
        result ^= num

    return result

해밍 거리

• 두 정수를 입력받아 몇 비트가 다른지 계산하라.

예제

• 입력: x = 1, y = 4

• 출력: 2

• 설명

  • 1 (0 0 0 1)
  • 4 (0 1 0 0)
  • 2번째 비트와 4번째 비트가 다르므로 정답은 2이다.

풀이 1. XOR 풀이

• 해밍 거리는 두 정수 또는 두 문자열의 차이를 말한다. 예를 들어 'Karolin'과 'Kathrin'의 차이는 3이다. 문자열의 경우 해밍 거리는 다른 자리의 문자 개수가 되며, 이진수의 경우 다른 위치의 비트 개수가 된다.
• XOR 연산을 이용하면 비트가 서로 다른 자리는 1이 되므로 1의 전체 개수를 리턴하면 된다.

def solution(x, y):
    return bin(x ^ y).count('1')

두 정수의 합

• 두 정수 a와 b의 합을 구하라. + 또는 - 연산자는 사용할 수 없다.

예제

• 입력: a = 1, b = 2
• 출력: 3

풀이 1. 전가산기 구현

• 두 정수의 합을 구하는 데 덧셈이나 뺄셈을 사용할 수 없기 때문에 비트 연산만으로 풀이해야 하는 문제다.
• 먼저 정수를 bin으로 2진수로 변환한 뒤 '0b'는 필요없기 때문에 [2:] 슬라이싱을 통해 앞 두자리를 제거해준다. 그 후 .zfill(32)를 이용해 32비트 자릿수를 맞춰준다.
• 이렇게 처리한 값을 뒷부분 부터 하나씩 전가산기를 통과하면서 결과를 채워나가면 된다.

def sum(a, b):
    MASK = 0xFFFFFFFF
    INT_MAX = 0x7FFFFFFF # 양의 정수 최댓값

    a_bin = bin(a & MASK)[2:].zfill(32)
    b_bin = bin(b & MASK)[2:].zfill(32)

    result = []
    carry = 0
    sum = 0
    for i in range(32):
        A = int(a_bin[31 - i])
        B = int(b_bin[31 - i])

        # 전가산기 구현
        Q1 = A & B
        Q2 = A ^ B
        Q3 = Q2 & carry
        sum = carry ^ Q2
        carry = Q1 | Q3

        result.append(str(sum))
    if carry == 1:
        result.append('1')

    # 초과 자릿수 처리
    result = int(''.join(result[::-1]), 2) & MASK
    # 음수 처리
    if result > INT_MASK:
        result = ~(result ^ MASK)

    return result

UTF-8 검증

• 입력값이 UTF-8 문자열이 맞는지 검증하라.

예제

• data = [197, 130, 1] 이 값은 11000101 10000010 00000001로 표현되며 2바이트 문자 다음에 오는 1바이트 문자로 모두 2개며 정상이다.

풀이 1. 첫 바이트를 기준으로 한 판별

• 이 표를 기준으로 첫 바이트가 1110으로 시작한다면 3바이트 문자이므로, 첫 바이트를 제외하고 뒤따르는 2바이트는 모두 10으로 시작해야 유효한 UTF-8 문자가 된다.

def solution(data):
    # 문자 바이트만큼 10으로 시작 판별
    def check(size):
        for i in range(start + 1, start + size + 1):
            if i >= len(data) or (data[i] >> 6) != 0b10:
                return False
        return True

    start = 0
    while start < len(data):
        # 첫 바이트 기준 총 문자 바이트 판별
        first = data[start]
        if (first >> 3) == 0b11110 and check(3):
            start += 4
        elif (first >> 4) == 0b1110 and check(2):
            start += 3
        elif (first >> 5) == 0b110 and check(1):
            start += 2
        elif (first >> 7) == 0:
            start += 1
        else:
            return False
    return True

1비트의 개수

• 부호 없는 정수형을 입력받아 1비트의 개수를 출력하라

예제

• 입력: 11111111111111111111111111111101
• 출력: 31

풀이 1. 1의 개수 계산

• 다음과 같이 이진수에서 1의 개수를 헤아리는 정도로 매우 쉽게 풀이할 수 있다.

def solution(n):
    return bin(n).count('1')

풀이 2. 비트 연산

• 파이썬의 문자열 기능을 사용하지 않고 비트 연산만으로 1비트의 개수를 헤아린다.
• 비트는 1을 뺀 값과 and 연산을 할 때마다 비트가 1씩 빠지게 된다. 그렇다면 0이 될 때 까지 이 작업을 반복하면 전체 비트에서 1의 개수가 몇개인지 할 수 있다.

def solution(n):
    count = 0
    while n:
        # 1을 뺀 값과 AND 연산 횟수 측정
        n &= n - 1
        count += 1
    return count

이진검색

• 이진 검색이란 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다.
• 이진 검색은 시간복잡도가 O(log n)이라는 점에서 대표적인 로그 알고리즘이며 이진 탐색트리와도 유사한 점이 많다.

이진 검색

• 정렬된 nums를 입력받아 이진 검색으로 target에 해당하는 인덱스를 찾아라

예제

• 입력: nums = [-1, 0, 3, 5, 9, 12], target = 9
• 출력: 4

풀이 1. 재귀 풀이

• 절반씩 범위를 줄여나가며 맞출 때까지 계속 재귀 호출한다.

def solution(nums, target):
    def binary_search(left, right):
        if left <= right:
            mid = (left + right) // 2

            if nums[mid] > target:
                binary_search(mid + 1, right)
            elif nums[mid] < target:
                binary_search(left, mid - 1)
            else:
                return mid
        else:
            return -1
    return binary_search(0, len(nums) - 1)

재귀 제한

• 파이썬에는 재귀 호출에 대한 호출 횟수 제한이 있으며 기본 값은 1000으로 설정되어 있다.

풀이 2. 반복 풀이

def solution(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2

        if nums[mid] > target:
            left = mid + 1
        elif nums[mid] < target:
            right = mid - 1
        else:
            return mid
     return -1

풀이 3. 이진 검색 모듈

• 파이썬은 이진 검색 알고리즘을 지원하는 bisect 모듈을 기본으로 제공한다. 여러가지 예외 처리를 포함한 이진 검색 알고리즘을 지원한다.

def solution(nums, target):
    index = bisect.bisect_left(nums, target)

    if index < len(nums) and nums[index] == target:
        return index
    else:
        return -1

회전 정렬된 배열 검색

• 특정 피벗을 기준으로 회전하여 정렬된 배열에서 target값의 인덱스를 출력하라.

예제

• 입력: nums = [4, 5, 6, 7, 0, 1, 2], target = 1
• 출력: 5

풀이 1. 피벗을 기준으로 한 이진 검색

• 정렬이 되어 있긴 한데 피벗을 기준으로 입력값이 돌아간 상황이다. 먼저 피벗을 찾아야 이진 검색을 할 수 있다. 예제 입력값의 경우 피벗은 4다.
• 가장 작은 값을 찾는다면 해당 위치의 인덱스가 피벗이 될 수 있다.
• 최솟값 인덱스 left를 찾아내 pivot에 할당하고 이를 기준으로 mid를 피벗만큼 틀어 mid_pivot을 구성한다.
• mid_pivot = (mid + pivot) % len(nums)

def solution(nums, target):
    # 예외 처리
    if not nums:
        return -1

    # 최솟값을 찾아 피벗 설정
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    pivot = left

    # 피벗 기준 이진 검색
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        mid_pivot = (mid + pivot) % len(nums)

        if nums[mid_pivot] < target:
            left = mid + 1
        elif nums[mid_pivot] > target:
            right = mid - 1
        else:
            return mid_pivot

    return -1

두 배열의 교집합

• 두 배열의 교집합을 구하라

예제

• 입력: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
• 출력: [2]

풀이 1. 이진 검색으로 일치 여부 판별

• 한쪽은 순서대로 탐색하고 다른 쪽은 정렬해서 이진 검색으로 값을 찾는다.

def solution(nums1, nums2):
    result = set()
    nums2.sort()
    for n1 in nums1:
        # 이진 검색으로 일치 여부 판별
        i2 = bisect.bisect_left(nums2, n1)
        if len(nums2) > 0 and len(nums2) > i2 and n1 == nums2[i2]:
            result.add(n1)

        return result

풀이 2. 투 포인터로 일치 여부 판별

• 양쪽 다 정렬하여 투 포인터로 풀이할 수도 있다.

def solution(nums1, nums2):
    result = set()

    # 양쪽 모두 정렬
    nums1.sort()
    nums2.sort()

    i = j = 0

    # 투 포인터 우측으로 이동하며 일치 여부 판별
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            i += 1
        elif nums1[i] > nums2[j]:
            j += 1
        else:
            result.add(nums1[i])
            i += 1
            j += 1

    return result

두 수의 합

• 정렬된 배열을 받아 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 이 문제에서 배열은 0이 아닌 1부터 시작하는 것으로 한다.

예제

• 입력: numbers = [2, 7, 11, 15], target = 9
• 출력: [1, 2]

풀이 1. 투 포인터

• 단순히 두 수의 합은 투 포인터로 풀 수 없지만 이 문제는 입력 배열이 정렬되어 있으므로 투 포인터로도 풀 수 있다.
• 투 포인터 풀이의 경우 O(n)에 풀이할 수 있다.

def solution(numbers, target):
    left, right = 0, len(numbers) - 1
    while not left == right:
        if numbers[left] + numbers[right] < target:
            left += 1
        elif numsbers[left] + numbers[right] > target:
            right -= 1
        else:
            return left + 1, right + 1

풀이 2. 이진 검색

• 현재 값을 기준으로 나머지 값이 맞는지 확인하는 형태의 이진 검색 풀이를 한다.

def solution(number, target):
    for k, v in enumerate(numbers):
        left, right = k + 1, len(numbers) - 1
        expected = target - v
        # 이진 검색으로 나머지 값 판별
        while left <= right:
            mid = (left + right) // 2
            if numbers[mid] < expected:
                left = mid + 1
            elif numbers[mid] > expected:
                right = mid - 1
            else:
                return k + 1, mid + 1

풀이 3. bisect 모듈

• bisect_left()는 lo와 hi를 통해 좌우 범위를 제한할 수 있다.

def solution(numbers, target):
    for k, v in enumerate(numbers):
        expected = target - v
        i = bisect.bisect_left(numbers, expected, k + 1)
        if i < len(numbers) and numbers[i] == expected:
            return k + 1, i + 1

슬라이싱 성능

• 슬라이싱은 매번 새롭게 객체를 생성해서 할당하고 엄청나게 큰 배열의 경우 슬라이싱으로 새로운 객체를 생성하는 데 상당한 시간이 든다.
• 마찬가지로 배열의 길이를 계산하는 데도 매번 길이를 계산하는 비용이 들어서 상당한 시간이 소요된다.
• 슬라이싱을 하게 되면 전체 객체를 복사하게 되고 이 과정에서 시간이 들게 된다.

2D 행렬 검색

• m * n 행렬에서 값을 찾아내는 효율적인 알고리즘을 구현하라. 행렬은 왼쪽에서 오른쪽, 위에서 아래 오름차순으로 정렬되어 있다.

예제

• 입력:

[

​ [1, 4, 7, 11, 15],

​ [2, 5, 8, 12, 19],

​ [3, 6, 9, 16, 22],

​ [10, 13, 14, 17, 24],

​ [18, 21, 23, 26, 30]

]

풀이 1. 첫 행의 맨 뒤에서 탐색

• 이 문제는 열을 기준으로 이진 검색을 수행한 다음 찾아낸 값을 기준으로 해당 위치의 각 행을 기준으로 다시 이진검색을 수행하면 해결할 수 있다.

• 첫 행의 맨 뒤 요소를 택한 다음 타겟이 이보다 작으면 왼쪽으로, 크면 아래로 이동하게 한다.

def solution(matrix, target):
    # 예외처리
    if not matrix:
        return False

    # 첫 행의 맨 뒤
    row = 0
    col = len(matrix[0]) - 1

    while row <= len(matrix) - 1 and col >= 0:
        if target == matrix[row][col]:
            return True
        # 타겟이 작으면 왼쪽으로 이동
        elif target < matrix[row][col]:
            col -= 1
        # 타겟이 크면 아래로 이동
        elif target > matrix[row][col]:
            row += 1

    return False

풀이 2. 파이썬다운 방식

def solution(matrix, target):
    return any(target in row for row in matrix)

• 내부적으로 행렬에 값이 존재하는지 여부를 위에서부터 차례대로 한 줄씩 탐색하게 될 것이다.
• any()는 하나라도 True라면 True를 출력하고, all()는 모든 값이 참이어야 True를 출력한다.

정렬

• 정렬 알고리즘은 목록의 요소를 특정 순서대로 넣는 알고리즘이다. 대개 숫자식 순서와 사전식 순서로 정렬한다.

버블 정렬

Bubblesort(A)
    for i from 1 to A.length
        for j from 0 to A.length - 1
            if A[j] > A[j + 1]
                swap a[j] with a[j + 1]

• 이 알고리즘은 n번의 라운드로 이뤄져있으며, 각 라운드마다 배열의 아이템을 한 번씩 죽 모두 살펴본다.
• 배열 전체를 살펴보는 것을 n번 하기 때문에 시간 복잡도는 항상 O(n^2)이다.

병합 정렬

• 최선과 최악 모두 O(n log n)으로 일정한 알고리즘이다.
• 대부분의 경우 퀵 정렬보다는 느리지만 일정한 실행 속도뿐 만 아니라 안정 정렬이라는 점에서 여전히 상용 라이브러리에 많이 쓰이고 있다.
• 분할 정복으로 배열을 더 이상 쪼갤 수 없을 때까지 분할한 후, 분할이 끝나면 정렬하면서 정복해 나간다.

퀵 정렬

• 피벗을 기준으로 좌우를 나누는 특징 때문에 파티션 교환 정렬이라고도 불리운다.

• 병합 정렬과 마찬가지로 분할 정복 알고리즘이며 여기에 피벗이라는 개념을 통해 피벗보다 작으면 왼쪽, 크면 오른쪽과 같은 방식으로 파티셔닝 하면서 쪼개 나간다.

• 로무토 파티션은 항상 맨 오른쪽의 피벗을 택하는 단순한 방식으로 최초의 퀵 정렬 알고리즘보다 훨씬 더 이해하기 쉽다.

# lo = 왼쪽 끝, hi = 오른쪽 끝
def Quicksort(A, lo, hi):
    def partition(lo, hi):
        pivot = A[hi]
        left = lo
        for right in range(lo, hi):
            if A[right] < pivot:
                A[left], A[right] = A[right], A[left]
                left += 1
        A[left], A[hi] = A[hi], A[left]
        return left

    if lo < hi:
        pivot = partition(lo, hi)
        Quicksort(A, lo, pivot - 1)
        Quicksort(A, pivot + 1, hi)

• 퀵 정렬은 매우 빠르고 효율적이지만 최악의 경우, 이미 정렬된 배열이 입력값으로 들어왔을 경우 O(n^2)가 된다.

안정 정렬 vs 불안정 정렬

• 안정 정렬 알고리즘은 중복된 값을 입력 순서와 동일하게 정렬한다.
• 입력값이 유지되는 안정 정렬 알고리즘이 불안정 정렬 알고리즘보다 유용하다.
• 대표적으로 병합 정렬, 버블 정렬이 안정 정렬이며 퀵정렬은 불안정 정렬이다. 따라서 실무에서는 병합 정렬이 여전히 활발히 쓰이고 있으며, 파이썬의 기본 정렬 알고리즘으로는 병합 정렬과 삽입 정렬을 휴리스틱하게 조합한 팀소트를 사용한다.

리스트 정렬

• 연결 리스트를 O(n log n)에 정렬하라.

예제

• 입력: 4 -> 2 -> 1 -> 3
• 출력: 1 -> 2 -> 3 -> 4

풀이 1. 병합 정렬

• 연결 리스트 입력에 대해서는 파이썬에서 정렬할 수 있는 별도의 함수를 제공하지 않기 때문에 직접 정렬 알고리즘을 구현해야 한다.
• 연결 리스트는 특성상 피벗을 고정된 위치로 지정할 수밖에 없고 입력값에 따라 성능의 편차가 심하므로 병합정렬로 구현한다.
• 병합 정렬의 분할 정복을 위해서는 중앙을 분할해야 하므로 런너 기법을 사용한다.

def MergeTwoLists(l1, l2):
    if l1 and l2:
        if l1.val > l2.val:
            l1, l2 = l2, l1
        l1.next = MergeTwoLists(l1.next, l2)

    return l1 or l2

def sortLists(head):
    if not (head or head.next):
        return head

    # 런너 기법 활용
    half, slow, fast = None, head, head
    while fast and fast.next:
        half, slow, fast = slow, slow.next, fast.next.next
    half.next = None

    # 분할 재귀 호출
    l1 = self.sortLists(head)
    l2 = self.sortLists(slow)

    return self.mergeTwoLists(l1, l2)

구간 병합

• 겹치는 구간을 병합하라.

예제

• 입력: [[1, 3], [2, 6], [8,10], [15, 18]]
• 출력:[[1, 6], [8, 10], [15, 18]]

풀이 1. 정렬하여 병합

• 이 문제를 풀기 위해 먼저 정렬을 수행한다. 정렬 순서는 첫번째 값을 기준으로 한다.
• 그 후 현재 아이템의 시작이 이전 아이템의 끝과 겹치게 되면 최댓값을 기준으로 병합하는 형태로 반복해 나간다.

def solution(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for i in intervals:
        if merged and i[0] <= merged[-1][1]:
            merged[-1][1] = max(i[1], merged[-1][1])
        else:
            merged += i,
    return merged

콤마 연산자

• 기본적인 추가 연산의 경우 요소를 이어붙인다.

a = [1]
b = [2, 3]
a += b
a
# [1, 2, 3]

• 콤마를 넣으면 중첩리스트가 된다. 콤마는 대괄호를 부여한 것과 동일한 역할을 한다.

a = [1]
b = [2, 3]
a += b,
a
# [1, [2, 3]]

삽입 정렬 리스트

• 연결 리스트를 삽입 정렬로 정렬하라

풀이 1. 삽입 정렬

• 삽입정렬은 정렬을 해야 할 대상과 정렬을 끝낸 대상, 두 그룹으로 나눠 진행한다. head는 정렬을 해야 할 대상이며 cur는 정렬을 끝낸 대상으로 정한다. 다음과 같이 정렬을 해야할 대상 head를 반복한다.

cur = parent = ListNode(None)
while head:
    while cur.next and cur.next.val < head.val:
        cur = cur.next

• 먼저 cur과 parent는 빈 노드로 정한다. cur엔 정렬을 끝낸 연결 리스트를 추가해줄 것이고, parent는 계속 그 위치에 두어 사실상 루트를 가리키게 한다.

• 정렬을 끝낸 cur는 이미 정렬된 상태이므로 정렬을 해야 할 대상 head와 비교하면서 더 작다면 계속 cur.next로 이동한다. 그 후 cur에 삽입될 위치를 찾았다면 cur 연결리스트에 추가한다.

• cur 위치 다음에 head가 들어가고 head.next에는 cur.next를 연결해서 계속 이어지게 한다. 그리고 다음번 head는 head.next로 차례를 이어 받는다. 이후에는 cur = parent를 통해 다시 처음으로 되돌아가며 차례대로 다시 비교하게 된다.

• 다음번 head도 cur보다 크다면 처음으로 돌아갈 필요가 없으므로 필요한 경우에만 포인터가 돌아가도록 한다.

def insertionSortList(head):
    cur = parent = ListNode(None)
    while head:
        while cur.next and cur.next.val < head.val:
            cur = cur.next

        cur.next, head.next, head = head, cur.next, head.next

        # 필요한 경우에만 cur 포인터가 되돌아가도록 처리
        if head and cur.val > head.val:
            cur = parent

    return cur.next

가장 큰 수

• 항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하라.

예제

• 입력: [10, 2]
• 출력: "210"

풀이 1. 삽입 정렬

• 맨 앞에서부터 자릿수 단위로 비교해서 크기 순으로 정렬한다. 즉 9는 30보다 맨 앞자리 수가 크므로 9가 더 파에 와야한다.

class solution():
    # 문제에 적합한 비교 함수
    @staticmethod
    def to_swap(n1, n2):
        return str(n1) + str(n2) < str(n2) + str(n1)

    def largestNumber(nums):
        i = 1
        while i < len(nums):
            j = i
            while j > 0 and self.to_swap(nums[j - 1], nums[j]):
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
                j -= 1
            i += 1

유효한 애너그램

• t가 s의 애너그램인지 판별하라.

예제

• 입력: s = "anagram", t = '"nagaram"
• 출력: True

풀이 1. 정렬을 이용한 비교

• 애너그램 여부를 판별하려면 양족 문자열을 모두 정렬하고 그 상태가 일치하는지 확인하면 된다.

def solution(s, t):
    return sorted(s) == sorted(t)

색 정렬

• 빨간색을 0, 흰색을 1, 파란색을 2라 할 때, 순서대로 인접하는 제자리 정렬을 수행하라.

예제

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

풀이 1. 네덜란드 국기 문제를 응용한 풀이

• 이 문제는 다익스트라가 제안한 네덜란드 국기 문제와 동일한 문제로, 퀵 정렬의 개선 아이디어와도 관련이 깊다.
• 네덜란드 국기 색깔인 붉은색, 흰색, 파란색을 세 부분으로 대입해 분할하는 것으로서, 피벗보다 작은 부분, 같은 부분, 큰 부분 이렇게 세 부분으로 분할하려 기존 퀵 정렬의 두 부분 분할에 비해 개선하는 방안을 제시하는 것이다.
• 네덜란드 국기 문제의 수도코드는 다음과 같다.

three-way-partition(A : array of values, mid : value):
    i = 0
    j = 0
    k = size of A

    while j < k:
         if A[j] < mid:
             swap A[i] and A[j]
            i += 1
            j += 1
         else if A[j] > mid:
             k -= 1
             swap A[j] and A[k]
         else:
             j += 1

• i와 k로 영역을 점점 좁혀가면서 mid에 해당하는 값을 모은다.

def solution(nums):
    red, white, blue = 0, 0, len(nums)

    while white < blue:
        if nums[white] < 1:
            nums[red], nums[white] = nums[white], nums[red]
            white += 1
            red += 1
        elif nums[white] > 1:
            blue -= 1
            nums[white], nums[blue] = nums[blue], nums[white]
        else:
            white += 1

원점에 K번째로 가까운 점

• 평면상에 points 목록이 있을 때, 원점 (0, 0)에서 K번 가까운 점 목록을 순서대로 출력하라. 평면상 두 점의 거리는 유클리드 거리로 한다.

예제

• 입력: points = [[1, 3], [-2, 2]], K = 1
• 출력: [[-2, 2]]

풀이 1. 유클리드 거리의 우선순위 큐 순서

• 유클리드 거리를 계산에 heap에 push한 뒤 k번 추출하여 리턴한다.
• 유클리드 거리에 math.sqrt()는 하지 않아도 결과는 같으므로 생략한다.

def solution(points, k):
    heap = []
    for x, y in points:
        dist = x**2 + y**2
        heapq.heappush(heap, (dist, x, y))

    result = []
    for _ in range(k):
        (dist, x, y) = heapq.heappop()
        result.append((x, y))

    return result

힙

• 힙은 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료 구조다.

• 최소 힙은 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖게 되며, 우선순위 큐에서 가장 작은 값을 추출하는 것은 매번 힙의 루트를 가져오는 형태로 구현된다.

• 힙은 부모노드가 항상 작다는 조건만 만족할 뿐, 왼쪽 노드와 오른쪽 노드에 대한 관계는 정의하지 않는다.

• 자식이 둘인 힙은 특별히 이진 힙이라고 하며, 대부분은 이진 힙이 널리 사용된다.

힙 연산

삽입

1. 요소를 가장 하위 레벨의 최대한 왼쪽으로 삽입한다.(배열로 표현할 경우 가장 마지막에 삽입)
2. 부모 값과 비교해 값이 더 작은 경우 위치를 변경한다.
3. 계속해서 부모 값과 비교해 위치를 변경한다.

• 시간복잡도는 O(log n)이다.

추출

• 추출은 루트를 추출하면 된다. 하지만 추출 후 힙의 특성을 유지해야 하기 때문에 시간 복잡도는 O(log n)이다.
• 추출 이후 비어 있는 노드엔 가장 마지막 요소가 올라가게 되고 자식 노드와 값을 비교해서 자식보다 크다면 내려가는 다운 힙 연산이 수행된다.

class BinaryHeap():
    def __init__(self):
        self.items = [None]

    def __len__(self):
        return len(self.items) - 1

    # 삽입 시 실행, 반복 구조 구현
    def _percolate_up(self):
        i = len(self)
        parent = i // 2
        while parent > 0:
            if self.items[i] < self.items[parent]:
                self.items[i], self.items[parent] = self.items[parent], self.items[i]
            i = parent
            parent = i // 2

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    # 추출시 실행, 재귀 구조 구현
    def _percolate_down(self, idx):
        left = idx * 2
        right = idx * 2 + 1
        smallest = idx

        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left
        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right

        if smallest != idx:
            self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx]
            self._percolate_down(smallest)

    def extract(self):
        extracted = self.items[1]
        self.items[1] = self.items[len(self)]
        self.items.pop()
        self._percolate_down(1)
        return extracted

배열의 k번째 큰 요소

• 정렬되지 않은 배열에서 k번째 큰 요소를 추출하라.

예제

• 입력: [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
• 출력: 4

풀이 1. heapq 모듈 사용

def solution(nums, k):
    heap = list()
    for n in nums:
        heapq.heappush(heap, -n)

    for _ in range(1, k):
        heapq.heappop(heap)

    return -heapq.heappop(heap)

풀이 2. heapq 모듈의 nlargest 이용

def solution(nums, k):
    return heapq.nlargest(k, nums)[-1]

• k번째만큼 큰 값이 가장 큰 값부터 순서대로 리스트로 리턴된다. 여기서 마지막 인덱스 -1이 k번째 값이 된다. nsmallest()를 사용하면 동일한 방식으로 n번째 작은 값도 추출할 수 있다.

풀이 3. 정렬을 이용한 풀이

• 추가, 삭제가 빈번할 때는 heapq를 이용한 힙정렬이 유용하지만 입력값이 고정되어 있을 때는 한번 정렬하는 것만으로 충분하다.

def solution(nums, k):
    return sorted(nums, reverse=True)[k - 1]

트라이

• 트라이(trie)는 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조다.

• 검색을 뜻하는 retrieval의 중간음절에서 따왔다.

• 이진 트리가 아니라 다진 트리의 형태를 띈다.

• 트라이는 문자 단위로 색인을 구축한 것과 유사하다. 문자열의 길이만큼 탐색하면 원하는 결과를 찾을 수 있다.

트라이 구현

• 트라이의 insert, search, startswith 메소드를 구현하라.

풀이 1. 딕셔너리를 이용해 간결한 트라이 구현

# 트라이의 노드
class TrieNode:
    def __init__(self):
        self.word = False
        self.children = collections.defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    # 단어 삽입
    def insert(self, word):
        node = self.root
        for char in word:
            node = node.children[char]
        node.word = True

    # 단어 존재 여부 판별
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.childeren:
                return False
            node = node.childeren[char]
        return node.word

    # 문자열로 시작 단어 존재 여부 판별
    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]

        return True  

팰린드롬 페어

• 단어 리스트에서 word[i] + word[j]가 팰린드롬이 되는 모든 인덱스 조합(i, j)를 구하라.

예제

• 입력: ['abcd', 'dcba', 'lls', 's', 'sssll']
• 출력: [[0, 1], [1, 0], [3, 2], [2, 4]]

풀이 1. 팰린드롬을 브루트 포스로 계산

• n^2번 반복하면서 모든 조합을 구성하고 매번 팰린드롬 여부인지 체크한다. 하지만 효율적이지 않아 타임아웃이 발생한다.

def solution(words):
    def is_palindrome(word):
        return word == word[::-1]

    output = []
    for i, word1 in enumerate(words):
        for j, word2 in enumerate(words):
            if i == j:
                continue
            if is_palindrome(word1 + word2):
                output.append([i, j])

    return output

풀이 2 . 트라이 구현

• 이 문제를 O(n)으로 풀기 위해선 모든 단어를 트라이로 만들어 두고 한 번씩만 탐색하는 문제로 변형할 것이다.
• 팰린드롬을 판별해야 하기 때문에, 뒤집어서 트라이로 구성하면 해법을 찾을 수 있다.
• 문자를 뒤집은 다음, 문자 단위로 계속 내려가며 트라이를 구현하고 단어가 끝나는 지점에는 단어 인덱스를 word_id로 부여한다.
• 트라이에 단어를 삽입하면서 남아 있는 단어가 팰린드롬일 경우 해당 노드에 palindrome_id를 부여한다.
• 판별 로직은 다음과 같다.
  • 탐색 중간에 word_id가 있고 나머지 문자가 팰린드롬인 경우 (해당 word_id의 단어를 앞 뒤에 붙이면 팰린드롬)
  • 끝까지 탐색했을 때,
    • word_id가 있는 경우 (서로 정반대 배열의 문자열)
    • palindrome_word_ids가 있는 경우 (탐색중인 단어를 palindrome_word_id의 단어에 붙이면 팰린드롬)

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.word_id = -1
        self.palindrome_word_ids = []

class Trie:
    def __init__(self):
        self.root = TrieNode()

    @staticmethod
    def is_palindrome(word):
        return word[::] == word[::-1]

    # 단어 삽입
    def insert(self, index, word):
        node = self.root
        for i, char in enumerate(reversed(word)):
            if self.is_palindrome(word[0: len(word) - i]):
                node.palindrome_word_ids.append(index)
            node = node.children[char]
        node.word_id = index

    def search(self, index, word):
        result = []
        node = self.root

        while word:
            # 판별 로직 - 1
            if node.word_id >= 0:
                if self.is_palindrome(word):
                    result.append([index, node.word_id])
            if not word[0] in node.children:
                return result
            node = node.children[word[0]]
            word = word[1:]

        # 판별 로직 - 2
        if node.word_id >= 0 and node.word_id != index:
            result.append([index, node.word_id])

        # 판별 로직 - 3
        for palindrome_word_id in node.palindrome_word_ids:
            result.append([index, palindrome_word_id])

        return result

class Solution:
    def palindromePairs(words):
        trie = Trie()

        for i, word in enumerate(words):
            trie.insert(i, word)

        results = []
        for i, word in enumerate(words):
            results.extend(trie.search(i, word))
        return result

@staticmethod 데코레이터

• 이 데코레이터를 사용해 정의한 메소드는 클래스와 독립적인 함수로서의 의미를 갖는다
• 클래스 메소드처럼 자유롭게 클래스 인스턴스에 접근하는 것이 제한된다. 클래스 인스턴스에 접근을 제한하고 분명하게 독립적인 함수로 선언하고자 할 경우 종종 사용된다.

트리

• 트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형으로 루트 값과 부모 자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.
• 트리의 중요한 속성 중 하나는 재귀로 정의된 자기 참조 자료구조라는 점이다. 트리는 자식도 트리고 그 자식도 트리다.,

트리의 각 명칭

• 트리는 항상 루트(root)에서부터 시작된다, 루트는 자식(child) 노드를 가지며 간선(edge)으로 연결되어 있다. 자식 노드의 개수는 차수(degree)라고 하며, 크기(size)는 자신을 포함한 모든 자식 노드의 개수다. 높이(height)는 현재 위치부터 리프(leaf)까지의 거리, 깊이(depth)는 루트에서부터 현재 노드까지의 거리다. 레벨(level)은 0부터 시작한다. 트리는 항상 단방향이기 때문에 간선의 화살표는 생략 가능하다.

그래프 vs 트리

• 트리는 순환구조를 갖지 않는 그래프이다.
• 또한 트리는 부모노드에서 자식노드를 가리키는 단 방향 노드 뿐이다.
• 트리는 하나의 부모 노드를 갖는다는 차이점이 있고 루트도 하나여야 한다.

이진 트리

• 트리 중에서도 가장 널리 사용되는 트리 자료구조는 이진 트리와 이진 탐색트리(binary search tree)다. 모든 노드의 차수가 2 이하일 경우를 이진 트리라고 부른다.
• 이진트리의 유형
  • full binary tree: 모든 노드가 0개 또는 2개의 자식 노드를 갖는다
  • complete binary tree: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
  • perfect binary tree: 모든 노드가 2개의 자식 노드를 갖고 있으며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.

이진트리의 최대 깊이

• 이진트리의 최대 깊이를 구하라. [3, 9, 20, null, null, 15, 7]가 주어졌을 때, 깊이는 3이다.

풀이 1. 반복 구조로 BFS 풀이

• 길이 depth는 while 구문의 반복 횟수이므로 BFS에서 반복 횟수는 곧 높이가 된다. 이제 반복 횟수를 리턴하면 최종 결과를 구할 수 있다.

solution(root):
    if root is None:
        return 0
    queue = collections.deque([root])
    depth = 0

    while queue:
        depth += 1
        # 큐 연산 추출 노드의 자식 노드 삽입
        for _ in range(len(queue)):
            cur_root = queue.popleft()
            if cur_root.left:
                queue.append(cur_root.left)
            if cur_root.right:
                queue.append(cur_root.right)

    # BFS 반복 횟수 = 깊이
    return depth

이진 트리의 직경

• 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라.

풀이 1. 상태값 누적 트리 DFS

• 가장 긴 경로를 찾는 방법은 먼저 가장 말단, 즉 리프 노드까지 탐색한 다음 부모로 거슬러 올라가면서 각각의 거리를 계산해 상태값을 업데이트 하면서 누적하여 찾아간다.
• 최종적으로 가장 긴 경로의 길이는 왼쪽 자식 노드의 상태값과 오른쪽 자식 노드의 상태값의 합에 2를 더한 값이다.

class solution():
    longest = 0

    def diameterOfBinaryTree(root):
        def dfs(node):
            if not node:
                return -1

            # 왼쪽, 오른쪽 각 리프노드까지 탐색
            left = dfs(node.left)
            right = dfs(node.right)

            # 가장 긴 경로
            self.longest = max(self.longest, left + right + 2)

            # 상대값
            return max(left, right) + 1

        dfs(root)
        return self.longest

• 리스트나 딕셔너리와 같은 자료형은 append()등의 메소드를 이용해 재할당 없이 조작이 가능하지만 숫자나 문자는 불변 객체이기 때문에 중첩함수 내에서는 값을 변경할 수 없다.

가장 긴 동일 값의 경로

• 동일한 값을 지닌 가장 긴 경로를 찾아라.

풀이 1. 상태값 거리 계산 DFS

• 트리의 말단 리프노드까지 DFS로 탐색해 내려간 다음, 값이 일치할 경우 거리를 쌓아 올라가며 백트래킹한다.

class longestUnivaluePath():
    result = 0

    def solution(node):
        def dfs(node):
            if node is None:
                return 0

            # 존재하지 않는 노드까지 DFS 재귀 탐색
            left = dfs(node.left)
            right = dfs(node.right)

            # 현재 노드가 자식 노드와 동일한 경우 거리 1 증가
            if node.left and node.left.val == node.val:
                left += 1
            else:
                left = 0
            if node.right and node.right.val == node.val:
                right += 1
            else:
                right = 0

            # 왼쪽과 오른쪽 자식 노드 간 거리의 합 최댓값이 결과
            self.result = max(self.result, left + right)
            # 자식 노드 상태값 중 큰 값 리턴
            return max(left, right)

        dfs(root)
        return self.return

이진 트리 반전

• 중앙을 기준으로 이진트리를 반전하라.

풀이 1. 파이썬다운 방식

def solution(root):
    if root:
        root.left, root.right = self.solution(root.right), self.solution(root.left)
        return root
    return None

• 재귀가 마지막 노드까지 갔을 때부터, None을 return하고 스왑이 일어난다.

풀이 2. 반복 구조로 BFS

def solution(root):
    queue = collections.deque([root])

    while queue:
        node = queue.popleft()
        # 부모 노드부터 하향식 스왑
        if node:
            node.left, node.right = node.right, node.left

            queue.append(node.left)
            queue.append(node.right)

    return root

• 재귀 풀이가 가장 말단 노드까지 내려가서 백트래킹하며 스왑하는 방식이라면 이 풀이는 부모 노드부터 스왑하면서 계속 내려가는 하향 방식 풀이다.

풀이 3. 반복 구조로 DFS

def solution(root):
    stack = collections.deque([root])

    while queue:
        node = stack.pop()
        # 부모 노드부터 하향식 스왑
        if node:
            node.left, node.right = node.right, node.left

            stack.append(node.left)
            stack.append(node.right)

    return root

두 이진트리 병합

• 두 이진 트리를 병합하라. 중복되는 노드는 값을 합산한다.

풀이 1. 재귀탐색

def solution(t1, t2):
    if t1 and t2:
        node = Treenode(t1.val + t2.val)
        node.left = solution(t1.left, t2.left)
        node.right = solution(t1.right, t2.right)
        return node
    else:
        return t1 or t2

• 각 이진 트리의 루트부터 시작해 합쳐 나가면서 좌, 우 자식 노드 또한 병합될 수 있도록 각 트리 자식 노드를 재귀호출 한다. 만약 어느 한쪽 노드가 없다면 존재하는 노드만 리턴하고 재귀호출을 진행하지 않는다.

이진 트리 직렬화 & 역직렬화

• 이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라.

풀이 1. 직렬화 & 역직렬화 구현

• 이진 트리 데이터 구조는 논리적인 구조이다. 이를 파일이나 디스크에 저장하기 위해서는 물리적인 형태로 바꿔줘야 하는데, 이를 직렬화라고 한다.
• 파이썬에는 pickle이라는 직렬화 모듈을 기본으로 제공한다. 이 모듈의 이름으로 인해 파이썬 객체의 계층 구조를 바이트 스트림으로 변경하는 작업을 피클링이라고도 한다.

직렬화

• BFS를 이용해 직관적으로 구현한다.

def serialize(root):
    queue = collections.deque([root])
    result = ['#']
    # 트리 BFS 직렬화
    while queue:
        node = queue.popleft()
        if node:
            queue.append(node.left)
            queue.append(node.right)

            result.append(str(node.val))
        else:
            result.append('#')

    return ' '.join(result)

역직렬화

• 왼족 자식과 오른쪽 자식에 각각 별도의 인덱스르 부여하여 nodes를 탐색한다.

def deserialize(data):
    # 예외 처리
    if data == '# #':
        return None

    nodes = data.split()

    root = TreeNode(int(nodes[1]))
    queue = collections.deque([root])
    index = 2
    # 빠른 런너처럼 자식 노드 결과를 먼저 확인 후 큐 삽입
    while queue:
        node = queue.popleft()
        if nodes[index] is not '#':
            node.left = TreeNode(int(nodes[index]))
            queue.append(node.left)
        index += 1

        if nodes[index] is not '#':
            node.right = TreeNode(int(nodes[index]))
            queue.append(node.right)
        index += 1

    return root

균형 이진트리

• 이진트리가 높이 균형인지 판단하라. 높이 균형은 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것을 말한다.

풀이 1. 재귀 구조로 높이차이 계산

• 재귀로 노드의 높이를 출력하면서 왼쪽과 오른쪽의 높이 차이가 1 이상나면 false를 리턴한다.

def solution(root):
    def check(root):
        if not root:
            return 0

        left = check(root.left)
        right = check(root.right)
        # 높이 차이가 나는 경우 -1, 이외에는 높이에 따라 1 증가
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return max(left, right) + 1

    return check(root) != -1

최소높이 트리

• 노드의 개수와 무방향 그래프를 입력받아 트리가 최소 높이가 되는 루트의 목록을 리턴하라.

예시

• 입력: n = 4, edge = [[1, 0], [1, 2], [1, 3]]
• 출력: [1]

풀이 1. 단계별 리프노드 제거

• 최소 높이를 구성하려면 가장 가운데에 있는 값이 루트여야 한다. 이 말은 리프 노드를 하나씩 제거해 나가면서 남아 있는 값을 찾으면 이 값이 가장 가운데에 있는 값이 될 수 있다는 것이다.
• 리프노드는 그래프에서 해당 키의 값이 1개뿐인 것을 말한다.

def solution(n, edge):
    if n <= 1:
        return [0]

    # 양방향 그래프 구성
    graph = collections.defaultdict(list)
    for i, j in edge:
        graph[i].append(j)
        graph[j].append(i)

    # 첫번째 리프 노드 추가
    leaves = []
    for i in range(n + 1):
        if len(graph[i]) == 1:
            leaves.append(i)

    # 루트 노드만 남을 때까지 반복 제거
    while n < 2:
        n -= len(leaves)
        new_leaves = []
        for leaf in leaves:
            neighbor = graph[leaf].pop()
            graph[neighbor].remove(leaf)

            if len(graph[neighbor]) == 1:
                new_leaves.append(neighbor)
        leaves = new_leaves

    return leaves

이진 탐색 트리(BST)

• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드로 이루어져 있는 트리
• 탐색 시 시간복잡도가 O(log n)이다.

자가 균형 이진 탐색 트리

• 자가 균형 이진 탐색 트리는 삽입, 삭제시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리다.
• 자가 균형 이진 탐색트리는 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지한다. 높이를 최대한 낮게 유지하는 것이 중요하다는 것이다.

정렬된 배열의 이진 탐색 트리 변환

• 오름차순으로 정렬된 배열을 높이 균형 이진 탐색 트리로 변환하라.
• 이 문제에서 높이 균형이란 모든 노드의 두 서브 트리 간 깊이 차이가 1 이하인 것을 말한다.

풀이 1. 이진 검색 결과로 트리 구성

def solution(nums):
    if not nums:
        return None

    mid = len(nums) // 2

    # 분할 정복으로 이진 검색 결과 트리 구성
    node = TreeNode(nums[mid])
    node.left = solution(nums[:mid])
    node.right = solution(nums[mid + 1:])

    return node

이진 탐색 트리를 더 큰 수 합계 트리로

• BST의 각 노드를 현재값보다 더 큰 값을 가진 모든 노드의 합으로 만들어라.

풀이 1. 중위 순회로 노드 값 누적

• 자신보다 같거나 큰 값을 구하려면 자기 자신을 포함한 우측 자식 노드의 합을 구하면 된다.
• 루트를 입력받았을 때 먼저 맨 오른쪽까지 내려가고 그 다음 부모 노드, 다시 왼쪽 노드 순으로 이동하ㅕㄴ서 자신의 값을 포함해 누적한다.

class solution:
    val = 0

    def bstToGst(root):
        # 중위 순회 노드 값 누적
        if root:
            self.bstToGst(root.right)
            self.val += root.val
            root.val = self.val
            self.bstToGst(root.left)

        return root

이진 탐색 트리 합의 범위

• 이진 탐색 트리가 주어졌을 때 L 이상 R 이하의 값을 지닌 노드의 합을 구하라.

예제

• 입력: root = [10, 5, 15, 3, 7, null, 18], L = 7, R = 15
• 출력: 32

풀이 1. 재귀 구조 DFS로 브루트 포스 탐색

• DFS로 전체를 탐색한 다음 노드의 값이 L과 R 사이일 때만 값을 부여하고 아닐 경우에는 0을 취해 계속 더해 나가면 쉽게 구할 수 있다.

def solution(root, L, R):
    if not root:
        return 0

    return (root.val if L <= root.val <= R else 0) + solution(root.left, L, R) + solution(root.right, L, R)

풀이 2. DFS 가지치기로 필요한 노드 탐색

• DFS로 탐색하되 L, R의 조건에 해당되지 않은 가지를 쳐내는 형태로 탐색에서 배제하도록한다.
• 현재 root가 L보다 작을 경우 더 이상 왼쪽 가지는 탐색할 필요가 없기 때문에 오른족만 탐색하도록 재귀 호출을 리턴한다.

def solution(root, L, R):
    def dfs(node):
        if not node:
            return 0

        if node.val < L:
            return dfs(node.right)
        elif node.val > R:
            return dfs(node.left)
        return node.val + dfs(node.left) + dfs(node.right)

    return dfs(root)

이진 탐색 트리 노드간 최소 거리

• 두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라.

예제

• 입력: root = [4, 2, 6, 1, 3, null, null]
• 출력: 1

풀이 1. 재귀 구조로 중위 순회

• 중위 순회를 하면서 이전 탐색 값과 현재 값을 비교한다.

class solution:
    prev = -sys.maxsize
    result = sys.maxsize

    # 재귀 구조 중위 순회 비교 결과
    def minDiffInBST(root):
        if root.left:
            self.minDiffInBST(root.left)

        self.result = min(self.result, root.val - self.prev)
        self.prev = result.val

        if root.right:
            self.minDiffInBST(root.right)

        return self.result

트리 순회

• 트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정을 말한다.
• 이진 트리에서 DFS는 노드의 방문 순서에 따라 다음과 같이 크게 3가지 방식으로 구분된다.
  • 전위 순회(pre - order): 현재 노드를 먼저 순회한 다음 왼쪽, 오른쪽 서브트리 순회
  • 중위 순회(in - order): 왼쪽 서브트리를 순회한 후 현재 노드, 오른쪽 서브트리 순회
  • 후위 순회(post - order): 왼쪽과 오른쪽 서브트리를 순회한 다음 현재 노드 순회

전위 순회

def preorder(node):
    if node is None:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

중위 순회

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

후위 순회

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

전위, 중위 순회 결과로 이진트리 구축

• 전위, 중위 순회 결과를 입력값으로 받아 이진 트리를 구축하라.

풀이 1. 전위 순회 결과로 중위 순회 분할 정복

• 전위 순회의 첫번째 결과는 중위 순회 결과를 왼쪽과 오른쪽으로 분할 시키는 역할을 한다. 이를 이용해 중위 순회의 분할 정복 문제로 바꾼다.
• 전위 순회의 두번째 노드는 중위 순회의 왼쪽 결과를 정확히 반으로 가른다.
• 이후 남아 있는 노드들을 계속 분할을 시도한다.

def solution(preorder, inorder):
    if inorder:
        # 전위 순회 결과는 중위 순회 분할 인덱스
        index = inorder.index(preorder.pop(0))

        # 중위 순회 결과 분할 정복
        node = TreeNode(inorder[index])
        node.left = solution(preorder, inorder[0:index])
        node.right = solution(preorder, inorder[indes + 1:])

        return node

백준 단계별로 풀기 - 스택

10828번

• https://www.acmicpc.net/problem/10828
• 스택을 구현하는 문제다. 파이썬의 경우 리스트가 스택의 모든 기능을 제공하므로 리스트를 이용ㅎ면 쉽게 구현할 수 있다.
• 자꾸 시간 초과가 나서 코드가 잘못 되었나 했더니 백준에서는 input()대신 sys.stdin.readline()를 사용해야 시간초과를 막을 수 있다고 한다.

import sys

# 스택 개체 구현
class stack():
    def __init__(self):
        self.stk = []
        self.count = 0

    def empty(self):
        return int(self.count == 0)

    def size(self):
        return self.count

    def push(self, n):
        self.stk.append(n)
        self.count += 1

    def pop(self):
        if self.empty() == 0:
            self.count -= 1
            return self.stk.pop()
        else:
            return -1

    def top(self):
        if self.empty() == 0:
            return self.stk[-1]
        else:
            return -1

n = int(input())

stack = stack()

for i in range(n):
    command = sys.stdin.readline().split()
    if command[0] == 'push':
        stack.push(int(command[1]))
    elif command[0] == 'pop':
        print(stack.pop())
    elif command[0] == 'empty':
        print(stack.empty())
    elif command[0] == 'top':
        print(stack.top())
    elif command[0] == 'size':
        print(stack.size())

10773번

• https://www.acmicpc.net/problem/10773
• 입력값이 들어오면 stack에 push하고 0이 입력될 때 마다 stack에서 pop한 뒤, stack 값들의 합계를 출력하면 되는 문제다.

import sys
k = int(input())

stack = []
for i in range(k):
    n = int(sys.stdin.readline())

    # 0이 입력될 경우
    if n == 0:
        stack.pop()
    # 다른 입력값이 들어왔을 경우
    else:
        stack.append(n)

print(sum(stack))

9012번

• https://www.acmicpc.net/problem/9012
• 괄호 입력값을 차례대로 스택에 쌓다가 ')'이 들어오면 stack의 마지막 값을 확인 한 뒤 '('이면 stack에서 pop을 한다. 그 후 모든 문자열을 확인하고 스택이 비어있으면 올바른 괄호 문자열, 비어있지 않으면 올바르지 않은 괄호 문자열이다.

t = int(input())
map_ = {'(':')'}

for i in range(t):
    s = list(input())
    stack = []
    for letter in s:
        if stack and stack[-1] in map_ and map_[stack[-1]] == letter:
            stack.pop()
        else:
            stack.append(letter)

    if stack:
        print('NO')
    else:
        print('YES')

4949번

• https://www.acmicpc.net/problem/4949
• 9012번과 비슷하나, 문자열에 괄호가 아닌 문자가 섞여있고, 소괄호와 대괄호가 섞여있다. 나는 문자열을 스캔하면서 대괄호 혹은 소괄호 일때는 스택에 push하고, )나 ]가 들어왔을 때, 스택의 마지막값을 확인해서 (나 [이면 스택에서 pop하는 것으로 구현했다.
• 처음엔 대괄호와 소괄호를 각각 다른 스택에 담는 것으로 구현했는데 이 경우 '([)]'와 같은 경우를 걸러낼 수가 없어서 다시 한 개의 스택으로 바꿨다. 괄호 내부의 문자열도 균형잡힌 문자열이어야 한다는 조건을 잊어버리는 실수를 했다.

string = input()
map_ = {'(':')', '[':']'}

while string != '.':
    stack = []
    for s in string:
        if s in ['[', ']', '(', ')']:
            if stack and stack[-1] in map_ and map_[stack[-1]] == s:
                stack.pop()
            else:
                stack.append(s)


    if stack:
        print('no')
    else:
        print('yes')

    string = input()

1874번

• https://www.acmicpc.net/problem/1874
• 숫자를 입력받아 입력받은 값이 push되지 않은 값보다 크면, 해당 입력값이 나올때까지 stack에 push하고 입력값을 pop한다. push와 pop을 할때마다 answer 리스트에 '+'와 '-'를 삽입한다. 그러나 입력받은 값이 push되지 않은 값보다 작을 경우 push를 통해서는 해당 값을 찾을 수 없으므로 is_false 변수를 1로 바꿈으로써 불가능한 경우라는 것을 표시한다. 마지막단에서 answer을 출력할 때는 is_false가 1일 경우 'NO'를 출력하고 0일 경우 한줄마다 '+'와 '-'를 하나씩 출력한다.
• 최소 한번의 push는 해야하므로 answer엔 '+'를 넣어놓았고 stack에는 1을 넣어놓았다. push되지 않은 수를 뜻하는 p는 2부터 시작하는 것으로 했다.

n = int(input())
answer = ['+']
stack = [1]
is_false = 0
p = 2

for i in range(n):

    k = int(input())

    if not stack:
        stack.append(p)
        answer.append('+')
        p += 1

    while stack[-1] != k:
        if stack[-1] < k:
            stack.append(p)
            answer.append('+')
            p += 1
        elif stack[-1] > k:
            is_false = 1
            break

    stack.pop()
    answer.append('-')

if is_false == 1:
    answer = ['NO']

for i in answer:
    print(i)

17298번

• https://www.acmicpc.net/problem/17298
• 파이썬 알고리즘 인터뷰에서 나온 '일일 온도'(https://littledatascientist.tistory.com/17?category=981837) 문제와 비슷하다고 느꼈다. 값 대신 인덱스를 스택에 쌓으면서 전보다 큰 값이 나올 경우 stack의 마지막 인덱스의 해당 값이 현재 값보다 클때까지 pop한다. 그 후 answer 리스트에는 pop된 인덱스마다 현재의 값을 저장한다.
• 스택에 인덱스를 push한다는 아이디어가 중요한 것 같다.

n = int(input())
A = list(map(int, input().split()))
answer = ['-1'] * n
stack = []

for i, cur in enumerate(A):
    while stack and cur > A[stack[-1]]:
        last = stack.pop()
        answer[last] = str(cur)
    stack.append(i)
print(' '.join(answer))