IT/Algorithm5 Dynamic Programming (동적 계획법) Dynamic Programming (DP) - 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법 - 나누어진 문제들은 중복 계산하지 않음 (계산 결과를 저장하여 중복 계산을 제거하는 것이 핵심) - 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 Memoization - 계산한 결과를 배열에 저장 조건 1. Overlapping Subproblems : 문제를 부분 문제로 쪼개고 그 문제의 결과값을 재활용 2. Optimal Substructure : 부분 문제의 최적 결과값을 사용해 문제의 최적 결과를 낼 수 있는 경우 과정 1. 문제의 논리가 작은 논리의 합으로 구성되어 있는지 확인 2. 문제의 변수 파악 3. 변수 간 관계식 만들기 (점화식) 4. Memoization 5. 초기값 확인 6.. 2022. 4. 15. Backtracking이란 Backtracking - 모든 조합을 시도해서 문제의 해를 찾음, 단 해의 조건을 위반하는 경우 끝까지 해를 구하지 않고 그만둠 - 완전 탐색 방법인 DFS, BFS와는 달리, 해의 가능성이 없는 경우를 탐색하지 않고 다음 탐색 진행 - 주로 DFS 탐색 도중 해의 가능성이 없는 노드를 가지치기하는 방식으로 진행 Promising - 해당 노드가 조건에 맞는지를 검사 Pruning (가지치기) - 조건에 맞지 않으면 탐색을 더 이상 진행하지 않고, 바로 다음 노드로 넘어가서 탐색 시간을 절약함 N-Queen - 크기가 N * N인 체스 판 위에 퀸 N 개를 서로 공격할 수 없게 놓는 문제 1. Promising -> 한 행에는 하나의 퀸만 위치할 수 있음, 맨 위부터 차례로 퀸을 배치 -> 수직 방향,.. 2022. 4. 14. [BFS] Breath-First Search (너비 우선 탐색) 목적 - Graph의 모든 Node를 Cycle(순환) 없이 탐색하는 방법 중 하나 - 같은 Node를 다시 탐색하지 않음 - 모든 Node를 한 번씩만 탐색 과정 1. 가장 위의 Node, Root Node에서 시작 2. 맨 위의 Node를 빼서 Queue에 넣은 후, 방문 표시(Visited True 표시) 3. 다음, 빼낸 Node와 바로 인접한 Node들을 빼서 Queue에 넣은 후, 방문 표시 4. 모든 Node들을 탐색할 때까지 3 반복 # pseudocode create a queue Q mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) nei.. 2022. 4. 13. 이전 1 2 다음
