Coding 공부

def dfs(W,H):
    if W == 0:
        return 1
    if dp[W][H]:
        return dp[W][H]
    dp[W][H] = dfs(W-1,H+1)
    if H>0:
        dp[W][H] += dfs(W,H-1)
    return dp[W][H]



while True:
    N = int(input())

    if not N:
        break
    dp = [[0]*31 for _ in range(N+1)]

    print(dfs(N,0))

재귀적으로 푸는 방식이다.

한알로 먹는 먹을수 있는 개수를 W, 반알로 먹을 수 있는 개수를 H로 두고 재귀적으로 풀면 된다.

원래 들어온 W,H에서 기본적으로 W가 남아있으면, 한알을 꺼내먹을수 있기에 W-1,H+1로 함수를 실행시켜준다.

그리고 만약 H가 있다면, 반알을 먹을수도 있으므로, W,H-1로 함수를 실행시켜준다.

그러다가 한알짜리 알약이 전부 떨어지면, 남은경우는 반알을 전부 먹는것이므로 return 1을 해주며, 중단해준다.

이렇게 해서 전체 날짜에서 먹을수 있는 날짜를 구하면 된다.

dp = 31*[0]
dp[1] = 1
dp[0] = 1


for n in range(2,31):
    for i in range(n):
        dp[n] += dp[i]*dp[n-i-1]

while True:
    N = int(input())
    if not N:
        break
    print(dp[N])

 위와 같은 형태의 문제를 카탈란 수라고 한다. 자세한 설명은 아래의 사이트에서 읽어보면 된다.

   카탈란 수 설명 출처 : suhak.tistory.com/77

카탈란 수의 점화식을 이용해서 쉽게 푸는 방법도 있다.

from collections import deque
def bfs():
    global N,M
    stack = deque()
    stack.append((N,M))
    visited = set()
    visited.add((N,M))
    while stack:
        x,y = stack.pop()
        if x == 1 and y == 1:
            return 'yes'
        if dict_array.get(x*y):
            for nodes in dict_array[x*y]:
                if nodes not in visited:
                    visited.add(nodes)
                    stack.append(nodes)
    return 'no'

N = int(input())
M = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dict_array = {}
for x in range(N):
    for y in range(M):
        if dict_array.get(arr[x][y]):
            dict_array[arr[x][y]].append((x+1,y+1))
        else:
            dict_array[arr[x][y]] = [(x+1,y+1)]

if dict_array.get(N*M):
    print(bfs())
else:
    print('no')

 처음으로 풀어본 영어로 된 문제이다. 영어로 되어있는 것을 제외하고는 그렇게 어렵지 않은 문제이고, python으로 통과한 사람들이 적다보니 통과시간에 걸릴까 걱정했는데 처음에는 아슬아슬하게 통과했다.

제한시간 2초인데 1.9초가 떴었다.

문제를 봐보면 일반적인 방탈출 게임 같아보인다. 하지만 여기서는 상하좌우로 움직이던 일반적인 bfs가 아닌 현재 내가 밟은 위치에 있는 값에 따라 움직일 수 있는 위치가 달라진다.

그 방법은 현재 내가 밟고있는 index에 위치한 값의 약수 쌍의 좌표로만 옮겨갈수 있다

예를 들면 

3 10 8 14

1 11 12 12

6 2 3 9

문제에 있는 3*4 배열을 봐보면

처음 시작 위치는 (1,1)이다. 그 위치에 있는 값은 3이므로, 3의 약수는 (1,3) (3,1)로 갈 수 있다.

그러면 다음 위치는 (1,3) 이나 (3,1)이 될수 있는데

만약 (1,3)이라한다면 (1,3)에 있는 값은 8 이다. 8의 약수는 (1,8) (2,4),(4,2),(8,1)이 존재할 수 있는데,

(4,2),(8,1),(1,8)은 범위를 넘어가므로, 갈 수 없다.

그러므로 (2,4)로 갈 수 있다.

이런식으로 jump를 해서 우측 최하단에 도착하는 게임이다.

도착이 가능하면 yes 불가능하면 no를 출력해주면 된다.

처음에는 약수를 구하는 생각을 해봤는데, 주어진 행렬의 최대가 1000*1000이다. 거기에 주어지는 최대값은 100만이다.

100만에 대한 모든 약수를 구하다보면  10억번 정도의 연산이 필요로 할 것 같아서, 폐기했다.

그 다음으로 생각한 방법이 위의 풀이이다.

역으로 올라가보자는 것이다.

우리가 (N,M)에 도착하기 위해서 무조건 배열 내에 N*M인 값이 존재해야한다.

1. N*M을 가지고 있는 위치를 찾아간다.

2. 그 위치에 도달할 수 있는 값을 찾아서 또 이동한다.

위와 같은 로직을 생각했다.

즉, 위의 예제로 설명하면

(3,4)에 도착하기 위해서는 12의 값이 필요한데, 이 12를 가진 발판의 위치는 (2,3),(2,4)이다.

(2,3)에 도착하기 위해서는 6의 값이 필요한데 6이 존재하는 위치는 (3,1)이다.

(2,4)에 도착하기 위해서는 8의 값이 필요한데 8이 존재하는 위치는 (1,3)이다.

(3,1),(1,3)에 도착하기 위해서는 3의 값이 필요한데 3이 존재하는 위치는 (1,1) 아니면 (3,3)이다.

이렇게 해서 풀 수 있다.

from collections import deque
def bfs():
    global N,M
    stack = deque()
    stack.append((N,M))

    while stack:
        x,y = stack.pop()
        if x == 1 and y == 1:
            return 'yes'
        if dict_array.get(x*y):
            for nodes in dict_array[x*y]:
                stack.append(nodes)
            del dict_array[x*y]
    return 'no'

