알고리즘/알고리즘 트레이닝(초록)10 효율성 - 최대 부분 배열 합, 두 퀸 1. NP - hard 문제 : 다항시간 알고리즘이 알려지지 않은 문제 2. 최대 부분 배열 합 배열에서 연속해 있는 값들을 선택해서 그 합을 최대로 만든다면 그 합은 얼마인가? 예) -1 2 4 -3 5 2 -5 2가 입력된다면 idx : 1~5까지의 합인 10이 정답임. f(n) = n번 인덱스에서 끝나는 최대 부분 배열 합 이 점화식을 구현하면, #include #include using namespace std; const int IMP = -1e9; int main() { int n, a[10]; cin >> n; for (int i = 0; i > a[i]; int sum = a[0], best = IMP; for (int i = 1; i < n; i++) { sum.. 2019. 12. 18. 재귀 - 부분집합, 순열 n개의 요소를 가진 배열에 대한 부분집합을 만든다면 총 2^n개의 부분집합이 나올 것. 각각의 요소들마다 부분집합에 포함하거나 포함하지 않거나 둘 중 하나이므로 2^n개의 부분집합이 생기는 것이다. #include #include #include using namespace std; const int MAX = 1e5 + 5; vector subset; int a[MAX],n; void make_subset(int k) { //k는 위치 if (k == n) { if (subset.empty()) cout BOJ 15649 - N과 M (1~12) N개 중 M개를 뽑아 나열하는 경우의 수 시리즈이다. 기본적으로 백트래킹을 이용해서 재귀로 구현함. 9~12같은 경우 중복을 제거해줘야 하는데, 이건 set로.. 2019. 12. 18. 이전 1 2 3 다음
