시간복잡도, 공간복잡도

시간복잡도

 

컴퓨터는 1초에 대략 3-5억 개의 연산을 처리할 수 있다. 따라서 시간 제한이 1초라고 한다면 3-5억 번의 연산 안에 답을 내고 종료되는 프로그램을 짜야 한다는 뜻으로 이해하면 된다.

 

입력의 범위를 보고 문제에서 요구하는 시간복잡도를 대략적으로 유추가 가능하다.

N의 크기	허용 시간복잡도
N <= 11	O(N!)
N  <= 25	O(2^N)
N  <= 100	O(N^4)
N  <= 500	O(N^3)
N  <= 3000	O(N^2logN)
N  <= 5000	O(N^2)
N  <= 1,000,000	O(NlogN)
N  <= 10,000,000	O(N)
그 이상	O(logN), O(1)

 

문제 1

N 이하의 자연수 중 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 프로그램을 작성하라. N은 5만 이하의 자연수이다.

var n = int.Parse(Console.ReadLine());
int answer = 0;

for (int i = 1; i < n; i++)
{
    if (i % 3 == 0 || i % 5 == 0)
        answer += i;
}
Console.WriteLine(answer);

시간복잡도: O(N)

 

 

문제 2

주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원수가 존재하면 1을, 존재하지 않으면 0을 출력하는 프로그램을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.

int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int answer = 0;

for (int i = 0; i < n.Length; i++)
    for (int j = i; j < n.Length; j++)
        if (i != j && n[i] + n[j] == 100) answer = 1;

Console.WriteLine(answer);

시간복잡도: O(N^2)

 

 

문제 3

N이 제곱수이면 1을 출력하고 제곱수가 아니면 0을 출력하는 프로그램을 작성하라. N은 10억 이하의 자연수이다.

var n = int.Parse(Console.ReadLine());
int answer = 0;

for (int i = 0; i * i <= n; i++)
    if ((i * i) == 0) answer = 1;

Console.WriteLine(answer);

시간복잡도: O(√N)

 

 

문제 4

N이하의 수 중에서 가장 큰 2의 거듭제곱수를 출력하는 프로그램을 작성하라. N은 10억 이하의 자연수이다.

var n = int.Parse(Console.ReadLine());
int answer = 0;

for (int i = 1; i <= n; i *= 2)
    answer = i;

Console.WriteLine(answer);

시간복잡도: O(logN)

 

 

 

공간복잡도

하드웨어에 의한 제한이 거의 없다시피한 요즘에는 크게 신경쓰지 않아도 괜찮은 부분이다. 다만, 메모리 제한이 512MB일 때 int 변수를 대략 1.2억개 정도 선언할 수 있다는 점은 기억해두는 게 좋다 (int 1개는 4바이트 이다).