너T야? 나 T(story)야….

완전탐색 - 브루토포스 (exhaustive/brute-force search)을 개선한 기법이다. 후보해 들을 단계적으로 만들어가는 과정에서 후보해들을 평가한다. 만약 한 후보해가 최종해가 될 수 없다고 판단되면 탐색을 멈추고 다른 후보해를 탐색한다. -> 최적화문제와 결정문제 해결이 가능하다 DFS(Depth First Search) 또는 그와 같은 스타일의 탐색을 총칭한다. 되추적(Backtracking) 이란?-어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 부모 노드로 돌아가서 다음 자식 노드에 대한 탐색을 계속한다.  이렇게 가능성을 보고 가지치기를 하며 가능한 것들을 판단한다.  다음 예시로는 순열 생성 되추적이 있다. 이것의 알고리즘은 다음과 같고 Java로는 다음..

이러한 행렬의 곱은 공학수학이나 이산수학에서 충분히 배웠다. 이때 Aik, b kj로 k가 왼쪽 식에는 오른쪽에, 오른쪽은 왼쪽에 적혀 있는건 두개가 같을 경우에 연산이 되기 때문이다. 분할 정복의 아이디어로는 다음과 같다. // r 배열은 행렬들의 행과 열의 수를 저장// i부터 j까지의 행렬을 곱할 때 최소 곱셈 횟수를 반환하는 함수public static int matMult_DC(int[] r, int i, int j) { // 기저 조건: 행렬이 하나일 경우 곱셈이 필요하지 않음 if (i == j) return 0; int minVal = Integer.MAX_VALUE; // 최소 곱셈 횟수를 무한대 값으로 초기화 // i부터 j-1까지의 k를 기준으로 분할하여 최소 곱..

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위한 알고리즘 기법으로, 문제를 작은 하위 문제들로 나누고, 각 하위 문제의 해를 저장하여 필요할 때 다시 사용함으로써 전체 문제를 효율적으로 해결하는 방법이다. DP는 특히 중복되는 하위 문제(subproblems)를 가진 문제에서 매우 유용하다. 즉 앞에서 설명한 분할 계획을 조금 더 효율적으로 할 수 있는 것이다.  동적 계획법의 핵심 개념최적 부분 구조: 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있어야 한다.예를 들어, 최단 경로 문제에서는 전체 경로의 최단 거리는 경로의 부분 문제에서도 항상 최단 거리로 구성될 수 있다.중복되는 하위 문제: 동일한 하위 문제가 여러 번 반복해서 계산되는 경우가 있어야 ..

분할 정복(Divide and Conquer)이란?큰 문제를 해결하기 어려울 때 작은 하위 문제들로 나누어서 해결하는 문제 해결 전략이다.이 방식은 하위 문제를 재귀적으로 해결하고, 그 결과를 합쳐서 원래 문제의 해답을 구한다. 분할 정복의 세 단계분할(Divide): 문제를 여러 개의 하위 문제로 나눈다. 이때, 하위 문제들은 원래 문제와 동일하거나 유사한 형태를 가져야 한다.정복(Conquer): 각 하위 문제를 재귀적으로 해결한다. 이 단계에서 하위 문제들이 충분히 작아지면 직접 해결할 수 있다.병합(Combine): 하위 문제의 해답을 모아서 원래 문제를 해결한다.분할 정복의 특징재귀적 접근: 문제를 계속해서 더 작은 문제로 나누고, 각 문제를 재귀적으로 해결한다.효율적 탐색: 분할을 통해 문제의..