코젤브

https://youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬 www.youtube.com

동적계획법(Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 접근하는 방법이다. 부분 문제가 반복되고 최적의 원칙을 만족하는 문제를 일반적인 방법에 비해 적은 시간 내에 풀 때 사용한다. ex) 피보나치, 정수삼각형, 이항 계수 상향식 해결법(Bottom-Up 방식) 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식 최적의 원칙 : 어떤 문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 적용된다고 한다. 백준 2579번: 계단 오르기 #include #define MAX 301 using namespace std; int main() { int n; int DP[301];..

Backtracking : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. (최적화 문제와 결정 문제를 푸는 방법) : 모든 경우가 아닌 제약 조건에 맞는 후보해에 대해서만 탐색한다. 즉, 불필요한 탐색을 하지 않고 이전 단계로 돌아와 다른 후보해를 탐색한다. 해를 찾다가, 지금의 경로가 해가 될 것 같지 않으면, 그 경로로 가지 않고 바로 되돌아간다. (즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적) 이를 가지치기라고 하는데, 불필요한 부분은 빼고 최대한 올바른 쪽으로 간다는 의미이다. 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 ..