가전제품 이것저것 이야기

메모이제이션 강좌를 보셨나요? 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법입니다. 메모이제이션이 동적 프로그래밍 중 하나입니다.

알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많습니다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍입니다.

dfs(깊이우선탐색)

한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 

- 재귀로 구현한다.

- 한번 방문한 곳은 다시 가지 않기 위해 check 배열 사용

BFS(너비우선탐색)

인접 노드부터 탐색

- 큐를 사용한다.

- 한번 방문한 곳은 다시 가지 않기 위해 check 배열 사용

www.acmicpc.net/problem/9184

코드

MAX_NUM = 51
dp = [[[0 for i in range(MAX_NUM)] for i in range(MAX_NUM)] for i in range(MAX_NUM)]

def w(a, b, c):

    if a <= 0 or b <= 0 or c <= 0:
        return 1


    if dp[a][b][c]:
        return dp[a][b][c]


    if a > 20 or b > 20 or c > 20:
        return w(20,20,20)

    elif a < b and b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return dp[a][b][c]
    else:
        dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
        return dp[a][b][c]


while True:
    x, y, z = map(int, input().split())
    if x == -1 and y == -1 and z == -1:
        break

    print("w(%d, %d, %d) = %d" %(x, y, z, w(x, y, z)))

문제에서 알려준 함수대로 구현을 먼저하되,

메모이제이션을 이용해서 이미 구한 적 있는 값은 다음 과정을 거치지 않고 바로 반환할 수 있도록 한다.

새로 알게된 문법 )

3차원 리스트 초기화하기 !

MAX_NUM = 51
dp = [[[0 for i in range(MAX_NUM)] for i in range(MAX_NUM)] for i in range(MAX_NUM)]

MAX_NUM을 5로 한다면,

이렇게 된다고 생각하면 된다.

www.acmicpc.net/problem/4949

코드

from collections import deque
deq = deque()

while True:

    s = input()
    flag = 1

    if s[0] == '.':
        break

    for i in range(len(s)):

        if s[i] == '[' or s[i] == '(':
            deq.append(s[i])
        elif s[i] == ']':
            if len(deq) != 0 and deq[len(deq)-1] == '[':
                deq.pop()
            else:
                flag = 0
                break
        elif s[i] == ')':
            if len(deq) != 0 and deq[len(deq)-1] == '(':
                deq.pop()
            else:
                flag = 0
                break

    if flag == 1 and len(deq) == 0:
        print("yes")
    else:
        print("no")

    deq.clear()

새로 알게된 문법 )

deq.clear() 하면 덱 안의 값이 모두 삭제된다.

www.acmicpc.net/problem/5430

코드

n = (int)(input())

for i in range(n):
    funcstr = input()
    list_n = (int)(input())

    de = (str)(input())[1:-1].split(',')
    funcstr = funcstr.replace('RR','')

    if list_n == 0:
        de = []

    r_flag = 0
    flag = 1
    for j in range(len(funcstr)):
        if funcstr[j] == 'R':
            r_flag = not r_flag
        else:
            if len(de) == 0:
                print("error")
                flag = 0
                break

            if r_flag:
                de.pop(len(de)-1)
            else:
                de.pop(0)


    if flag == 1:
        if r_flag:
            de.reverse()
        print('[', end='')
        print(','.join(de), end='')
        print(']')

1. 양 옆의 '['와 ']'를 인덱싱으로 제거하고, 콤마를 기준으로 split() 

de = (str)(input())[1:-1].split(',')

2. 'RR'이면 다시 원상태이기 때문에 replace() 함수로 없애주었다.

funcstr = funcstr.replace('RR','')

3. 줄바꿈없이 print

print('[', end='')

4. 중간중간 콤마를 넣어 join

print(','.join(de), end='')

www.acmicpc.net/problem/1021

파이썬 코드

from collections import deque

n, m = map(int, input().split())

deq = deque(i+1 for i in range(n))
li = list(map(int, input().split()))

sum = 0
for i in range(m):
    diff = deq.index(li[0])
    diff_rev = len(deq) - diff

    if diff == 0:
        li.pop(0)
        deq.popleft()
    elif diff < diff_rev:
        deq.rotate(-diff)
        sum += diff
        li.pop(0)
        deq.popleft()
    else:
        deq.rotate(diff_rev)
        sum += diff_rev
        li.pop(0)
        deq.popleft()

print(sum)

뽑아야 하는 값의 인덱스를 diff로, 전체 deque의 길이에서 diff를 뺀 값을 diff_rev로 놓았습니다.

diff가 0이면 뽑아야 하는 수가 가장 앞에 있다는 의미이므로 리스트와 deque에서 각각 값을 꺼냅니다.

diff 보다 diff_rev가 더 크면 deque를 오른쪽 방향으로 diff_rev 만큼 rotate 시킨 후 값을 꺼냅니다.

반대는 반대로 합니다.