백트래킹_순열 생성 (Permutation Generation)
순열(Permutation)은 주어진 원소들의 순서를 고려한 배열이다. 즉, 주어진 원소들의 모든 가능한 순서의 경우를 나열하는 것이 순열 생성이다. 주어진 원소가 n개라면, 순열의 개수는 n! (팩토리얼)개가 된다.예시:주어진 원소가 [1, 2, 3]일 때, 가능한 모든 순열은 다음과 같다:[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1] 순열 생성의 특징순열은 원소들의 순서를 바꾸어 다양한 조합을 만들기 때문에, 원소들의 순서가 매우 중요하다. 따라서 순열 생성 문제에서는 모든 원소를 한 번씩 사용하여 가능한 모든 경우를 나열하는 방식으로 접근해야 한다. 백트래킹을 이용한 순열 생성백트래킹을 사용한 순열 생성은 각 단계에서 아직 사용하지 않은 원소를 선..
백트래킹_부분 집합 생성 (Subset Generation)
부분 집합 생성(Subset Generation)은 주어진 집합의 모든 부분 집합을 구하는 문제이다. 부분 집합(Subset) 생성의 개념주어진 집합이 있을 때, 그 집합의 부분 집합이란 주어진 원소들 중 일부 또는 전체를 선택한 새로운 집합을 말한다. 부분 집합에는 빈 집합과 전체 집합도 포함된다. 주어진 집합에 포함된 원소의 개수가 n개라면, 그 집합의 부분 집합의 개수는 2^n개이다. 이는 각 원소를 선택하거나 선택하지 않음으로써 발생하는 모든 경우의 수이다.예시주어진 집합이 {1, 2, 3}이라고 할 때, 부분 집합은 다음과 같다:[][1][2][3][1, 2][1, 3][2, 3][1, 2, 3]백트래킹을 사용한 부분 집합 생성백트래킹(Backtracking)은 모든 가능한 선택을 시도하면서, ..
최대 부분 배열 합 (Maximum Subarray Sum)
최대 부분 배열 합(Maximum Subarray Sum) 문제는 주어진 배열에서 연속된 부분 배열 중에서 가장 큰 합을 갖는 부분 배열을 찾는 문제이다. 이 문제는 배열에서 연속된 요소들의 합을 최대화하는 부분 배열을 찾는 것이 목표이다.문제 정의주어진 배열에서 연속된 부분 배열의 합이 최대가 되는 부분 배열을 찾는다.배열의 원소는 양수와 음수 모두 포함될 수 있다.예를 들어, 배열 [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 주어진다면, 최대 부분 배열 합은 6이며, 그 부분 배열은 [4, -1, 2, 1]입니다. 카데인 알고리즘 (Kadane's Algorithm)이 문제는 카데인 알고리즘(Kadane’s Algorithm)을 사용하여 O(n)의 시간 복잡도로 해결할 수 있다. 카데인..
0-1 배낭 문제 (0-1 Knapsack Problem)
0-1 배낭 문제는 NP-완전 문제 중 하나로, 주어진 아이템 중에서 최대 가치를 얻을 수 있도록 배낭에 담는 방법을 찾는 문제이다. 각각의 아이템은 특정한 무게와 가치가 있으며, 배낭은 최대 무게 제한이 있다. 아이템을 쪼갤 수 없기 때문에, 각 아이템을 넣거나 넣지 않는 선택을 해야 하며(즉, 0 또는 1로 선택), 이를 최적화하는 방식이다.문제 정의:N개의 아이템이 있고, 각 아이템은 무게 weights[i]와 가치 values[i]를 가진다.배낭의 용량 W는 한정되어 있으며, 이보다 무게가 큰 아이템들은 넣을 수 없다.목표는 배낭에 담을 수 있는 최대 가치를 구하는 것이다.예시:아이템이 다음과 같다고 가정해 본다:아이템 1: 무게 2, 가치 3아이템 2: 무게 3, 가치 4아이템 3: 무게 4, ..
