2024 - 02 - 14 C++ 코딩테스트 10주완성 D+5

*재귀함수 시간복잡도 

(Main Logic * 함수 호출)

시간복잡도 구하기 예제

Cnt 라는 전역변수를 기반으로 어림잡아 시간복잡도를 구하는 방법도 있지만

정석적인 방법으로는 Cnt 디버깅을 통해 점화식 을 구해 시간복잡도를 구하는 방법이 있다.

예를들어

n = 4 일때 도화식에서 구한 경우의 수가 맨위부터 아래로 내려오며

1+2+4 이고

n = 8 일때 

1+2+4+8 이면 

a(r^a-1) / r - 1 이라는 등비수열의 합 공식을 떠올릴 수 있다.

첫번째항(a) = 1 , 등비는 2, 갯수는 log(2n+1) 이므로 2n-1 이 나온다.

따라서 시간복잡도는 2n - 1 이며, 빅오표기법으로는 O(n) 이다.

로그는 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타낸다.

재귀함수 시간복잡도 두번째 예제

실습코드

void solve3(int N)
{
	if (N == 0) return;

	for (int i = 0; i < 3; i++)
	{
	solve3(N - 1);
	}
	return;
}

int main()
{
	//시간복잡도 다섯번째 예제

	cin >> thirdn;
	solve3(thirdn);
}

Solve 가 호출되면 매개인수인 N의 개수에 따라 3의 제곱만큼 Solve의 재귀함수를 호출하고, 숫자가 0이 되면 리턴한다.

따라서 시간복잡도는 1+ 3 + 9 .. 만큼 등비수열의 합으로 구하는 것이기에

등비수열의 합의 공식을 이용하여 시간복잡도를 구한다.

첫번째 항이 1 이고, 등비가 3, 그리고 갯수가 n 이니까

1(3^n -1) / 3-1

따라서 3^n-1 / 2 가 시간복잡도이다.

이를 빅오표기법으로 나타내면 3^n 이다.

*공간 복잡도

입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양

*누적합

요소들의 누적 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 의미

PrefixSum

배열의 작은요소를 시작으로 점차적으로 큰요소까지 오름차순으로 더하는 방식

SuffixSum

배열의 큰요소를 시작으로 점차적으로 작은요소까지 내림차순으로 더하는 방식

실습코드

typedef long long ll;
int a[100004], b, c, psum[100004], n, m;

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
	cin >> a[i];
	psum[i] = psum[i - 1] + a[i];
}

for (int i = 0; i < m; i++)
	{
	cin >> b >> c;
	cout << psum[c] - psum[b - 1] << "\n";
	}
	return 0;
}

*구현과 문제를 푸는 방법의 기초

구현

1. 소스코드안에 문제를 주석으로 남겨둘것

2. 하나의 주석마다 코드를 작성할것

문제를 푸는 방법

1. 문제를 본다.

2. 문제를 해석한다. 
  ㄴ 가. 최대, 최소범위를 파악한다.
  ㄴ 나. 단순 구현이라면 구현하자.
  ㄴ 다. 무식하게 풀 수 있다면 무식하게 풀자  
  ㄴ 라. 아니라면, 다른 알고리즘을 생각하자.
  ㄴ 마. 내가 짠코드가 정답이라도 반례가 있는지 한번 더 확인해볼것

3. 코드로 짠다.

*백준 2309 문제풀이

실습코드

 

#include <bits/stdc++.h>
using namespace std;

int a[9];
int sum;
pair<int, int> ret;
vector<int> v;
void solve()
{
	for (int i = 0; i < 9; i++)
		{
		for (int j = 0; j < i; j++)
			{
				if (sum - a[i] - a[j] == 100)
				{
				ret = { i,j };
				return;
				}
			}
		}
}	

int main()
{

//아홉 개의 난쟁이들의 키가 주어짐.
//키는 100을 넘지 않는 자연수이며 아홉 난쟁이의 키는 모두 다름.
//가능한 정답이 여러가지인 경우에는 아무거나 출력
//일곱 난쟁이의 키를 오름차순으로 출력

//순열
	for (int i = 0; i < 9; i++)
	{
	cin >> a[i];
	}
	sort(a, a + 9);

	do {
	for (int i : a) cout << i << "";
	cout << '\n';
	int sum = 0;
	for (int i = 0; i < 7; i++)
	sum += a[i];

	if (sum == 100) break;
	} while (next_permutation(a, a + 9));
	for (int i = 0; i < 7; i++) cout << a[i] << "\n";
	return 0;

//조합
	for (int i = 0; i < 9; i++)
	{
		cin >> a[i]; sum += a[i];
 	}

	solve();
	for (int i = 0; i < 9; i++)
	{
		if (ret.first == i || ret.second == i) continue;
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	for (int i : v) cout << i << "";
	return 0;

}