설명다이나믹 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 간단한 하위 문제들로 나누어 해결하는 알고리즘 설계 기법이다. DP는 주로 중복된 하위 문제들이 존재할 때 효율적으로 문제를 해결하는 데 사용된다. 핵심 개념은 "작은 문제들을 먼저 풀고, 그 결과를 이용해 더 큰 문제들을 해결"하는 것이다.접근 방근1. 상향식 접근 (Bottom-Up Approach): 작은 하위 문제들로부터 해결해 나가며 점점 큰 문제를 해결하는 방법이다. 일반적으로 반복문을 사용해 테이블을 채워가며 문제를 해결한다. ex) 피보나치 수열을 계산할 때, 피보나치 수 F(n)을 계산하기 위해 F(0) 부터 F(n - 1)까지 차례로 계산하고, 이를 통해 F(n)을 계산한다. 2. 메모이제이션(Memoi..

이분 탐색(Binary Search)이분 탐색은 정렬된 배열에서 값을 찾는 효율적인 알고리즘이다. 어릴 적 친구와 1부터 100까지의 수 중 숫자 맞추기를 할 때 똑똑한 친구들은 50보다 커?(ㅇㅇ) 75보다 커?(ㄴㄴ) 이런 식으로 반 씩 줄여서 질문을 했을 것이다. 이것이 이분 탐색이다. 이 알고리즘은 배열을 차례대로 탐색하는 것이 아니라, 중간 값을 기준으로 탐색 범위를 계속해서 반으로 줄여나간다. 이로 인해 시간복잡도가 O(log n)으로 효율적이다. 아래 표에서 2를 찾아보겠다.123456789 먼저 중간 값인 5를 탐색한다. 2는 5보다 작기에 5보다 큰 값들은 신경 쓰지 않는다.12345     남은 값들 중 중간 값인 3을 탐색한다. 2는 3보다 작기에 3보다 큰 값들은 신경 쓰지 않는다...