태야

<내 코드>

n = int(input())
memo = [0 for _ in range(101)]

for i in range(0, 4):
    memo[i] = 1
for j in range(4, 6):
    memo[j] = 2

for _ in range(n):
    m = int(input())
    for k in range(6, m+1):  # 6 ~ m-1
        memo[k] = memo[k-1] + memo[k-5]

    print(memo[m])

피보나치 수열과 비슷한 맥락으로 규칙을 찾아 점화식을 세우면 간단하게 풀 수 있었다.

인덱스 0번 ~ 4번까지는 1과 2로 넣어주고 그 다음부터는 점화식을 통해 값을 구해나가는 구조였다. 인덱스 값을 0번째 부터 설정해서 뒤에서 조금 헷갈린거 말고는 크게 어렵지 않았다.

<내 코드>

n = int(input())
memo = [0 for i in range(n+1)]
memo[1] = 1
for i in range(2, n+1):
    memo[i] = memo[i-1]+memo[i-2]

print(memo[-1])

처음에 재귀호출을 통해 풀었을 때, 예상대로 시간초과가 났다. 

Bottom-up은 바닥에서 올라오는 것, 즉, 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것이다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 문제를 풀 수 있다. 두 번째 피보나치 수를 구하는 문제와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 구하는 문제를 풀 수 있다....이걸 반복하면 n번째 피보나치 수를 구할 수 있다.

동적 계획법이란?

어떤 문제를 풀기 위해 그 문제를 더 작은 문제들로 나누고, 작은 문제들에서 구한 해를 어딘가에 저장한 다음 활용해 문제를 해결하는 알고리즘 설계 기법이다. DP는 이름처럼 다이내믹한 프로그래밍이라는 거리가 멀다. 단순히 붙여진 이름일 뿐이라고 한다.

분할 정복 방식과 차이점

DP의 문제 접근 방식은 기본적으로 '분할 정복 알고리즘(Divide and Conquer)'과 비슷하다. 두 경우 모두 문제를 부분으로 나누어 각 부분 문제의 답을 계산하고, 이 값을 이용해 원래 문제를 해결하는 과정이다. DP와 분할 정복의 차이는 부분 문제로 나누는 방식에 차이가 있다. DP는 작은 문제들이 반복적으로 사용되며 (즉, 답이 바뀌지 않음) 반대로 동적 계획법은 작은 문제가 중복이 발생하지 않고 단순히 나누어 푸는 방법이다.

DP 문제의 해결 순서

1. 큰 문제를 작은 문제로 나눈다.

2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다.

3. 작은 문제의 도출 값을 메모하고, 큰 문제를 풀어나갈 때 작은 문제가 반복되면 메모한 값을 이용한다. (Memoization방식)

DP의 조건

1. 작은 문제가 반복, 중복이 일어나는 경우

2. 같은 문제의 값은 매번 같다.

여기서 반복적으로 중복이 일어난 부분이 있다. 원으로 표시한 부분만 아니라 F(4)와 F(3)을 구하기 위해 모두 F(2)를 계산해야한다. 이런 식으로 매번 다 계산을 하면 시간적으로 비효율적이다. 그래서 DP방식을 이용해 메모이제이션을 통해 값을 활용해서 문제를 해결하면 훨씬 빠른 계산이 가능해진다.

<내 코드>

def binarySearch(M, tree):
    start = 1
    end = max(tree)

    while start <= end:
        leng = 0
        mid = (start + end) // 2

        for i in tree:
            if i >= mid:
                leng += i - mid

        if leng >= M:
            start = mid + 1
        else:
            end = mid - 1

    return end


N, M = map(int, input().split())
tree = list(map(int, input().split()))

sortTree = sorted(tree)
print(binarySearch(M, sortTree))

이분 탐색 알고리즘을 이용해서 푸는 문제다. 알고리즘만 알고 있으면 생각보다 간단한 문제였다. 같은 코드로 채점 했는데 pypy3는 588ms가 걸리고 python3는 2984ms 가 걸리면서 다소 큰 차이가 있었다. 

 이분 탐색 알고리즘 - 파이썬

이분 탐색은 값을 비교할 때마다 찾는 값이 있을 범위를 절반씩 좁히면서 탐색하는 효율적인 알고리즘이다. 이분 탐색에서 중요한 것은 '이미 정렬된 데이터'에서 값을 비교하면 찾는다는 것이다. 따라서 순차 탐색처럼 처음부터 하나씩 하는 것이 아니라 정렬된 데이터에서 기준점을 잡고 반으로 줄여나가며 찾는 것이기에 훨씬 효율적이고 빠른 알고리즘이다.

이분 탐색은 실생활에서 '책'을 떠올리면 쉽게 이해할 수 있다. 우리는 책을 이용해 원하는 것을 찾을 때 첫 페이지부터 찾는 것이 아니라, 중간쯤 쪽수를 찾아 펼친 다음 범위를 좁혀나가며 계속 찾아나간다. 원하는 페이지가 펼친 페이지보다 뒤에 있다면 앞쪽은 찾을 필요 없이 바로 뒤쪽부터 찾게 된다.

예제

def binary_search(a, x):
    start = 0
    end = len(a)-1

    while start <= end:
        mid = (start + end) // 2
        if(x == a[mid]): 	# 원하는 값 발견!
            return mid 
        elif (x > a[mid]): 	# 찾는 값이 더 크면, 오른쪽으로 범위를 좁혀 탐색
            start = mid + 1
        else:			# 찾는 값이 더 작으면, 왼쪽으로 범위를 좁혀 탐색
            end = mid - 1
            
    return -1			# 찾지 못했을 때

a = [1, 4, 9, 25, 36, 49] # 정렬된 자료
print(binary_search(a, 36)) # 5
print(binary_search(a, 12)) # -1

<내 코드>

n = int(input())
A_num = list(map(int, input().split()))
sorted_A = sorted(A_num)

m = int(input())
M_num = list(map(int, input().split()))


def binary_search(M, sorted_A):
    start = 0
    end = len(sorted_A)-1

    while start <= end:
        mid = (start + end) // 2

        if(m == sorted_A[mid]):
            return print(1)
        elif (m > sorted_A[mid]):
            start = mid + 1
        else:
            end = mid - 1
    return print(0)


for m in M_num:
    binary_search(m, sorted_A)

이분 탐색 알고리즘 문제다. 이분 탐색은 미리 정렬된 리스트에서 값을 찾아나가는 알고리즘이다. 정렬된 자료에서 중앙값을 찾은 다음 찾으려는 값과 비교한다. 중앙값이 더 크면 찾으려는 값이 오른쪽에 있는 것이기에 오른쪽으로 범위를 좁히고, 중앙값이 더 작다면 왼쪽으로 범위를 좁혀 찾아나간다. 비교하는 값이 존재한다면 1을 프린트하고, 없다면 0을 프린트한다.

<내 코드>

import sys
n = int(sys.stdin.readline())
nums = []


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


def pop():
    if(nums):
        return nums.pop()
    else:
        return -1


def size():
    return len(nums)


def empty():
    if(not nums):
        return 1
    else:
        return 0


def top():
    if(nums):
        return nums[-1]
    else:
        return -1


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

<내 코드>

n = int(input())
dots = []
for i in range(n):
    dots.append(list(map(int, input().split())))

dots = sorted(dots, key=lambda x: (x[1], x[0]))

for i in dots:
    print(*i)