poksul_log

📍 다이나믹 프로그래밍이란? 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 컴퓨터는 연산 속도와 메모리 공간에 한계가 있기 때문에, 이를 최대한으로 활용해야 한다. 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수가 있는데, 이를 이용한 방법이 바로 DP이다. 📍 다이나믹 프로그래밍이 쓰이기 위한 조건 큰 문제가 작은 문제로 나눠질 수 있어야 한다. 작은 문제에서 구한 정답은 이를 포함하는 큰 문제에서도 동일하다. 다이나믹 프로그래밍은 1번 조건에 의해 분할 정복과도 비슷한 성질을 지니고 있지만, 분할 정복과 달리 문제들이 서로에게 영향을 끼친다. 📍 피보나치 수열 문제를 통해 알아보는 DP 다이나믹 프로그래밍의 대표적 예로 피보나치 수열 문제..

📍백트래킹이란 ? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 즉, 해를 찾을 때 중간에 해가 아니어서 막힐 경우, 이전 단계로 되돌아가 해를 다시 찾는 기법 📍백트래킹의 쓰임 최적화 및 조합, 결정 문제를 풀 때 쓰인다. 주로 DFS(깊이 우선 탐색)와 묶여서 잘 쓰이는데, DFS는 가능한 모든 경로를 탐색한다. 따라서, n이 큰 경우 경우의 수를 줄여야 할 필요성이 있다. → 이 때 백트래킹을 사용하여 불필요하거나 불가능한 경로를 사전에 차단하는 것을 통해 경우의 수를 줄일 수 있다. 즉, 가지치기를 할 수 있다는 것 ! ▶ DFS와 쓰일 때 흐름은 다음과 같다. DFS로 모든 경우의 수를 탐색할 때, 조건문을 걸어 불가능한 경우를 정의하고, 해당 상황일 때 탐색을 중지 이후 ..

가장 작은 것을 선택하여 제일 앞으로 보내는 정렬 방법 ▶ 흐름은 다음과 같다. 1. 맨 앞에서부터 차례로 돌며 가장 작은 수 찾기 2. 가장 작은 수 맨 앞에 있는 수 3. 2번째 수부터 차례로 돌며 2번째로 작은 수 찾기 4. 2번째 수 2번째로 작은 수 5. 위의 과정을 n번째까지 반복 ▶ C++ 코드 #include int main(){ int i, j, min, index, temp; int array[10] = { 1, 10, 8, 7, 5, 4, 6, 3, 2, 9}; for(i=0; i 2번째까지 제외한 8개 살펴보기 ... >> 10+9+...+1 = (10*11)/2 - n(n+1)/2 >> O(n^2)