알고리즘 스터디 1주차

목차
1. BOJ 1010번 다리 놓기
2. BOJ 2504 괄호의 값
3. PostOrder iteration으로 구현하기

1. BOJ 1010번 다리 놓기

서쪽에 N개의 사이트,동쪽의 M개의 사이트가 있는데, 이를 연결할 수 있는 경우의 수를 묻는 문제이다.

풀이과정

이는 잘 생각해보면 둘의 Combination, 즉 조합을 구하라는 문제와 같다는 것을 알 수 있다.

가장 먼저 생각해볼 수 있는 Combination을 구하는 식이다.
하지만 이 식의 경우는 불필요한 Factorial 연산 + 나누기 연산이 들어가므로 바람직하지 않다.

Combination은 공식이 다양하게 있는데, 난 이항계수를 이용하여 풀어보았다.

다들 많이 본적이 있는 식이다.

이를 이해하기 쉽게 표현하자면

코드로 표현해보면

DP[i][j] = DP[i-1][j-1] + DP[i-1][j]

다음과 같이 정의할 수 있다.

추가적으로 다음식을 사용하게 되면

r > N/2 인 경우를 굳이 구하지 않고 처리할 수 있다

이를 이용하여 Dynamic Progamming을 사용하여 풀면 간단하게 풀린다.

Code

# 2차원 배열선언

## [[0]*30]*30 <- 이렇게 선언하지마시오... 주의!
answer = [[0 for col in range(31)] for row in range(31)]

def combination(N, M):
	# 가장자리 Case 1
    if N == 1 or M == 0:
        return 1
    
    # 가장자리 Case 2
    if M == 1:
        return N
    
    # 조합 공식
    if M >= N/2:
        M = N - M
    
    # 이미 구한 값이라면 return
    if answer[N][M] != 0:
        return answer[N][M]
    
    # DP Memoization
    answer[N][M] = combination(N-1, M) + combination(N-1, M-1)
    return answer[N][M]

for N, M in input_array:
    print("M Combination N: ", combination(M, N))

BOJ 2504 괄호의 값

괄호로된 문자열이 주어진다.
올바른 문자열이 다음과 같이 정의된다고 한다.

다음의 조건에 맞게 값을 구하라는 문제이다.

풀이 과정

Input의 길이가 1~30이므로 시간에 구애받는 문제는 아닌것으로 보인다.

다양한 풀이가 존재할 수 있겠지만,
난 이 문제를 DP를 이용하여 풀어보았다.

DP 배열은 다음과 같이 정의할 수 있다.

DP[i][j] : i ~ j 까지에서의 괄호열의 값

그럼 점화식은 어떻게 구할 수 있을까?

우선 케이스를 생각해보자

케이스는 두가지로 생각해볼 수 있다.

1. 괄호에 크게 쌓여있는 경우

이 경우에는 괄호 안에 있는 값에 괄호의 종류에 따라 곱셈을 해주어야한다.
Ex) [ A ]인 경우는 곱하기 3 or ( A )인 경우는 곱하기 2
  

2. 두개의 괄호가 붙어있는 경우

이 경우는 두개의 완성된 괄호가 나열되어있는 경우인데, 이 경우는 두 값을 더해주어야한다.
Ex) (A)(B)

그럼 우리는 DP 식을 다음과 같이 구상해볼 수 있다.

1. 괄호에 크게 쌓여있는 경우

DP[start][end] = DP[start+1][end-1] * (2 또는 3)

2. 두개의 괄호가 붙어있는 경우 - mid는 start와 end 사이 어떤 값

DP[start][[end] = DP[start][mid] + DP[mid+1][end]

이 식을 이용하여 DP배열을 채워보자

일단 우리는 작은 괄호 먼저 값을 구해야 다음 괄호의 값을 구할 수 있다.

그래서 가장 작은 괄호열 '()' 와 '[]' 의 경우를 구해야한다. 이 때 괄호열의 길이는 2이다.
그 다음으로 괄호열의 길이는 4이다. 그 다음은 6이다.

이때, 괄호의 길이는 2의 배수라는 것을 알 수 있는데, 이를 활용하여 2의 배수만큼 괄호열의 길이를 늘려 DP 값을 구해야한다.

그럼 길이가 2일때 먼저 구해보자.

길이가 2인 경우, 점화식은 다음과 같이 이루어져 있는데, 이상한 점을 하나 발견할 수 있다.

ex) 인풋이 '[]'일 경우
	DP[0][1] = DP[1][0] * 3

