[백준/C언어] 시간 복잡도

#24262번_알고리즘 수업 - 알고리즘의 수행 시간 1

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자. MenOfPassion 알고리즘은 다음과 같다.

풀이

문제에서 주어진 알고리즘에서는 1번의 연산만 하게된다. 즉 입력값에 상관없이 1번의 연산을 하므로 시간복잡도는 O(1)이다. 따라서 연산 횟수는 1이며 상수이므로 최고차항의 계수는 항상 0이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int n;

	scanf("%d", &n);

	printf("1\n0\n");

	return 0;
}

---

#24263번_알고리즘 수업 - 알고리즘의 수행 시간 2

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자. MenOfPassion 알고리즘은 다음과 같다.

풀이

위 알고리즘에서 입력한 n의 값만큼 반복한다. 따라서 시간 복잡도는 O(n)이다. 연산횟수는 n이고, 1차함수 이므로 최고차항의 계수는 1이 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int n;

	scanf("%d", &n);

	printf("%d\n1", n);

	return 0;
}

---

#24264번_알고리즘 수업 - 알고리즘의 수행 시간 3

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자. MenOfPassion 알고리즘은 다음과 같다.

풀이

이중 반복문을 사용하여 총 연산횟수는 n^2이 된다. 즉 시간복잡도는 O(n^2)이다. 즉 연산횟수는 n^2이며, 최고차항의 계수는 2이다. 해당문제의 경우 주어지는 n의 값의 범위를 유의하여 자료형을 사용해야한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	long long n;

	scanf("%lld", &n);

	printf("%lld\n2", n * n);

	return 0;
}

---

#24265번_알고리즘 수업 - 알고리즘의 수행 시간 4

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자. MenOfPassion 알고리즘은 다음과 같다.

풀이

이중 반복문으로 인해 O(n^2)이다. 따라서 수행횟수를 다항식으로 나타내었을 때, 최고차항 계수는 2가된다. 슈도 코드를 살펴보면 i가 k일때 j는 k - n번 연산한다. 따라서 연산 횟수는 (n - 1) + (n -2) + (n -3) + ... + 1이 된다. 위 연산을 반복문을 통해 변수 sum에 저장한 뒤 출력한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	long long n;
	long long sum = 0;
	
	scanf("%lld", &n);

	for (int i = 1; i < n; i++) {
		sum += i;
	}

	printf("%lld\n2", sum);

	return 0;
}

---

#24266번_알고리즘 수업 - 알고리즘의 수행 시간 5

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자. MenOfPassion 알고리즘은 다음과 같다.

풀이

삼중 반복문으로 인해 O(n^3)이 된다. 따라서 수행횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 3이다. 슈도코드에서 반복문을 살펴보면 3개의 반복문에서 모두 1부터 n까지 반복을 수행한다. 따라서 수행 횟수는 n * n * n으로 표시할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	long long n;
	
	scanf("%lld", &n);


	printf("%lld\n3", n * n * n);

	return 0;
}

---

#24267번_알고리즘 수업 - 알고리즘의 수행 시간 6

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자. MenOfPassion 알고리즘은 다음과 같다.

풀이

삼중 반복문으로 인해 O(n^3)이된다. 즉 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 3이다. 예시로 n의 값이 7일 때 총 수행횟수를 구하는 방식은 다음과 같다. 위를 참고하여 수행횟수를 구하는 연산을 일반화 해보면 다음과 같다. 일반화 된 연산을 반복문으로 구현하여 출력한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	long long n;
	long long sum = 0;
	
	scanf("%lld", &n);

	for (int i = 0; i < n - 2; i++) {
		sum += (n - 2 - i) * (1 + i);
	}


	printf("%lld\n3", sum);

	return 0;
}

---

#24313번_알고리즘 수업 - 점근적 표기 1

문제

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자. O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다} 이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다. 함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

풀이

출력에서 O(n) 정의를 만족하면 1 아니면 0을 출력하도록 했으므로 g(n) = n이 된다. 예시를 통해 참, 거짓을 판단하는 것은 다음과 같다. 위 연산을 일반화하면 다음과 같다. a1 x n0 + a0 <= c x n0 를 만족하면 참, 아니면 거짓 단 위의 식만으로 판별을 하면 예외가 발생한다. 예외가 발생하는 경우의 예시는 다음과 같다. 따라서 a0가 음수일 때 위의 일반식으로 연산을 한다면 n의 값이 n0일 때만 연산을 하여 참을 출력한다. 2번째의 케이스처럼 n이 3일때는 정의를 만족하지 않으므로 결과적으로 해당경우는 정의를 만족하지 않는다고 판별해야한다.  위의 예외경우는 f(n)의 일차항 계수가 c보다 클 때 발생하게 된다. (c의 값이 더 클 경우는 n의 값이 양수이기만 하면 만족하게된다.) 따라서 판별문에서 위의 일반식에 더불어 a0에 대한 조건을 추가하여 작성한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int a1, a0;
	int c;
	int n0;

	scanf("%d %d", &a1, &a0);
	scanf("%d", &c);
	scanf("%d", &n0);

	int f = a1 * n0 + a0;
	int g = c * n0;

	if (f <= g && a1 <= c)
		printf("1");
	else
		printf("0");

	return 0;
}