끄적끄적

유형 : 스택

풀이과정

 Stack이란 후입선출하는 자료구조로 이를 이용하여 괄호의 균형을 체크한다.

 stack은 그냥 list를 선언하여 활용했는데, 어차피 맨 뒤의 것만 지울것이기 때문이다(list.pop()). 만약 앞의 것을 지워야한다면 deque를 선언하여 활용하는 것이 좋다.

 1. 문자열의 앞에서 부터 확인하는데, 왼괄호('(','[')를 만나면 stack에 넣어준다.

 2. 오른괄호를 만나면 stack의 맨 뒤의 원소를 확인하여 둘이 짝이면 stack의 맨 뒤의 것을 제거한 후 넘어가고(list.pop()), 짝이 맞지 않는다면 균형이 잡히지 않은 괄호이기 때문에 'no'를 리턴해준다.

입출력

 문제자체는 굉장히 쉬운 문제인데, 이상한데서 고생을 했다. 바로 입출력 문제인데, Python3에서 input()으로 입력을 받을 경우에는 뒤에 개행문자가 없지만 sys.stdin.readline()으로 입력을 받을 경우에는 뒤에 개행문자가 추가되어 입력이 들어온다. 따라서 이를 유의해야한다.

Python Code

주어진 N을 5와 3만을 사용하면서 가장 적은 수의 5와 3으로 나타내는 문제이다.

풀이과정

 $N = 5x + 3y$ 라 할때, $x$가 클수록 $x+y$가 작아질 것이다. 예를 들어, 30이라면 5를 6개 쓰는 것이, 3을 10개 쓰는것 보다 낫다.

1. 위에 썼듯, 5를 최대한 많이 사용하기 위해서 먼저, N이 5로 나누어 지는지 확인한 후,  나누어 진다면 answer에 N을 5로 나눈 몫을 더한 후 반환한다.

2. N이 5로 나누어지지 않는 경우에는, N에서 3을 빼준 후, answer 에 1을 더한다(3을 한번 사용).

3. N이 0이 될때까지 1~2 과정을 반복하되, N이 음수가 되는 경우에는 N이 5와 3만으로 표현되지 않는 것이므로 -1을 반환한다.

Python Code

유형 : dp

카드 n장을 살 때, 지불할 수 있는 최대 금액을 구하는 문제이다.

풀이과정

 카드 i 장을 구매하는데 필요한 금액을 dp[i] 이고, 카드 n장이 들어있는 팩의 가격이 p[n]라 하면, dp[i]는 아래와 같다.

 dp[i] = dp[i-n] + p[n]

 가능한 모든 n에 대하여 dp[i]가 최대값이 되도록 update해나가면 된다.

Python Code

유형 : bfs

풀이과정

1. ripen을 deque로 선언한 후, 토마토들의 정보를 읽으며 익은 토마토의 인덱스 (i,j)를 넣는다.

2. ripen에서 popleft로 하나씩 꺼내가며, 토마토의 이웃을 체크하고 익지 않은 토마토가 있으면 상태를 1로 바꾸어주고 ripen에 넣는다. 이때, time step을 세기위해, 각 time step마다, ripen에서 꺼내기 전에, ripen에 몇개의 요소가 들어있는지 체크해두고 popleft로 체크된 수 만큼만 빼고, 새로 넣는 토마토는 오른쪽으로 넣는다.

3. ripen이 빌때까지 2를 반복한 후, 장애물의 숫자와 익은 토마토의 숫자의 합이 m*m 일 경우에는 시간을, 아닐경우에는 -1을 반환한다.

Python Code

* 편의를 위해서 tomato는 (m+2)*(m+2) 행렬로, 가장자리를 -1(장애물)로 채웠습니다.

문제풀기

카카오 코드 페스티벌 2018 본선 문제

 입출금 로그를 보고 잘못된 부분이 있는지, 없다면 최소 충전금액은 얼마인지 알아내는 문제이다.

풀이과정

 먼저, a, b를 list로 가지고 있을 필요없이 입력받고 바로바로 처리하면 효율적으로 문제를 해결할 수 있다.

 minB는 0이 아닌 b의 최솟값이며, lastB는 이전 step의 b값이 된다.

 a+lastB가 음수인 경우에는 충전이 필요하며 충전 금액 temp는 아래와 같이 주어진다.

 temp = b - a - lastB

 충전금액은 최소충전금액의 배수만 가능하므로, 최소충전금액(변수 pay)은 충전액들의 최소 공배수가 되고, 이를 해결하기 위해 pay 변수를 계속해서 pay변수와 위의 temp 변수의 최대공약수로 갱신해준다.

 로그가 잘못 되었을 조건은 아래와 같다.

 1. 각 step에서 잔액 b는 전 step에서의 잔액과 현 step에서의 입출금 a의 합으로 주어져야하는데, b = lastB + a 를 만족하지 않으면 그 로그는 잘못된 로그이다.

 2. 최소충전금액이 pay이므로, 입출금 후의 잔액의 최솟값 minB는 pay보다 작아질 수 없다. 따라서 minB < pay 인 경우 그 로그는 잘못된 로그이다.