0~1 사이의 길이를 구하는데 1~0 사이의 값이 사용된다.

---

이 문제를 해결하기 위해 간단한 트릭을 사용하였다.

i > j 인 경우 DP배열의 값을 1로 초기화해었다. (이외의 경우는 0으로 초기화)
1로 초기화하면 길이가 2인 괄호열의 경우에도 문제없이 구할 수 있게 된다.

코드는 앞선 경우의 수를 나누어 작성하였다.

Case 1. [A]인 경우

DP[start][end] = DP[start+1][end-1] * 3

Case 2. (A)인 경우

DP[start][end] = DP[start+1][end-1] * 2

Case 3. (A)(B)

DP[start][end] = DP[start][mid] + DP[mid+1][end]

Case 3의 경우는 start와 end 사이를 탐색하여 올바른 괄호열로 이루어진 경우에만 수행한다.

Code

배열 초기화

DP = [[1 if i > j else 0 for col in range(31)] for row in range(31)]

# DP = [[0 for col in range(31)] for row in range(31)]
#
# for i in range(31):
#    for j in range(31):
#        if i > j:
#            DP[i][j] = 1
                       

괄호열의 값 구하기

str = "(()[[]])([])"  # 예시 Input
length = len(str)

for gap in range(2, length+1, 2):
    
    for start in range(length-gap+1):
        end = start + gap -1
        
        if str[start] == '(' and str[end] == ')':
            DP[start][end] = DP[start+1][end-1] * 2
            
        elif str[start] == '[' and str[end] == ']':
            DP[start][end] = DP[start+1][end-1] * 3
            
        for i in range(start+1, end):
            if DP[start][i] > 0 and DP[i+1][end] > 0:
                DP[start][end] = max(DP[start][end], DP[start][i] + DP[i+1][end])

값 확인

print(DP[0][length-1])

Postorder Iteration 구현하기

친구의 부탁으로 트리탐색하는 방법 중 하나인 PostOrder를 Iterative하게 구현해보았다.

PostOrder는 재귀로 구현하면 쉽게 짤 수 있다.

def postorder(root):
	postorder(root.left)
    postorder(root.right)
    print(root.value)

이를 Iterative하게 짜려면 stack을 사용해야한다.

사실 stack을 C, C++로만 사용해서 Python으론 사용해본 적이 처음인데, 기본 자료구조 list만으로도 구현이 가능하였다

어떻게 구현할지 생각해보자..

값을 출력하는 경우를 생각해보면,

1. Leaf 노드인 경우
2. 자식 노드들을 모두 탐색한 경우

이 이외의 경우 외엔 자식노드를 먼저 탐색해야한다.
이때 우선 왼쪽 자식을 먼저 탐색한다.

그럼 stack을 이용해서 DFS를 하는 것이 좋겠다.

이때 stack이 어떻게 변화하는지에 대해서 잘 추적해야한다.

1. Leaf 노드라면 출력한다.
2. 자식 노드가 존재하고 탐색하지 않은 자식노드가 있다면 부모노드를 stack에 넣고 자식 노드로 이동한다.
3. 왼쪽 오른쪽 모두 탐색했다면 (visited==True) 노드를 출력하고 stack을 pop하여 상위 노드로 올라간다.

코드로 보면 더 이해가 쉬울 것이다.

Code

def postorder_iter(root):
    stack = [root]

    while stack:
        current = stack.pop()
        
        # If current is leaf node
        if current.left is None and current.right is None:
            print(current.value)
            current.visited = True
            continue
        
        
        # If left-child exists and not visitied
        if current.left not None and current.left.visited is False:
            stack.append(current)
            stack.append(current.left)
        
        # If right-child exists and not visitied
        elif current.right is not None and current.right.visited is False:
            stack.append(current)
            stack.append(current.right)
        
        else:
            print(current.value)
            current.visited = True