Awesome

https://www.acmicpc.net/problem/10816

참고) 파이썬에서 이 문제를 이분탐색으로 풀면 시간초과가 발생한다.

import sys


# 처음으로 key와 같거나 큰 값이 나타나는 위치를 찾는다
def lowerBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if nList[mid] <= key:
            end = mid
        elif nList[mid] < key:
            start = mid + 1
    return end


# 처음으로 key보다 큰 값이 나타나는 위치를 찾는다
def upperBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if nList[mid] <= key:
            start = mid + 1
        elif key < nList[mid]:
            end = mid
    return end


n = int(sys.stdin.readline())
nList = list(map(int, sys.stdin.readline().split()))  # 상근이 갖고 있는 카드 리스트
m = int(sys.stdin.readline())
mList = list(map(int, sys.stdin.readline().split()))  # 찾아야 할 카드 리스트
nList.sort()

for i in mList:
    ret = upperBound(0, n, i) - lowerBound(0, n, i)
    print(ret, end=' ')

앞서 Lower bound 이진 탐색에 대해 알아보았다. 

https://awesomeroo.tistory.com/30

이번에는 Upper bound 이진 탐색이다. Upper bound 이진 탐색은 처음으로 큰 값이 나타나는 위치를 찾는다.

먼저 일반적인 binary search 코드이다.

Lower bound에서도 그랬지만, Upper bound와의 코드 비교를 위해서 올린다.

def binarySearch(start, end, key):
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] > key:
            end = mid - 1
        elif lst[mid] < key:
            start = mid + 1
        elif lst[mid] == key:
            return 1
    return 0


lst = [0, 1, 2, 3, 3, 5, 6, 7, 8]
print(binarySearch(0, len(lst)-1, 3))

그리고 Upper bound binary search.

def upperBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if lst[mid] == key:
            start = mid + 1
        elif lst[mid] < key:
            start = mid + 1
        elif key < lst[mid]:
            end = mid
    return end
    
lst = [0, 1, 2, 3, 3, 5, 6, 7, 8]
print(upperBound(0, len(lst), 6))

이번에도 upper bound에서는 일반 바이너리 서치와 같은 세 가지 if문이 등장한다.

1. lst[mid] == key

2. lst[mid] < key

3. key < lst[mid]

먼저 1번을 보자. upper bound는 key보다 큰 값이 나오는 위치를 찾아야 하므로, 

lst[mid]가 key와 같다면 그 값은 포함시킬 필요가 없다. 따라서 start를 mid에서 하나 증가한 값으로 변경한다.

2번. key가 lst[mid]보다 크다면, 마찬가지로 key보다 큰 값을 찾아야 하기 때문에 key보다 작은 lst[mid]는 다음 탐색 범위에 포함시킬 필요가 없다. 그래서 start를 mid에서 하나 증가한 값으로 변경한다.

3번. key가 lst[mid]보다 작을 때를 보자. mid가 너무 큰 것이므로 end를 작게 해줘야 하는데, lst[mid]가 key보다 처음으로 큰 값(원하는 값)일 수도 있으므로 lst[mid]를 포함시키기 위해 end=mid가 된다.

return end 하는 이유는, start = end가 되는 순간 start와 end가 정답이 되기 때문이다.

또한 함수를 처음 콜하는 부분에서 end가 len(lst)-1이 아니라 len(lst)가 되는 이유는,

리스트를 끝까지 살폈는데 답이 안 나온다면 마지막으로 살폈던 위치를 반환할 것이기 때문이다. 그 때 len(lst)를 반환해서 답이 없음을 알아보기 위함이다. 

먼저 이진 탐색 코드.

def binarySearch(start, end, key):
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] > key:
            end = mid - 1
        elif lst[mid] < key:
            start = mid + 1
        elif lst[mid] == key:
            return 1
    return 0
    
lst = [0, 1, 2, 3, 3, 5, 6, 7]
print(binarySearch(0, len(lst)-1, 7))

Lower bound 이진 탐색이란 

찾고 싶은 key 값과 같은 값이 나타나는 첫 위치를  찾거나,

같은 값이 없으면 큰 값이 나타나는 첫 위치를 찾는 방법이다.

def lowerBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if lst[mid] == key:
            end = mid
        elif key < lst[mid]:
            end = mid
        elif lst[mid] < key:
            start = mid + 1
    return end
    
lst = [0, 1, 2, 3, 3, 5, 6, 7]
print(lowerBound(0, len(lst), 7))

범위 설정에 있어서 이진 탐색과 비교했을 때 이해가 안되서 애먹었다.

일부러 이해하기 쉽도록 ==, <, > 세 가지 케이스로 나누었다.

먼저 2번째 줄, 보통의 이진 탐색은 조건을 while start <= end 로 잡는다.

하지만 lower bound는 while start < end 로 잡는다.

그 이유는 일반 이진 탐색은 start == end가 되었을 때도 그 값이 찾고자 하는 key였는지 살피고 나서 찾았으면 1을 리턴하고 못 찾았으면 0을 리턴하든지 해야 하는데,