Python Code

문제풀기

유형 : 그리디

빨리 끝나는 회의부터 처리해야 한다. 이때, 끝나는 시간이 똑같은 회의의 경우, 시작 시간이 빠른 회의부터 처리한다.

코드

import sys

n=int(sys.stdin.readline())
times = []
for _ in range(n):
    times.append(tuple(map(int,sys.stdin.readline().split())))
  
times.sort()
times.sort(key=lambda x: x[1])
now,ans=0,0
for time in times:
    if time[0]>=now:
        ans+=1
        now=time[1]
print(ans)

정렬

 위의 코드에서는 times.sort()로 회의 시작 시간을 기준으로 정렬을 한 후, 회의 종료 시간을 기준으로 한번 더 정렬을 함으로써 위에서 언급한 규칙을 만족시켰다.

 하지만, 아래와 같이 comparator를 직접 정의함으로써 한번에 정렬할 수도 있는데, 내장함수로 두번 정렬하는 위의 방법이 훨씬 효율적이었다. ( 위의 방법 : 메모리 44944kb, 시간 328ms, 아래의 방법 : 메모리 50360kb, 시간 552ms)

from functools import cmp_to_key

def compare(x, y):
    if x[1] < y[1] :
        return -1 
    elif x[1] > y[1] :
        return 1
    else: 
        if x[0] < y[0] :
            return -1
        else:
            return 1
times.sort(key=cmp_to_key(compare))

문제풀기

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

유형 : dp

 LIS(Longest Increasing Subsequence)로 알려진 유명한 문제이다. 주어진 배열에서 몇 개의 요소들을 제거하여 만들 수 있는 가장 긴 증가하는 수열을 찾는 문제로, 배열이 [1,3,5,2,1,6] 으로 주어진 경우 [1,3,5,6]이 가장 긴 증가하는 부분 수열이 된다.

 아래의 풀이는 나무위키의 최장 증가 부분 수열을 Python으로 구현한 것이다.

 풀이를 살펴보면, 먼저 시간복잡도를 O(nlogn) 으로 하기 위해서는 이진탐색을 활용해야하므로, 먼저 이진탐색을 정의한다. bin_search 함수는 이진탐색으로 원하는 값보다 같거나 큰 가장 작은 수의 인덱스를 반환한다. dp[i]는 i+1번째 요소까지를 고려했을 때 가장 긴 부분 수열의 길이가 되며, p_i[i]는 길이가 i인 증가하는 부분수열의 마지막 수(가장 큰 수)이며, 이 값을 가장 작게 유지하는 것이 나중에 유리하다는 것을 알 수 있다.

풀이과정

1. bin_search를 통하여 p_i에서 a보다 크거나 같은 가장 작은 수의 인덱스를 찾는다(idx).

2-1. 이 idx가 배열 p_i의 길이와 같다면, 이는 가장 큰 수가 들어왔다는 것으로, 가장 긴 증가하는 부분 수열의 뒤에 붙으므로써 가장 긴 증가하는 부분 수열의 길이가 1 증가하게 된다. 즉, dp에는 idx 값을 넣어주고, p_i 에는 a 값을 추가로 넣어준다.(p_i의 길이가 늘어났다는 것은, dp의 최댓값 역시 늘어났다는 것을 의미한다.) 

2-2. idx가 배열 p_i의 길이보다 작다면, 이는 a 값을 마지막으로 하는 증가하는 부분 수열은 기존의 부분 수열보다 길이가 크지 않다는 것이고, idx는 a를 마지막으로 넣었을 때 만들수 있는 가장 긴 부분 수열의 길이를 나타낸다. 이 때, 기존의 길이가 idx인 부분 수열의 마지막 보다는 a가 작거나 같으므로 p_i[idx]의 값을 a로 바꾸어준다.

3. 이렇게 모든 요소에 대하여 반복한 후 dp의 최댓값을 반환한다.

시간복잡도

 1의 과정(이진탐색)의 시간 복잡도가 logn이고, 이 과정을 모든 요소에 대하여 반복해야 하므로 총 n번 진행하면 된다. 따라서 시간복잡도는 O(nlogn)이 된다.

코드

import sys

#t보다 크거나 같은 가장 작은 수 반환
def bin_search(arr, t):
    l=0
    r=len(arr)
    if t > arr[-1]:return len(arr)
    elif t<arr[0]:return 0
    mid = (l+r)//2
    while l<=r:
        if arr[mid] > t:
            r=mid-1
        elif arr[mid] < t:
            l = mid+1
        else:
            return mid
        mid = (l+r)//2
    return mid+1

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

dp=[0]
p_i=[0]

for a in a_i:
    idx = bin_search(p_i,a)
    # 가장 큰 수가 들어왔다
    if idx == len(p_i):
        p_i.append(a)
    else:
        p_i[idx] = a
    dp.append(idx)
print(max(dp))

문제 풀기