[TIL] Algorithm - 분할정복 + 스택

1. 이분 탐색 개념을 이용한 문제 풀이 (11053번 - 가장 긴 증가하는 부분 수열)

import sys

# A의 크기
N = int(sys.stdin.readline())
# 수열
A = list(map(int, sys.stdin.readline().split()))

# https://namu.wiki/w/최장%20증가%20부분%20수열#s-3.2 참고

def LIS() :
    # d[i] = A[i]를 마지막 값으로 가지는 가장 긴 증가부분 수열 길이
    d = [A[0]]
    for i in range(1, len(A)) :
        # d에 저장된 가장 마지막 값보다 현재 값이 크면
        if d[-1] < A[i] :
            d.append(A[i])
        # 마지막 값보다 현재 값이 작으면 
        # -> 0 ~ len(d)-1 사이에서 현재값보다 작은 값 중 가장 큰 값을 찾는다  -> 이분탐색
        else :
            min, max = 0, len(d)-1
            save = 0
            while min <= max :
                mid = (min + max) // 2
                if d[mid] < A[i] :
                    min = mid + 1
                else :
                    max = mid -1
                    save = mid
            d[save] = A[i]
    # 최종적으로 구해야하는 값       
    print(len(d))

LIS()

• 나무위키 알고리즘 참고[https://namu.wiki/w/최장%20증가%20부분%20수열#s-3.2]
• 설명을 직접 보며 구현하면서 느낀점은 이분탐색 중 인덱스 관리가 매우 중요하다는 것이다.
• 약간의 오류도 결과에 매우 큰 영향을 미치므로 어떤 것을 이분탐색하는지 확실하게 생각하고 할것!

---

2. 분할 정복(divide and conquer)

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법
ex) merge sort

• 분할 : 현재 문제와 동일하되 입력의 크기가 더 작은 다수의 부분 문제로 분할
• 정복 : 부분 문제(재귀 대상)를 재귀적으로 풀어 정복, 부분 문제가 충분히 작으면(base case) 직접적인 방법으로 해결
• 결합 : 부분 문제의 해를 결합해 원래 문제의 해 도출

점화식(Recurrence)
: 더 작은 입력에 대한 자신의 값으로 함수를 나타내는 방정식 또는 부등식

※ 점화식을 푸는 방법 ※
1. 치환법 (substitution method)
    : 한계를 추측한 후 그 추측이 옳음을 증명하기 위해 수학적 귀납법 사용
    <참고> https://rninche01.tistory.com/entry/알고리즘-기초-04-치환법Substitution-Method

2. 재귀트리 방법 (recursion-tree method)
    : 점화식을 각 노드가 재귀 호출의 해당 레벨에 따른 비용을 나타내도록 만든 트리로 변환 후 점화식을 푼다.
      이를 위해 합의 한계를 구하는 기법을 이용
      <참고> https://rninche01.tistory.com/entry/알고리즘-기초-05-재귀-트리Recursion-Tree-Method

3. 마스터 방법 (master method)
    : T(n) = T(n/b) + f(n) 이라는 점화식을 푸는 기본 지침 제공
    <참고> https://johngrib.github.io/wiki/master-theorem/

---

1. 2630번 - 색종이 만들기

import sys

N = int(sys.stdin.readline())
# 파란색 = 1, 하얀색 = 0
paper = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

blue, white = 0, 0

'''
현재 영역 내에 모두 같은 값이 존재하는지 판별하는 함수
row : 시작 행
col : 시작 열
size : 얼만큼의 크기를 확인할 것인지
'''
def isEquals(row, col, size) :
    current = paper[row][col]
    for i in range(row, row+size) :
        for j in range(col, col+size) :
            if current != paper[i][j] :
                return False
    return True

# 색종이의 개수를 세는 함수
def paperCount(row, col, size) :
    global blue, white
    
    if isEquals(row, col, size) : 
        if paper[row][col] == 0 :
            white += 1
        else :
            blue += 1
    else :
        newSize = size // 2
        paperCount(row, col, newSize)
        paperCount(row, col+newSize, newSize)
        paperCount(row+newSize, col, newSize)
        paperCount(row+newSize, col+newSize, newSize)

paperCount(0, 0, N)
print(white)
print(blue)

• 분할 : 종이의 크기를 1/2배로 줄인다.
• 정복 : 현재 영역 안에 있는 모든 수가 동일하면 완료
• 결합 : global 함수를 이용한 count 값 사용

---

2. 1629번 - 곱셈

import sys

A, B, C = map(int, sys.stdin.readline().split())

# https://velog.io/@grace0st/곱셈-백준-1629번-파이썬 참고

