완전 탐색은 과정을 이해하기 쉽도록 의사결정 트리(possibility tree)를 사용한다.따라서, 완전탐색과 의사결정 트리가 무엇인지 먼저 살펴본다!완전탐색완전탐색(Exhaustive Search)은 정답이 될 가능성이 있는 모든 후보를 탐색해서 정답을 찾는 알고리즘이다.의사결정 트리의사결정 트리는 문제를 해결하는 모든 경우의 수를 트리 형태로 나타낸 것이다.이를 깊이 우선 탐색(DFS) 방식으로 탐색하면 가능한 모든 경우를 빠짐없이 확인할 수 있다. => 즉, 완전탐색은 의사결정 트리를 DFS 기반으로 순회하는 과정과 동일!!- 의사결정 트리의 특징가능한 모든 경우를 표현한다.모든 선택지를 고려해야 하니까, 트리 구조로 나타내서 더 직관적으로 이해할 수 있다.DFS 방식으로 탐색한다.한 가지 경우를..

1. 문제 이해이 문제는 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제다.덧셈의 순서가 다르면 다른 경우로 카운트한 개의 수를 여러 번 사용할 수 있음예제 분석예제 입력 120 2 예제 출력 121 설명:K = 2 이므로 두 개의 수를 더해서 N = 20을 만들어야 함.가능한 경우: (0+20), (1+19), (2+18), ..., (20+0) → 21가지예제 입력 26 4 예제 출력 284 설명:K = 4 이므로 네 개의 수를 더해서 N = 6을 만들어야 함.가능한 경우: (0+0+0+6), (0+0+1+5), ... 등 84가지✅ 제한 조건1 ≤ N ≤ 2001 ≤ K ≤ 200경우의 수를 1,000,000,000(10억)으로 나눈 나머지 출력2. 접근 방식 (DP..

코테99 23일차 문제는 백준 9251번 LCS다.  문제 이해LCS(최장 공통 부분 수열) 문제는 두 개의 문자열이 주어졌을 때, 두 문자열에서 공통으로 등장하는 가장 긴 부분 수열의 길이 를 찾는 문제다.여기서 부분 수열 은 연속될 필요가 없지만, 원래 순서를 유지해야 한다. 제한 조건문자열 길이는 최대 1000시간 제한 0.1초 (O(N^2) 알고리즘까지 가능)접근 방법이 문제는 동적 계획법(DP) 을 활용하여 해결할 수 있다.2차원 DP 배열을 사용해 비교하는 방식이 핵심. 점화식 도출문자열을 2차원 표로 비교dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지 비교했을 때 LCS의 길이 를 저장한다.문자가 같을 때dp[i][j] = dp[i-1][j-1] + 1..

코테99 22일차 문제는 백준 11053번 '가장 긴 증가하는 부분 수열'이다. 문제 이해주어진 수열에서 "가장 긴 증가하는 부분 수열 (LIS: Longest Increasing Subsequence)" 의 길이를 구하는 문제이다.예를 들어, 아래 수열이 주어졌을 때10 20 10 30 20 50 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50] 이므로, 정답은 4가 된다. 제한 조건1 ≤ N ≤ 1,000 (수열의 길이)1 ≤ Ai ≤ 1,000 (수열의 각 원소 값)O(N^2)의 알고리즘으로도 해결 가능접근 방법이 문제를 해결하기 위해 동적 계획법 (DP) 을 사용한다.각 dp[i] 는 arr[i]를 마지막 원소로 가지는 가장 긴 증가하는 부분 수열의 길이 를 의미한다. 점화식 유도i번째..

코테99 21일차 문제는 백준 1003번 '피보나치 함수'다.  문제 이해이 문제는 피보나치 함수의 재귀 호출 과정에서 0과 1이 몇 번 출력되는지를 계산하는 문제다. 일반적인 피보나치 수열을 구하는 방식이 아니라, 특정 값이 반환될 때마다 몇 번 호출되는지를 파악해야 한다.예를 들어, fibonacci(3)을 호출하면 다음과 같은 과정이 진행된다:fibonacci(3) -> fibonacci(2) + fibonacci(1)fibonacci(2) -> fibonacci(1) + fibonacci(0)fibonacci(1) = 1 (출력: 1)fibonacci(0) = 0 (출력: 0)fibonacci(2) 결과 = 1 (출력: 1)fibonacci(3) 결과 = 2 (출력: 1)위 과정에서 0은 1번, ..

보호되어 있는 글입니다.