[코딩테스트 28일차] BAEKJOON 2748번 : 피보나치 수 2, BAEKJOON 10989번 : 수 정렬하기 3

[BAEKJOON 2748번 : 피보나치 수 2]

[문제]

---

[고찰]

블로그에는 기록해두지 않았지만, 코딩테스트 20일차 때도 'BAEKJOON 10870번 : 피보나치 수 5" 문제를 풀었습니다.

그 때는 아래와 같이 반복문을 통해 풀었는데, 이번에는 다른 방법으로 풀고자 재귀함수로 해당 문제를 풀었습니다.

 

재귀함수를 이용해 피보나치 함수를 만들어 제출했는데, 시간 초과로 실패하였습니다.

그래서 이에 대해 찾아보니 피보나치 함수를 재귀함수로 풀었을 때 시간복잡도가 O(2^n)으로 어마어마하다는 것을 알게 되었고, 이에 다시 반복문을 활용하여 풀게 되었습니다.

 

아래는 제가 재귀함수로 풀었던 코드입니다.

#include <iostream>

using namespace std;

int Fibonacci(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;

	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	cout << Fibonacci(n);

	return 0;
}

---

[개념]

개념적으로는 사실 어렵지 않습니다.

저는 fn_1을 0, fn을 1로 F0과 F1이 될 변수를 설정하고 구할 Fn을 fx로 설정하였습니다.

 

반복문은 2부터 시작하여 입력받은 매개변수까지 반복합니다.

2부터 시작하는 이유는 0번째 피보나치 수와 1번째 피보나치 수는 fn_1과 fn으로 이미 설정하였기 때문입니다.

 

fx = fn + fn_1;

fn_1 = fn;

fn = fx;

 

이렇게 하면, fx를 fn + fn_1을 통해 구하고, fn_1을 fn, fn을 fx로 하여 n - 1번째와 n번째를 하나씩 앞당길 수 있습니다.

long long Fibonacci(int x)
{
	if (x == 0) return 0;
	if (x == 1) return 1;

	long long fn_1 = 0, fn = 1;
	long long fx = 0;

	for (int i = 2; i <= x; i++)
	{
		fx = fn + fn_1;
		fn_1 = fn;
		fn = fx;
	}

	return fx;
}

 

그리고 함수와 변수 모두 long long 타입으로 설정하여야 합니다.

 

처음에 int 타입으로 제출했다가 틀렸었습니다.

F89는 1,779,979,416,004,714,189인데, int 타입의 최대 범위를 넘어섭니다.

그렇기 때문에 int 타입으로 변수와 함수를 설정하면, 오버플로우가 되기 때문에 틀리게 됩니다.

---

[정리]

재귀함수를 사용하는 아이디어는 좋았지만, 문제에서 제공된 입력된 값의 범위가 90보다 작거나 같은 자연수라는 것을 제대로 봤어야 했습니다.

 

전에 풀었던 '피보나치수 5' 문제는 입력된 값의 범위가 20보다 작거나 같은 자연수여서, 이 문제에 위의 피보나치 함수를 재귀함수로 구현했던 코드를 제출하니 정답이었습니다.

 

그만큼 입력된 값의 범위는 중요했고, 앞으로는 이를 주의 깊게 살펴봐야겠습니다.

---

[Solution]

#include <iostream>

using namespace std;

long long Fibonacci(int x)
{
	if (x == 0) return 0;
	if (x == 1) return 1;

	long long fn_1 = 0, fn = 1;
	long long fx = 0;

	for (int i = 2; i <= x; i++)
	{
		fx = fn + fn_1;
		fn_1 = fn;
		fn = fx;
	}

	return fx;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	cout << Fibonacci(n);

	return 0;
}

---

[BAEKJOON 10989번 : 수 정렬하기 3]

[문제]

---

[고찰]

처음에 이 문제를 sort를 통해 풀었다가, 메모리 초과로 실패하였습니다.

해당 문제에서는 sort 함수를 사용하면 안되는데, 그 이유는 시간과 메모리 효율성 때문입니다.

 

아래는 제가 메모리 초과로 실패한 코드입니다.