def mult(A, B) :
    if B == 1 :
        return A % C
    else :
        tmp = mult(A, B//2)
        # 지수가 짝수일 경우
        if B % 2 == 0 :
            return (tmp * tmp) % C
        # 지수가 홀수일 경우
        else :
            return (tmp * tmp * A) % C

print(mult(A, B))

1. 지수 법칙
   : A^m+n = A^m * A^n

2. 나머지 분배 법칙
    : (A*B) % C = (A%C) * (B%C) % C

• 분할 : 지수 B를 반으로 줄인다.
• 정복 : A를 1번 곱하는 경우 A % C 계산
• 결합 : B의 짝수, 홀수에 따라 최종 식 계산

---

3. 6549번 - 히스토그램에서 가장 큰 직사각형

import sys

# https://hooongs.tistory.com/330 참고

'''
직사각형의 최대 넓이를 구하는 함수
n : 입력받은 직사각형 수
histogram : 직사각형 높이 정보가 들어있는 리스트
'''
def rectangle (n, histogram) :
    stack = []
    result = 0
    for i in range(n) :
        # 스택의 가장 위에 있는 값이 현재 높이 보다 클 경우
        while len(stack) != 0 and histogram[stack[-1]] > histogram[i] :
            t = stack.pop()
            if len(stack) == 0 :
                width = i
            else :
                width = i - stack[-1] - 1
            result = max(result, histogram[t]*width)
        stack.append(i)
    
    # 스택에 아직 값이 남아있을 경우
    while len(stack) != 0 :
        t = stack.pop()
        if len(stack) == 0 :
            width = n
        else :
            width = n - stack[-1] -1
        result = max(result, histogram[t]*width)
    
    return result
        
'''
입력값 : (직사각형의 수 + 직사각형들의 높이)가 한줄에 주어진다.
입력값[0] = 직사각형의 수
입력값[1:] = 직사각형의 높이 
'''
while True :
    histogram = list(map(int, sys.stdin.readline().split()))
    if histogram[0] == 0:
        break
    print(rectangle(histogram[0],histogram[1:]))

위 코드는 분할 정복 방법을 사용한 것은 아니다.
스택을 이용하여 문제풀이를 먼저 해보았다.
여기서 스택은 가장 낮은 높이의 인덱스부터 쌓이도록 만들었다. 

<참고 > https://hooongs.tistory.com/330

우선 다음 문제들도 좀 풀고 이 문제를 세그먼트 트리와 분할 정복으로 푸는 방법에 대해 공부해봐야겠다.

세그먼트 트리(Segment Tree)
: 여러 개의 데이터가 존재할 때 특정 구간의 합을 구하는데 사용하는 자료구조
▶ 리프(leaf) 노드 : 배열의 그 수 자체
▶ 리프 노드가 아닌 노드 : 왼쪽 자식과 오른쪽 자식의 합 저장

<참고> https://book.acmicpc.net/ds/segment-tree

---

3. 스택 (Stack)

데이터를 임시 저장할 때 사용하는 자료구조로 후입선출(Last-In First-Out) 방식

• push : 스택에 데이터를 넣는 작업
• pop : 스택에서 데이터를 꺼내는 작업

https://ko.wikipedia.org/wiki/스택

1. 스택 구현하기 (10828번 - 스택)

import sys

N = int(sys.stdin.readline())
stack = []

def push(x) :
    stack.append(x)

def empty() :
    if len(stack) == 0 :
        return 1
    return 0

def pop() :
    if empty() == 1 :
        return -1
    return stack.pop()

def size() :
    return len(stack)

def top() :
    if empty() == 1 :
        return -1
    return stack[-1]
    

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

---

2. 10773번 - 제로

import sys

K = int(sys.stdin.readline())
list = []

for i in range(K) :
    input = int(sys.stdin.readline())
    if input == 0 :
        list.pop()
    else :
        list.append(input)

print(sum(list))

---

3. 9012번 - 괄호

import sys

testcase = int(sys.stdin.readline().strip())

def isVPS(input) :
    stack = []
    
    for i in input :
        if i == "(":
            stack.append(i)
        elif i == ")" :
            if stack :
                stack.pop()
            else :
                return "NO"
    if stack :
        return "NO"
    else :
        return "YES"

for i in range(testcase) :
    input = list(sys.stdin.readline())
    print(isVPS(input))

---

4. 2493번 - 탑

import sys

N = int(sys.stdin.readline())

tower = list(map(int, sys.stdin.readline().split()))

# 왼쪽부터 탑의 높이를 읽어가기 위해 사용
# 최댓값을 저장할 스택
stack = []

# 수신탑의 인덱스를 저장할 리스트
# 인덱스는 1부터 시작한다.
result = []

for i in range(N) :
    # 스택에 값이 있을 경우
    while stack :
        # 현재 타워 높이 <  왼쪽에 있는 타워 중 가장 높은 타워 높이 
        if tower[stack[-1]] > tower[i] :
            result.append(stack[-1]+1)
            break
        # 아닐경우 -> 현재 타워가 더 높으므로 이 이후에는 스택에 있는 마지막 타워의 높이는 사용 불가
        else :
            stack.pop()
    # 스택에 값이 없을 경우 : 수신이 가능한 탑이 없다.
    if not stack :
        result.append(0)
    # 현재 타워가 수신할 수 있는 경우가 존재하므로 삽입
    stack.append(i)

for i in result :
    print(i, end=" ")

---

앞의 스택 3문제는 보다 스택의 기본을 동작을 알 수 있는 문제였고, 4번째 문제는 스택의 특성인 LIFO를 활용해야하는 문제였다.
머리로는 알고 있었지만 활용하는 것은 다른 문제인 것같다. 

위의 탑 문제인 경우에는 리스트의 오른쪽부터 접근하여 완전 탐색을 할 수도 있었지만 → O(n^2)
스택을 이용하여 왼쪽부터 접근하여 빠르게 문제를 해결할 수 있었다. → O(n)

이와 같이 자료구조에 대해 알면 문제를 좀 더 쉽게 접근할 수 있으므로 자료구조에 대해 다시한번 공부해야겠다.