[기초] 알고리즘과 입출력 (+시간 복잡도)

 

 

알고리즘이란?

 

 

어떠한 문제를 해결하기 위한 여러 동작들의 모임, 절차입니다.

 

알고리즘 - 위키백과, 우리 모두의 백과사전

 

---

 

---

'시간 복잡도'

 

 

• 시간 복잡도를 이용하면 작성한 코드가 시간이 얼마나 걸릴지 예상할 수 있다.
• 표기법으로 대문자 O를 사용한다.
• 영어로는 Big O Notation
• 입력의 크기에 대해서 시간이 얼마나 걸릴지 나타내는 방법
• 최악의 경우에 시간이 얼마나 걸릴지 나타내야한다.

 

 

 

 

만약  1부터 N까지의 합을 계산하면,

 

시간 복잡도: O(N)

 

 

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

 

 

 

---

 

동일하게 1부터 N까지 합을 계산하는데 이중for문을 사용하면,

 

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

 

 

int sum = 0;
for (int i = 1; i <= N; i++) {
	for (int j = 1; j <= N; j++) {
    		if (i == j) {
        		sum += j;
        }	
    }
}

 

 

 

이렇게 반복문이 중첩되면 시간 복잡도는 크게 증가하는것을 알 수 있습니다.

 

 

 

이때 소요되는 시간은 시간 복잡도에 가장 큰 입력값을 넣었을 때, 1억이면 1초정도 소요

 

시간 복잡도가 1초 걸리는 각 입력 값의 크기는,

 

- O(1)

- O(log N)

- O(N) : 1억

- O(N log N) : 5백만

- O(N^2) : 1만

- O(N^3) : 500

- O(2^N) : 20

- O(N!) : 10

 

 

---

 

시간 복잡도의 의미 (대부분의 경우, 항상은 아님) 는,

 

- O(1) : 단순계산 (배열접근연산, 덧셈)

- O(log N) : N개를 절반으로 계속해서 나눔

- O(N) : 1중 for문

- O(N log N) : 

- O(N^2) : 2중 for문

- O(N^3) : 3중 for문

- O(2^N) : 크기가 N인 집합의 부분 집합

- O(N!) : 크기가 N인 순열

 

---

 

시간 복잡도 계산,

 

 상수는 버리고 계산하며

- O(3N^2) = O(N^2) 

- O(1/2N^2) = O(N^2) 

- O(5) = O(1)

 

두 가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버림

- O(N^2 + N) = O(N^2) 

 

두 가지 항이 있는데 변수가 다르면 놔둠

- O(N^2 + M)

 

 

---

 

'입출력'

 

 

Hello World!를 출력하는 문제

 

2557번: Hello World

 

#include <iostream>
using namespace std;

int main(){
    cout << "Hello World!";
    return 0;
}

 

---

 

두 수를 입력받고 A+B를 출력하는 문제

 

1000번: A+B

#include <iostream>
using namespace std;

int main(){
	int A, B;
    cin >> A >> B;
    cout << A+B;
    return 0;
}