lower bound는 start == end가 되었으면 바로 그 위치를 리턴하면 되기 때문이다. start == end가 되는 순간 그 값이 key와 같은 값이거나 처음으로 큰 것이 나타나는 위치이기 때문이다. 그래서 start == end 는 while이 진행될 조건으로 포함시킬 필요가 없다.

다음 if 문을 보자.

일반 이진 탐색에서의 세 가지 if문을 보자.

1. lst[mid] == key

2. key < lst[mid]

3. lst[mid] < key

먼저 3번은 일반 이진 탐색과 같다고 보면 된다. 

lower bound는 key와 같거나 더 큰 값을 찾아야 하므로 key가 더 크다면 start를 높여서 최소한 같은 값이라도 찾을 수 있도록 범위를 좁혀주어야 한다.

하지만 1. lst[mid] == key 일 때는?

원하는 key가 나오긴 했지만, 똑같은 값이 더 왼쪽에서 나타날 수도 있다.

따라서 이 위치를 포함해서 더 작은 위치에서 이 값이 등장하지는 않는지 다시 한번 살펴야 하는 것이다.

2. key < lst[mid]도 마찬가지이다. key가 lst[mid]보다 작긴 하지만, 무작정 바이너리 서치처럼 end = mid - 1 할 수 없는 이유는 lst[mid]가 key보다 처음으로 큰 값일 수 있기 때문이다.

마지막, lowerBound 함수를 호출하는 부분을 보자.

보통 이진 탐색이라면 함수를 호출할 때 start를 0으로, end를 len(lst)-1로 둘 것이다. 왜냐? 배열은 0부터 시작이니까.

하지만 lower bound 이진 탐색의 경우, end를 len(lst)로 두었다.

그 이유는 리스트 안에 원하는 값이 없었을 경우, 즉 원하는 key보다 작은 값들만 있었을 경우 

마지막 while문을 돌 때 start와 end가 len(lst)가 됨으로써

len(lst)를 반환하게 되고, 리스트에 존재하지 않는 인덱스를 반환했기 때문에 리스트에 key가 없다! 는 것을 알기 위함이다.

(원하는 key보다 큰 값들만 있었을 경우에 리턴값은 0이다. lower bound가 뭔지 생각해보자)

https://www.acmicpc.net/problem/1920

import sys


def binarySearch(start, end, num):
    mid = (start + end) // 2
    if nList[mid] == num:
        return 1
    if start > end:
        return 0
    if num > nList[mid]:
        start = mid + 1
    elif num < nList[mid]:
        end = mid - 1
    return binarySearch(start, end, num)


n = int(sys.stdin.readline())
nList = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
mList = list(map(int, sys.stdin.readline().split()))

nList.sort()

for i in mList:
    print(binarySearch(0, n-1, i))

https://www.acmicpc.net/problem/2630

처음에는 시작점, 종료점 각각을 매개변수로 넣었다가 더 헷갈려서

시작점의 row, col, 한 변의 길이만을 매개변수로 두었다.

시작하는 row, col 위치만 안다면 각각에 +n만 해서 범위를 잡을 수 있기 때문이다.

어째 분할과 정복보다는 위치 잡는 게 더 헷갈렸던 문제.

import sys


