99-3週間航行し、パスワードを取得


Today I learned
2022/01/24
回顧録
1/24
航行99、アルゴリズム2週目
教材:Pythonアルゴリズムインタビュー
第12章図表
1.理論
バックトラック
太陽を探している間に、現在のパスが太陽ではないように見える場合は、戻りません.
これは、符号化が重複文の数を減らし、効率を向上させることを意味する.
これを枝切りといいます.不要な部分を取り除き、できるだけ正しい方向に進むことを意味します.
通常は、不要な経路を事前に遮断して、状況の数を減らすことができますが、N!の場合、最悪の場合でも指数関数時間が必要になるため、処理できない問題があります.どれだけうまく剪定すれば効率が決まるか.
まとめると、backtrackingは、特定の条件を満たす場合にのみ、可能な限り考慮されます.
すなわち,答えが可能か否かを判断し,そうでなければ探索を行わずに剪定枝を遡及と見なす.
主に、問題解決では、DFSなどを使用して、すべての状況で答えが見つからない場合を定義し、条件文で実装できます.この場合、ブラウズを停止して前の状況に戻り、他の状況でナビゲートすることができます.
👍 ポストトラッキング技術の発展の見通しを確定する
どのノードに希望があるか、すなわちどのノードが有害かを判断し、希望がないと判断した場合、そのノードの前の(親)ノードに戻り、次のサブノードに戻ります.
有害である可能性がある場合を希望(希望)と呼び,到達不可能なノードを剪定(剪定)する.
2.質問
https://www.acmicpc.net/problem/9095
3. MySol
  • Back Tracking
  • def solution(pwLength, numOfChar):
        result = []
        visited = []
    
        def dfs_stack(start):
    
           for node in range(start, numOfChar):
    
                visited.append(charList2[node])
    
                if len(visited) == pwLength:
                    result.append(visited[:])
                    visited.pop()
                    continue
    
                else:
                    dfs_stack(node+1)
    
                visited.pop()
    
           return
    
        dfs_stack(0)
    
        def pwCheck(lists):
    
            for i in lists:
                jaUm = 0
                moUm = 0
                for char in i:
                    if char in 'aeiou':
                        moUm+=1
                    else:
                        jaUm+=1
                if jaUm>=2 and moUm>=1:
                    print(''.join(i))
    
        pwCheck(result)
    
        return
    
    
    if __name__ == '__main__':
    
        lists = input().split(" ")
        pwLength = int(lists[0])
        numOfChar = int(lists[1])
        charList2 = list(input().split())
        #charList = ['a','t','c','i','s','w']
        charList2.sort()
        solution(pwLength, numOfChar)
    
        # for i in result:
        #     temp = ''.join(i)
        #     print(temp)
    
    
    4.学んだこと
  • この問題はDFSと再帰関数の理解に非常に役立つ問題である.
  • 5.総評
    回帰、DFSトレーニング