스터디룸

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #241 Different Ways to Add Parentheses

문제 풀이

주어진 연산식에 괄호를 삽입할 수 있는 모든 경우의 수에 대해 삽입하고 그에 대한 연산 결과를 리턴해야 한다. 여기서 알 수 있는 점은 주어진 연산자가 +, -, * 밖에 없으므로 0으로 나누는 결과를 고려할 필요가 없다.

분할 정복으로 해결할 수 있는데 몇 가지 생각이 필요하다. 우선 괄호를 어떻게 놓아서 분할하느냐의 문제다. 이에 대해 재귀 호출로 연산자를 기점으로 나눠 좌우측으로 구분하고 분할된 부분이 단순 숫자일 경우 최소 단위에 도달함을 의미하므로 그대로 리턴한다. 리턴된 결과값들을 연산자로 계산하여 다시 그 결과값을 리턴한다. 이 과정을 모든 글자에 대해 순회하면 모든 경우의 수에 대해 탐색할 수 있겠다.

• 리턴할 결과값들을 저장할 리스트 생성
• 각 글자에 대해 iterate
• 만약 탐색 좌표의 글자가 +, -, * 중 하나로 연산자에 해당된다면 연산자를 기준으로 좌/우측으로 나누어 재귀 호출 (분할)
• 만약 입력이 단순 숫자라면 그대로 리턴 (부분 문제의 최소 단위)
• 리턴 받은 좌, 우측 결과에 대해 연산자를 적용하여 계산 (eval 연산, 정복)
• 맨 처음 호출위치까지 리턴받아 종료

python 코드

class Solution:
    def compute(self, l1, l2, exp):
        result = []
        for i in l1:
            for j in l2:
                result.append(eval(str(i) + exp + str(j)))
        return result
    def diffWaysToCompute(self, expression: str):
        if expression.isdigit():
            return [expression]
        result = []
        for i, exp in enumerate(expression):
            if exp in "+-*":
                left = self.diffWaysToCompute(expression[:i])
                right = self.deffWaysToCompute(expression[i + 1:])
                result.extend(self.compute(left, right, exp))
        return result

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #406. Queue Reconstruction by Height

문제 풀이

그리디 알고리즘으로 해결할 수 있는 문제다. 우선 다른 원소들과 비교했을 때 키가 클수록 다른 원소에 영향을 받지 않으므로 키에 대해 내림차순으로 정렬하고 동일 키에 대해 앞 사람들 중 자신의 키 이상의 사람의 수가 적을 수록 앞쪽에 위치하며 뒤의 사람에 대해 영향을 받지 않으므로 앞자리 사람이 적은 오름차순으로 정렬한다.

리턴할 새 배열을 생성하고 정렬된 원소들에 대해 차례대로 자신의 키 이상인 앞사람의 수를 인덱스 삼아 삽입한다.

자신의 키 이상인 앞사람의 수를 기준으로 삽입하는 이유는 우선 자신보다 크거나 같은 사람이 이미 줄을 선 시점에서 자신의 키 이상인 앞사람의 수는 그 시점에서의 좌표를 의미하기 때문이다.

python 코드

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        sol = []
        people.sort(key=lambda x: (-x[0], x[1]))
        for p in people:
            sol.insert(p[1], p)
        return sol

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 3020. 개똥벌레

문제 풀이

주어진 범위에 대해 완전 탐색을 진행하나 해당 구간에서 부딪히는 장애물의 수를 구하는 과정을 이진 탐색을 사용해 $O(log\ n)$으로 줄임으로써 전체 시간복잡도를 $O(nlog\ n)$으로 만들어야 한다. 특히 이 문제는 binary search의 lower bound와 upper bound를 제대로 이해하면 바로 해결할 수 있었다.

• 항상 홀수 번은 석순, 짝수 번은 종유석이고 N은 언제나 짝수이므로 절반으로 나눠 두 배열에 별도로 입력받는다.
• 구간 h는 높이 h-1과 h 사이를 의미하므로 탐색은 1부터 H까지 진행한다.
• 따라서 1부터 H까지 순회한다고 할 때 석순은 h와 같거나 큰 개수이고(lower bound) 종유석은 H - [종유석 길이] < h (upper bound)를 만족하는 개수이다.
• bound를 다루는 두 개의 함수를 둘 필요 없이 석순의 경우 h번째 구간일 때 h-1에 대한 upper bound를 판별하면 종유석과 함께 같은 함수를 사용할 수 있다.
• 부딪히는 종유석, 석순의 개수는 각 장애물 개수 - upper bound 좌표가 되겠다.
• 모든 구간에 대해 순회하면서 최소값을 갱신하여 카운트한 뒤 결과를 리턴하면 된다.

python 코드

import sys
input = sys.stdin.readline