# (시작점 row, 시작점 col, 한 변의 길이)
def devideAndConquer(r, c, n):
    global white, blue
    color = board[r][c]
    for row in range(r, r + n):
        for col in range(c, c + n):
            if board[row][col] != color:
                devideAndConquer(r, c, n//2)  # 0, 0
                devideAndConquer(r, c + n // 2, n//2)  # 0, 1
                devideAndConquer(r + n // 2, c, n//2)  # 1, 0
                devideAndConquer(r + n // 2, c + n // 2, n//2)  # 1, 1
                return
    if color == B:
        blue += 1
    elif color == W:
        white += 1

N = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
W, B = 0, 1
white, blue = 0, 0
devideAndConquer(0, 0, N)

print(white)
print(blue)

https://www.acmicpc.net/problem/12865

다이나믹 프로그래밍을 풀 때는 표를 그리는 경우가 많았다.

표를 그린다는 것 = 컴퓨터로 생각하면 Memoization이기 때문인 것 같다.

표를 그려보고, 그 표를 컴퓨터가 만들어낼 수 있도록 일반화하는 것이 중요하다.

하지만 정답을 해결할 수 있는 표를 만들어 낼 수 있다면 이미 그 문제를 풀 수 있다는 뜻이겠지...

그러니까 어떤 경우를 순회하면서 무엇을 저장해야 하는가? 메모이제이션 아이디어를 생각하는 게 쟁점이다.

이 문제도 마찬가지이다.

지금까지 for문을 돌렸기 때문에 무작정 for문으로 시작하려 한다면 애먹을 가능성이 높다. (내가 그랬다.)

for문으로 해결하면 안 된다는 뜻이 아니라,

먼저 '표'와 같은 해결 방법을 찾아야 한다는 뜻이다.

소스코드는 아래와 같지만,

아이디어를 이해한다면 사실 소스코드는 직접 만들 수 있을 것이고

나중에 경계값 처리 등을 실수했을 때나 보면 된다.

import sys
N, K = map(int, sys.stdin.readline().split())  # N은 물건 갯수, K는 최대 무게
item = []  # 입력으로 주어질 아이템 무게/가치 리스트
for i in range(N):
    item.append(list(map(int, sys.stdin.readline().split())))
W, V = 0, 1  # item 리스트에서 무게를 0, 가치를 1로 가리키면 헷갈리므로 그냥 이렇게 쓸 것이다

knapsack = [[0 for _ in range(K+1)] for _ in range(N)]  # 최대 가치를 저장한 표. 문제 해결의 열쇠

for index, wv in enumerate(item):
    for weight in range(1, K+1):
        if wv[W] > weight:
            knapsack[index][weight] = knapsack[index-1][weight]
        else:
            knapsack[index][weight] = max(knapsack[index-1][weight], wv[V] + knapsack[index-1][weight-wv[W]])

print(max(map(max, knapsack)))

https://suri78.tistory.com/2

를 참고했다. 표를 그리면서 설명을 잘 해놓으신 것 같다.

https://www.acmicpc.net/problem/1912

원트에 풀었지만 다시 생각해보니 생각해볼 만한 점이 있어 포스팅한다.

처음에 생각한 점화식은

이번에 들어가야 할 값 = max(이전까지의 연속합+현재값, 현재값, 현재값+바로 이전 값)

이었다.

왜 현재 값+바로 이전 값을 계산해야 된다고 생각했는지는 잘 모르겠다.

무조건 2개를 선택해서 연속합을 만들어야 한다면, 그렇게 될 것 같다.

하지만 문제에서는 1개 이상만 선택하면 된다고 했으니, 점화식은

이번 연속합 = max(바로 이전까지의 연속합+현재값, 현재값) 이 된다.

이 뜻은,

현재 값에 연속합을 더하는 것이 낫냐? 아니면 이전 연속합을 더하는게 손해냐? 를 묻는 것이다.

예를 들어 주어진 수열이 -1, -1, 55 이라고 생각할 때,

연속합+현재값은 53이고 현재 값은 55이므로 최대 연속합은 55이다.

이전 연속합들을 데리고 갈지, 아니면 더하면 오히려 손해이므로 버리고 갈 지를 결정한다고 생각하면 된다.

주석친 곳을 보면 

maxSum = max(seq[now]+subsum[now-1], seq[now]) 라고 되어 있는데, 이것이 볼드처리한 점화식과 같다.

seq는 주어진 수열, subsum은 연속합을 저장한 배열이다.

하지만 이 max 를 보면, seq[now]가 양쪽에 공통되어 있다는 사실을 알 수 있는데.

그렇다면 max(subsum[now-1], 0)이 된다.

이것을 풀어서 생각해보면 

이전까지의 연속합이 0을 넘느냐? 이다.

이전까지의 연속합이 0을 넘으면, 현재 값이 양수든 음수든 무조건 더하는게 이득이므로 데리고 간다. 라는 뜻이다.

그래서 본문과 같이 if문으로 바꿔봤더니 속도가 더 빨라졌다.

import sys
N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split())) # 주어진 수열
subsum = [seq[0]]  # 연속합을 저장할 리스트

for now in range(1, N):
    # 연속 합에 현재 값을 더하는 게 낫냐? OR 현재 값에서 다시 시작하는 게 낫냐?

    #maxSum = max(seq[now]+subsum[now-1], seq[now])
    #subsum.append(maxSum)

    if subsum[now-1] > 0:
        subsum.append(seq[now] + subsum[now-1])
    else:
        subsum.append(seq[now])


print(max(subsum))

https://www.acmicpc.net/problem/2565

선행문제: 11053번

LIS 기초 문제인 11053번을 풀어봤다면 어려울 것이 없는 문제이다.

뭔가 복잡할 것 같지만, 어느 순간에 전깃줄이 교차하는지를 생각해보면 된다.

전깃줄은 '다른 애들이 증가하고 있는데 혼자 감소하면' 교차한다.

즉, 다른 애들은 증가하고 있는데 지들만 감소하고 있는 아이들을 찾으면 되는데,

이것은 가장 긴 부분 증가 수열을 뺀 나머지들이다. (증가수열에 속하지 않으면 감소하는 애들일 것이므로)

파이썬 코드이다.

import sys
import operator

numCable = int(sys.stdin.readline())
cable = []

for i in range(numCable):
    start, end = map(int, sys.stdin.readline().split())
    cable.append([start, end])  # start는 왼쪽 전봇대, end는 오른쪽 전봇대
cable.sort(key=operator.itemgetter(0))  # 기준을 왼쪽으로 삼고 정렬한다. 

increasing = [1]  # 각 원소마다 증가 부분 수열 갯수를 저장

for now in range(1, numCable):
    candidates = [0]
    for before in range(now):
        if cable[before][1] < cable[now][1]:
            candidates.append(increasing[before])
    increasing.append(max(candidates)+1)

maxIncreasing = max(increasing)
cableToCut = numCable-maxIncreasing
print(cableToCut)