アルゴリズム学習1週目

目次
1.BOJ 1010号架橋
2.BOJ 2504かっこの値
3.PostOrder反復による実現

1.BOJ 1010号架橋

西側にはNサイト、東側にはMサイトがありますが、接続可能であれば個数の質問ができます.

解法

よく考えてみると、これは2つの組み合わせ、つまり組み合わせを求める問題であることがわかります.

これが最初に考えた組み合わせです.
しかし、不要なセクタ演算+除算演算が含まれているため、この場合は望ましくない.
組合せ式はいろいろありますが、この係数で解いてみます.

みんな何度も会ったことがあります.
わかりやすいと言えば

コードで表現すると.

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

次のように定義できます.
また、次の式を使用します.

r>N/2の場合は求めずに処理できる
この機能を利用して、ダイナミックゲームを使って問題を解くことができます.

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かっこまでの値
どうやって点火式を手に入れたの?

まずケースを考えてみましょう

ケースは2つ考えられます.

1.大かっこ

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

2.かっこが2つある場合

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

DP式は次のように考えられます.

1.大かっこ

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

2.カッコが2つある場合、-midはstartとendの間の任意の値です。

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

この式を用いてDP配列を埋め込む
まず、次のカッコの値を求めるには、カッコの値を求めます.
したがって、最小かっこ「()」と「[]」を求める必要がある場合.このとき、カッコ列の長さは2です.
次に、かっこ列の長さは4です.次は6です.
このとき、括弧の長さが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を創造的に体現している.
PostOrderは再帰的に実現され,容易に作成できる.

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

反復式に整理する場合はstackを使用する必要があります.
実際、私は初めてstackをC、C++として使い、Pythonを使い、基本資料構造リストだけで実現できます.

どうやって実現するか考えてみましょう。

出力値を考慮すると、

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

このほか、まずサブノードを参照します.
このとき,まず左側のサブアイテムを探索する.
では、stackでDFSを作ったほうがいいです.
この場合、スタックがどのように変化しているかをよく追跡する必要があります.

Leafノードの場合、出力されます.

サブノードが存在し、参照されていないサブノードがある場合は、親ノードをスタックに入れてサブノードに移動します.

の左側と右側をナビゲートした場合、出力(=True)ノードが出力され、スタックがポップアップされ、上部ノードに戻ります.

コードで見ると分かりやすいです.

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