#include <iostream>
#include <algorithm>  
#include <vector>     

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<int> arr(n);

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	sort(arr.begin(), arr.end());

	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << "\n";
	}

	return 0;
}

---

[개념]

현재 문제에서 입력은 최대 10,000,000개입니다.

일반적인 sort 함수는 O(n log n)의 시간 복잡도를 가지기 때문에

입력으로 최대 개수가 주어진다면, 10,000,000 x log₂10,000,000 ≈ 230,000,000번의 연산을 하게 됩니다.

이때 시간 초과 또는 메모리 초과가 발생할 수 있습니다.

 

sort 함수는 내부적으로 비교 기반 정렬이며, 대량의 데이터를 메모리에 담고 정렬을 수행합니다.

입력을 모두 저장한 후 정렬하기 때문에 그만큼 메모리가 많이 들게 됩니다. 

 

정리해보자면, sort 함수는 아래의 특징을 가집니다.

• O(n log n)의 시간 복잡도를 가진다.
• 내부적으로 비교 기반 정렬이며, 데이터를 모두 저장한 후 정렬한다.

 

또한, 입력의 최대 개수는 많지만, 숫자는 1부터 10,000 사이의 정수로 값의 범위가 상대적으로 작습니다.

즉, 값은 제한되어 있지만 개수만 많은 경우입니다.

이때는 sort 함수를 사용하는 것보다 계수 정렬(Counting Sort)을 활용하는 것이 압도적으로 빠릅니다.

 

계수 정렬 (Counting Sort)

계수 정렬은 정렬 알고리즘 중 하나로, 데이터의 크기 범위가 제한되어 있고, 정수인 경우에 사용할 수 있는 정렬 알고리즘입니다.

데이터를 직접 정렬하지 않고, 각 값이 몇 번 나왔는지를 세어서 정렬 결과를 만들어냅니다.

 

동작 원리

1. 카운트 배열을 생성합니다.
2. 정렬할 값(양의 정수)가 몇 번 나왔는지를 카운트 배열에 저장하여 등장 횟수를 셉니다.
3. 카운트 배열을 출력하여 정렬 결과를 출력합니다.

 

시간복잡도

• O(n + k)의 시간 복잡도를 가집니다.
  • n : 데이터 수,  k : 숫자 범위

 

해당 문제에서 계수 정렬을 활용한다면, O(n + k)의 시간 복잡도를 통해 최대 10,000번만 연산하면 됩니다.

메모리 측면에서는, 정수 배열 count만 사용하기 때문에 그만큼 메모리 효율성도 챙길 수 있습니다.

 

계수 정렬의 동작 원리를 해당 문제에서 적용한다면,

먼저, 최대 10000까지의 정수를 입력받아야 하기 때문에 10001 크기의 count 배열을 선언합니다.

이후 입력값을 입력받으면서, 그 값을 count[num]++과 같은 방식으로 카운트 배열에 저장하여 등장 횟수를 셉니다.

int count[10001] = { 0 };
int n;
cin >> n;

int num;
for (int i = 0; i < n; i++) {
	cin >> num;
	count[num]++;
}

 

마지막으로 반복문을 활용하여 count 배열을 출력하는데,

첫 번째 반복에서는 인덱스를 1부터 10000까지하여, 카운트 배열 전체를 반복하고,

이후 두 번째 반복에서는 첫 번째 반복의 인덱스에 해당하는 카운트 배열이 0이 될때까지 인덱스 값을 출력해주면 됩니다.

for (int i = 1; i <= 10000; i++) {
	while (count[i]--) {
		cout << i << '\n';
	}
}

---

[정리]

해당 문제를 풀면서 사용하는 함수의 시간 복잡도나, 정렬 알고리즘과 같은 다른 알고리즘들에 대해 무지하다는 것을 깨달았습니다.앞으로는 알고리즘 공부에도 힘써야겠습니다.

---

[Solution]

#include <iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int count[10001] = { 0 };
	int n;
	cin >> n;

	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		count[num]++;
	}

	for (int i = 1; i <= 10000; i++) {
		while (count[i]--) {
			cout << i << '\n';
		}
	}

	return 0;
}