백준 단계 11 : 시간 복잡도 (C++)

 

https://shine-slowly.tistory.com/33

알고리즘: 시간 복잡도란

시간 복잡도를 잘 모르신다면 이 포스팅을 읽는 것을 추천드립니다.

 

24262. 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	cout << 1 << '\n' << 0;
}

주어진 함수

#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	cout << 1 << '\n' << 0;
}

n의 크기에 상관없이 고정된 시간으로 계산된다. 단순하게 index에 접근하기만 하므로 O(1)이다.

 

 

 

24263. 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

주어진 함수

#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	cout << n << '\n' << 1;
}

O(n)이다. for문을 한번 반복하기 때문이다.

 

 

 

24264. 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

주어진 함수

#include<iostream>
#include<cmath>
using namespace std;
int main() {
	long long int n;
	cin >> n;
	cout << n*n << '\n' << 2;
}

n의 자료형을 설정하는 부분을 꼭 확읺애야 한다. 최대 500,000까지 될 수 있므로 long long으로 꼭 해야 한다. 나는 이 부분을 놓쳤다.

 

 

 

24265. 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

 

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

주어진 함수

#include<iostream>
#include<cmath>
using namespace std;
int main() {
	long long int n;
	cin >> n;
	cout << n*(n - 1)/2 << '\n' << 2;
}

코드 1이 1+2+3+...+n-1번 실행되게 되는데 이걸 n*(n-1)/2로 나타낼 수 있다. 이거는 수학 공식을 알고 있어야 할 수 있을 것 같다. O(n^2)이 된다.

 

 

 

24266. 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

주어진 함수

#include<iostream>
using namespace std;
int main() {
	long long int n;
	cin >> n;
	cout << n*n*n << '\n' << 3;
}

삼중 for문이라서 O(n^3)이 된다.

 

 

 

24267. 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

주어진 함수

#include<iostream>
using namespace std;
int main() {
	long long int n;
	cin >> n;
	cout << (n - 2) * (n - 1) * n / 6 << '\n' << 3;
}

위와 같은 공식을 사용해서 구할 수 있다. 

 

 

 

24313. 오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

#include<iostream>
using namespace std;
int main() {
	int a1, a0, c, n0;
	cin >> a1 >> a0 >> c >> n0;
	if ((a1 <= c) && (a1 * n0 + a0 <= c * n0)) {
		cout << true;
	}
	else {
		cout << false;
	}
	return 0;
}

n ≥ n0인 모든 n에 대해 f(n)  ≤   c · g(n)를 만족하는 양의 상수 c와 n0가 존재하면 f(n) = O(g(n))이다.

예를 들어 어떤 알고리즘이 n^3 + n^2 + 1라면, c=3이고 n0=1일 때 g(n)=n^3은 항상 성립힌다.