N = int(input())
M = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dict_array = {}
for x in range(N):
    for y in range(M):
        if dict_array.get(arr[x][y]):
            dict_array[arr[x][y]].append((x+1,y+1))
        else:
            dict_array[arr[x][y]] = [(x+1,y+1)]

if dict_array.get(N*M):
    print(bfs())
else:
    print('no')

이 코드는 위의걸 개선한 코드이다. 방문표시를 하기위해서 visited를 쓰는대신 한번 방문한 곳은 전부 지워버렸다.

from collections import deque
import bisect
import sys
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    stack = deque()
    stack_dict = dict()
    for _ in range(int(input())):
        command,val = input().split()
        val = int(val)
        if command == 'I':
            if stack_dict.get(val):
                stack_dict[val] += 1
            else:
                bisect.insort_left(stack,val)
                stack_dict[val] = 1
        else:
            if val == 1:
                if stack:
                    last_number = stack[-1]
                    if stack_dict[last_number] == 1:
                        stack_dict.pop(last_number)
                        stack.pop()
                    else: 
                        stack_dict[last_number] -= 1
            else:
                if stack:
                    first_number = stack[0]
                    if stack_dict[first_number] == 1:
                        stack_dict.pop(first_number)
                        stack.popleft()
                    else:
                        stack_dict[first_number] -= 1
    if stack:
        print(stack[-1],stack[0])
    else:
        print('EMPTY')

정렬된 행렬일때 쓸 수 있는 bisect 라이브러리를 이용해서, 이진탐색 후, deque에 넣어주었다.

뺄때 매번 insert, pop을 하면 연산시간이 오래걸리므로, dictionary로 개수를 세주었고, dictionary가 0이 될때 pop을 해주었다.

number_list = [True]*1003002
number_list[0] = False
number_list[1] = False
for number in range(2,1003002):
    if number_list[number]:
        for j in range(number+number,1003002,number):
            number_list[j] = False

N = int(input())
flag = False
for find_number in range(N,1003002):
    if number_list[find_number]:
        string_number = str(find_number)
        if len(string_number)%2:
            if len(string_number) != 1:
                a = string_number[:N//2]
                b = string_number[N//2+1::-1]
                if a == b:
                    result = find_number
                    break
            else:
                result = find_number
                break
        else:
            a = string_number[:N//2]
            b = string_number[N//2::-1]
            if a == b:
                result = find_number
                break
    

print(result)

소수를 구한뒤 앞뒤로 같은지 확인해주면 되는 문제였다.

그리고 최대 입력값 100만일때 나오는 소수& 팰린드롬 수는 1003001 이므로 거기까지만 돌리면 된다.

import math
a=input()
k={}
for i in range(10):
    k[i]=0
for j in a:
    j=int(j)
    k[j]+=1
result1=0
result2=0
for index,value in k.items():
    if index==6 or index==9:
        result2=k[9]+k[6]
    else:
        if result1<value:
            result1=value
            

result2=math.ceil(result2/2)
if result2>result1:
    print(result2)
else:
    print(result1)

간단한 문제이다. 6,9일때와 아닐때를 구분해서 개수를 세준뒤에 둘중 큰걸 출력해주면 된다.

N = input()
room_number = [0]*10

for number in N:
    room_number[int(number)] += 1
a = room_number[6]+room_number[9]
b = (room_number[6]+room_number[9])//2
room_number[6],room_number[9] = b,a-b

print(max(room_number))

이런식으로 구현해도 된다.

a= int(input())
def cal(a):
    temp = []
    for i in a:
        temp.append(i-1)
        if i%3==0:
            temp.append(i/3)
        if i%2==0:
            temp.append(i/2)
    return temp
cnt=0
minimum=[a]
while True:
    if a==1:
        print(cnt)
        break
    temp=minimum[:]
    minimum=[]
    minimum=cal(temp)
    cnt+=1
    if min(minimum)==1:
        print(cnt)
        break

유명한 DP 문제이다.

각각의 연산을 한뒤에 새롭게 옮겨가는 LIST를 따로 만들어주고, 그걸 갱신하면서 횟수가 어느회차인지 알면된다.

N = int(input())
number_list = [N]
cnt = 0
flag = False
if N == 1:
    print(0)
else:
    while True:
        new_number = []
        for numbers in number_list:
            if numbers == 1:
                flag = True
                break

            if not numbers%3:
                new_number.append(numbers/3)
            if not numbers%2:
                new_number.append(numbers/2)
            new_number.append(numbers-1)
        if flag:
            print(cnt)
            break
        cnt += 1
        number_list = new_number[:]

똑같은데 이런식으로도 만들수 있다.

print(''.join(sorted(input())[::-1]))

정렬을 해준뒤 역으로 출력해준다.

T=int(input())
cnt=0
for test_case in range(T):
    sp=list(input())
    total=[]
    for i,v in enumerate(sp):
        if i!=len(sp)-1:
            if sp[i]!=sp[i+1]:
                total.append(sp[i])
        else:
            total.append(sp[i])
    for k in total:
        if total.count(k)>1:
            break
    else:
        cnt=cnt+1
print(cnt)

풀이 방식은 다음과 같다.

 마지막 위치를 제외한 현재위치와 다음위치를 비교를 해서 같지 않을때에 그때 현재위치의 문자열을 total에 넣어준다.

마지막 위치는 total에 넣어준다.

그리고 난뒤에 total을 반복문을 돌리면서 그 개수가 1개를 초과하면, 그룹 단어가 아니므로 멈춰주고, 한번도 만나지 않으면, 그룹 단어이므로 cnt를 늘려준다.