N, H = map(int, input().split())
suck, jong = [], []
for _ in range(N // 2):
    suck.append(int(input()))
    jong.append(int(input()))

def search(arr, val): # upper bound 판별
    l, r = 0, len(arr)
    while l < r:
        mid = l + (r - l) // 2
        if arr[mid] > val:
            r = mid
        elif arr[mid] <= val:
            l = mid + 1
    return len(arr) - l # val보다 작은 값 제외한 나머지

suck.sort()
jong.sort()
min_v, sol = N, 0
for h in range(1, H + 1):
    s = search(suck, h - 1) + search(jong, H - h)
    if s < min_v:
        min_v = s
        sol = 1
    elif s == min_v:
        sol += 1
print(min_v, sol)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

그리디 알고리즘(Greedy Algorithm)?

"매 선택마다 현재 시점에서 당장 최적인 답을 선택하여 적합한 결과를 얻는다"는 개념으로 출발하는 알고리즘이다. 즉, 각 단계에서 선택한 결과가 전체적으로도 최선의 결과임을 바라는 알고리즘이다. 다만 그리디 알고리즘이 적용될 수 없는 경우가 있다.

마시멜로 실험을 그리디 알고리즘으로 접근한다고 해보자. 마시멜로 실험에서 지금 당장 1개를 먹거나 지금은 기다렸다가 2개를 먹을 수 있다고 가정할 때, 그리디 알고리즘은 매 순간의 최적해를 구하므로 기다려서 현재 상태가 0이 되는 것보다 먹음으로써 현재 상태를 1로 만드는 것이 최적이라 결정한다.

그리디 알고리즘의 적용 조건

그리디 알고리즘을 적용할 수 있기 위해서 문제는 두 가지 속성을 지녀야 한다.

• 탐욕 선택 속성(Greedy Choice Priority)

  현재의 선택이 이후 선택에 영향을 주지 않음을 의미한다.

• 최적 부분 구조(Optimal Substructure)

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

활동 선택 문제(Acticity Selection Problem)

교실 할당(Classroom Assignment) 문제라고도 부른다. 한정된 공간에서 최대한 많은 수의 수업을 배정해야 한다.

위 그림대로 9개의 수업과 시작 시각 $s_i$와 종료 시각 $f_i$가 주어진다고 하자. 종료 시각이 빠른 순서대로 배치하면 교실의 가용 횟수가 항상 최적이 된다. 종료 시각이 빠르면 종료 시각 이후 뒤의 수업에 영향을 주지 않기 때문이다. 각 수업을 수직선으로 나타내보자.

따라서 $a_1,\ a_3,\ a_6,\ a_8$이 최대로 가용할 수 있는 조합이 된다. 시간 측면으로 보면 $a_2,\ a_5,\ a_7,\ a_8$이 12로 최대이지만 마시멜로 실험처럼 $a_1$을 선택하지 않고 $a_2$를 취하는 건 그리디 알고리즘으로 해결할 수 없다. 따라서 선택한 수업들 중 마지막 수업의 종료 시각과 이후 수업의 시작 시각이 겹치는 지 여부만 검사하여 1번의 탐색으로 해결이 가능하기 때문에 시간복잡도는 $O(n)$이다.

python 코드

activity = [[1, 1, 3], [2, 2, 5], [3, 4, 7], [4, 1, 8], [
    5, 5, 9], [6, 8, 10], [7, 9, 11], [8, 11, 14], [9, 13, 16]]
sol = []
for act in activity:
    if not sol:
        sol.append(act)
        continue
    if act[1] >= sol[-1][2]:
        sol.append(act)
print(sol)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #76 Minimum Window Substring

문제 풀이

슬라이딩 윈도우를 쓰긴 하는데 그 범위가 가변적이란 점에서 투 포인터 쪽으로 생각함이 맞지 싶다. T에 들어있는 알파벳이 최소한 전부 포함되어 있음을 보장해야 한다는 점에서 필요한 글자와 들어간 글자의 현황을 명확히 해야 한다.

• T를 기준으로 Counter 객체를 생성한다.
• T의 길이만큼은 최소한 포함해야 하므로 missing 변수에 len(T)를 저장한다.
• 결과값을 갱신하여 저장할 start, end 포인터를 0으로 설정하고 좌측 포인터 left도 0으로 설장한다. 이후 조건 충족 시마다 최소 범위 탐색을 위해 left를 우측으로 이동시킬 예정이다.
• 모든 글자에 대해 탐색을 진행하고 그 좌표를 right이라 하자. 다만 파이썬은 A[left:right]의 경우 A[right - 1] 원소까지 조회하므로 right는 1부터 시작한다.
• 각 글자에 대해 만약 Counter의 값이 1이상이면 해당 글자가 T에 포함된 글자이며 윈도우 내에 모자란 상태임을 의미한다. 따라서 이 글자를 포함시킴에 따라 missing 값에서 1을 빼고 counter[S[right]]의 값도 1을 빼준다.
• 만약 missing이 0이 되어 T의 모든 알파벳이 윈도우 안에 들어왔다면 문제의 조건에 따라 최소 범위를 찾기 위해 left를 우측으로 옮겨야 한다. left < right 범위 내에서 현재 left 좌표의 글자를 빼려면 counter[S[left]]의 값이 음수여야 한다.(0인 상태면 left 좌표를 윈도우에서 뺄 경우 T의 알파벳 포함 조건에 위배됨) counter[글자]의 값이 음수라면 잉여 글자이므로 탐색 좌표의 counter값이 0이 될 때까지 반복한다.
• left 포인터를 우측으로 옮기는 과정이 끝나면 start와 end를 갱신해야 하는지 체크한다. 만약 end가 0으로 아직 한번도 갱신이 되지 않았거나 right - left <= end - start로 저장된 정답이 탐색 범위보다 크다면 갱신한다.
• 모든 순회가 끝나면 S[start:end]를 리턴한다.

python 코드

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        missing = len(t)
        counter = collections.Counter(t)
        left = start = end = 0
        for right in range(1, len(t) + 1):
            missing -= counter(s[right - 1]) > 0
            counter[s[right]] -= 1
            if missing == 0:
                while left < right and counter[s[left]] < 0:
                    counter[s[left]] += 1
                    left += 1
                if not end or right - left <= end - start:
                    start, end = left, right
                    missing += 1
                    counter[s[left]] += 1
                    left += 1
        return s[start:end]