효율성 - 최대 부분 배열 합, 두 퀸

1. NP - hard 문제 : 다항시간 알고리즘이 알려지지 않은 문제

 

2. 최대 부분 배열 합

배열에서 연속해 있는 값들을 선택해서 그 합을 최대로 만든다면 그 합은 얼마인가?

 

예) -1 2 4 -3 5 2 -5 2가 입력된다면 idx : 1~5까지의 합인 10이 정답임.

 

f(n) = n번 인덱스에서 끝나는 최대 부분 배열 합

이 점화식을 구현하면,

 

#include  <iostream>
#include <algorithm>
using namespace std;
const int IMP = -1e9;

int main() {
	int n, a[10]; cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	int sum = a[0], best = IMP;
	for (int i = 1; i < n; i++) {
		sum = max(a[i], sum + a[i]);
		best = max(best, sum);
	}
	cout << best << '\n';
}

f(n)은 다음 순회때 한번씩만 쓰고 버리므로 그냥 변수 하나(sum)만 써도 된다.

 

O(n)

 

 

---

3. 두 퀸

n*n체스판에 두 퀸을 배치할 때, 둘이 서로 공격하지 못하게 배치하는 경우의 수를 출력.

 

n<=2인 경우 0 출력,

n==3인 경우 8 출력....

 

구하고자 하는 경우의 수를 q(n)이라고 하고 상황을 세가지로 나눈다.

1) n번쨰 행과 n번째 열에 둘 중 아무 퀸도 넣지 않는다고 할 때 : q(n-1)

2) n번쨰 행과 n번째 열에 하나의 퀸을 넣는 경우 : (2n-1)*(n^2 - 3(n-1) -1)

  그 퀸을 배치하는 경우는 2n-1

  그 퀸이 공격할 수 있는 칸의 개수와 그 퀸이 위치한 칸은 3(n-1) + 1

  따라서 다른 하나의 퀸을 배치할 수 있는 칸의 수는 n^2 - 3(n-1) -1

3) n번쨰 행과 n번째 열에 두 퀸을 모두 넣는 경우 : (n-1)*(n-2)

 

전체 상황은 (1) + (2) - (3) 이므로

메모이제이션 사용하면 O(n)

 

점화식 풀어서 정리하면 O(1) -> 생략