[Algorithm] 빅오 표기법과 시간/공간 복잡도

알고리즘 파트를 포스팅한다면 제일 처음은 어떤 내용을 다루어야 할까 고민하다가

역시 Big-O notation과 Time/Space Complexity를 다루기로 했다.

 

백준 골드 등급 뿐만 아니라 실버에서도 까다로운 문제는 해당 개념을 알아야 한다.

단순히 '빠른 알고리즘을 쓰면 끝나는 거 아니야?'라고 생각할 수 있지만,

언제나 말하지만 소잡는 칼을 닭 잡는 데 쓰는 것은 미친 짓이다.

 

코테를 치루다가 모르는 알고리즘이 나왔다고 하자. 그냥 포기할 것인가?

그 순간에 내 알고리즘이 왜 통과가 될 수 없는지 원인을 분석하고

문제를 해결할 수 있는 방안을 찾아내야 한다.

 

문제를 보고 어떤 알고리즘을 사용할지 물색하는 과정은 가장 무식한 브루트 포스부터 시작할 지언정

그걸 떠올려보는 것과 진짜로 구현해봐야지만 되는지 안 되는지 판단이 가능한 사람은

시작부터가 다르다. 

 

즉, 빅오 표기법과 시간/공간 복잡도를 공부한다는 것은

현재 내 알고리즘의 성능의 분석과 문제 해결에 적절한지를 판단하는 지표로써 사용할 수 있다.

아, 여기서 지표로써 사용할 수 있다는 의미는 절대적인 기준이 되기는 힘들다는 것을 의미한다.

어디까지나 참고용이다. 이에 대한 내용도 가능하면 다뤄보자.

 

---

1. Big-O notation

 

Big O notation - Wikipedia

 

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

 

우선, 나는 이런 있어 보이는 설명 방식으로 정리하는 것을 좋아하지 않는다.

분명 멋있긴 하지만 내 포스팅의 최고 원칙은 해당 개념을 잊어버린 내가 N년 후 다시 보아도

한 번에 이해할 수 있어야만 한다는 것이기 때문에 위키 링크는 참고용으로 올려놓았을 뿐이다.

 

O는 하나의 함수다. 프로그래밍할 때 함수를 어떻게 사용했었나?

소괄호를 열고 인자값을 던져주면 됐었다. 이것도 마찬가지다.

O(1), O(9,999), O(N), O(NM) ....

근데 대체 여기서 1과 9,999와 N, NM이 대체 무엇을 의미하는 것일까.

임의의 코드를 하나 작성해보자.

 

#include <iostream>
using namespace std;

int main(void) {
    int N, M;
    cin >> N >> M;

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

    return 0;
}

컴퓨터의 연산은 굉장히 빠르다.

그렇기 때문에 사칙연산 정도의 간단한 계산은 O(1)로 판단해도 좋다.

수가 커지면 이야기가 달라지지만, 일단 패스하고 입출력도 제외하고 생각해보자.

 

그렇다면 위의 코드에서 고려해야 하는 데이터들을 단계별로 따져보면 다음과 같다.

  1. i < N을 판단

  2. sum에 i를 더하는 연산

  3. j < M을 판단

  4. sum에 j를 더하는 연산

각각을 판단하는 것은 O(1)이 4번 이므로 O(4)이지만, 조금 상세하게 분석해보면

1,2의 과정은 N번 반복하는 반면에 3,4의 과정은 NM번 반복한다.

그렇다면 시간복잡도를 O(2N + 2NM)이라고 표기해야할까? 그렇지 않다.

 

물론 표기법에 따라서 엄청 자세하게 나누기도 하지만 우리는 지금 논문을 쓰려는 게 아니라

문제를 풀기 위해 간단한 분석 정도만 하고 그칠 것이기 때문에 시간을 지배하는 조건만 찾으면 된다.

 

---

2. Time Compelxity

 

⏱️ 시간복잡도는 반복문이 지배한다.

예를 들어, 내가 지방으로 여행을 간다는 상황을 가정해보자.

그런데 차에 기름이 없어서 주유소에 들러야 할 것 같은데 그게 귀찮다고

자전거를 타고 여행을 가겠다는 결론을 내리는 미친 사람은 없을 것이다.

 

물론 시작하고 어느 지점까지는 자전거가 자동차를 앞서 있을 수 있겠지만,

기름을 넣고 출발하는 시점에서 자동차는 압도적인 속도로 자전거를 앞지를 것이다.

여기서 결국 시간을 지배하는 요소는 자전거와 자동차의 속력에 의해 지배된다.

이때, 속력과 같은 전체 요소의 대소를 판단하는 항목을 지배한다(dominate)라고 한다.

 

여담이지만 여기서 한 가지 재미있는 것을 더 알아갈 수도 있다.
내가 항상 말하는 "소 잡는 칼을 닭 잡는데 쓰지 말라"라고 하는 이유가
목적지가 코앞이라면 자동차보다 자전거, 혹은 걸어가는 것이 훨씬 빠르고 간단할 수 있기 때문이다.

 

그렇다면 위의 예시나 혹은 아무 예시를 하나 더 가져와서 판단해보자.

O(2N + 2NM)이나 O(N + 1,000)의 시간 복잡도를 가지는 것은 O(NM)과 O(N)으로 표기할 수 있다.

처음에는 2N과 1,000이 어느정도 영향을 끼칠 수는 있겠지만, 여기서 다시 가장 처음 위키를 언급하며

가져왔던 인용글을 참고해보자.

 

빅오 표기법은 인수가 특정 값이나 무한대로 향하는 경향이 있을 때, 함수의 제한 동작을 설명하는 표기법이다.

 

즉, 우리가 빅오 표기법을 사용하는 이유는 정확한 분석을 토대로 한 알고리즘 작성이 아니라

최악의 경우를 가정하여 상한선을 어림짐작하고 코드를 작성하기 위한 지표라고 생각하면 된다.

시간 복잡도를 고려하면 이런 코드 작성이 가능하다.

 

#include <iostream>
using namespace std;

int main(void) {
    int N; cin >> N;

    // 반복문을 사용한 전체합 O(N)
    int sum1 = 0;
    for (int i=1; i<=N; i++)
        sum1 += i;
    cout << sum1 << endl;

    // 수학적 원리를 이용한 전체합 O(1)
    int sum2 = 0;
    sum2 = N * (N+1) / 2;
    cout << sum2 << endl;
}

방법 1은 O(N)의 시간 복잡도를 지니지만, 방법 2는 O(1)의 연산으로 끝나는 것을 확인할 수 있다.

 

이제 대충 알고리즘 수행시간을 계산하는 방법과 이유를 알겠다.

그런데 문제는 그렇게 구한 값이 무엇을 의미하는가?

 

✒️ 간단한 연산 1억 번 == 1초

이건 절대 절대적인 수치가 아니라 어림짐작을 위한 척도 정도임을 망각해선 안 된다.

보통 알고리즘 문제는 제한 시간이 적혀 있다. 길면 2초 정도가 주어지고 짧으면 0.5초 정도된다.

SCPC나 기업 알고리즘 대회의 경우 너무 압도적인 데이터양을 주다보니 10초를 주기도 한다.

10초 정도면 해볼만 한데? 싶겠지만 그러다 나처럼 샷건 치다가 무선 키보드 하나 갈고 정신 차린다...

 

그럼 이제 위에서 작성한 1부터 N까지 전체합을 구하는 문제 조건에서

N의 범위가 (1 <= N <= 1,000,000,000,000)로 주어지고, 시간 제한이 1초라고 한다면

위의 반복문을 사용하면 절대 통과할 수가 없을 것이다.

 

다른 예를 들어보면, 최악의 경우가 N == 1,000,000이고 M == 1,000에 시간제한에

시간 제한이라고는 1초밖에 주어지지 않은 문제가 있다고 가정해보자.

내가 머릿속에서 상상한 알고리즘이 2중 반복문을 사용한 풀이법이라면 O(NM)이므로

대략 10억 번의 연산, 즉 10초 정도가 걸리므로 이 문제를 해결할 수가 없다.

그러기 위해서 (방법이 존재한다면)  O(NlogM)이나 O(logN), O(N)등의 시간이 걸리는

알고리즘을 떠올리고 코드로 작성해야 한다.

 

여기서 중요한 것은 계수를 줄이는 것보다 차수를 줄이는 것에 집중해야 한다.

획기적으로 O(2NM)이 2초 정도 걸릴 것 같다고, O(NM)으로 줄여볼까? 라고 접근하는 건 옳지 않다.

 

그런데 이때 단순히 다른 알고리즘을 사용하는 것 외에도 한 가지 방법이 더 존재한다.

바로 공간복잡도(Space Complexity)를 고려하는 것이다.

 

---

3. Space Complexity

 

시간 복잡도가 알고리즘 수행시간을 측정하는 용도라면, 공간 복잡도는 사용 메모리를 의미한다.

알고리즘 문제 풀이 방법 중 하나는 시간 복잡도를 줄이기 위해서 공간 복잡도를 희생하는 방법도 있다.

굳이 그런 이유가 아니더라도 인접 행렬로 구현하면 메모리 초과가 나서 인접 리스트로 구현해야 하는 등,

여러가지 요인들을 판단하기 위한 개념이다.

 

보통 효율적이고 좋은 알고리즘이라 하면, 최소한의 수행시간으로 최소한의 메모리 사용을 하는 알고리즘을 말하는데

실제로 구현하려고 보면 체지방 줄이면서 동시에 근육량 늘리기 같은 말과 비슷하다.

 

사담을 조금 섞고 시작하자면, 현대에 다다라서 메모리 관리는 최중요 고려 요소로 넣지는 않는다.

예전엔 메모리 제한이 너무 심했기에 심각하게 고려해야 했지만, 요샌 자원이 풍부해서 펑펑 쓴다.

하지만 컴퓨터 연산 속도는 물리적인 이유로 한계점에 다다랐기 때문에 그만큼 발전을 하지 못했기 때문에

문제를 분류할 때, P(Polynomial Time) - NP(Non-deterministic Polynomial Time) - NSPACE / PSAPCE의 순서로 넘어간다. 각각의 용어가 무엇을 의미하는 지는 딱히 중요하지 않다.

그냥 이러한 이유로 시간 복잡도가 우선순위에 있어서 앞서는 것을 보여주고 싶었다.

 

📈 인접 행렬과 인접 리스트 📉

쉽게 말해서 인접 행렬은 NM 크기의 배열을 모두 만든 것이고 인접 리스트는 트리를 만들었다고 보면 된다.

 

2차원 표를 만들어서 문제를 푸는 방식은 굉장히 직관적이고 구현도 쉽다는 장점이 있지만,

단점으로 불필요한 공간까지 잡아먹으며, 연산 과정에 해당 공간을 지나치니 시간 복잡도까지 증가한다.

알고리즘 문제 조건에는 시간 제한 뿐만 아니라 메모리 제한까지 존재한다.

만약, 내가 1 <= N <= 100,000과 1 <= M <= 100,000 크기의 정수 타입 2차원 그래프를 만든다고 생각해보자.

그렇다면 메모리가 (int)4byte * 100,000 * 100,000 이므로 400억 바이트로써 대충 40,000MB 정도를 차지하게 될 것이다.

하지만 내가 알기로 보통 메모리 제한은 128MB 정도밖에 되지 않는다.

그럼 제출과 동시에 메모리 초과로 광탈 당하는 기적을 맛보게 될 것이다.

이 외에도 고작 하나의 정보를 얻기 위해 NM크기의 그래프를 모두 순회해야하는 등의 불편함이 존재한다.

 

이런 이슈를 피해가 위해 여러 자료구조를 택하는데, 단순히 노드간 연결 정보만 저장하는 리스트나

트리 등을 이용하여 반복을 돌리더라고 깊이를 logN으로 줄여버리는 방법 등이 존재한다.

 

마찬가지로 '인접 리스트가 언제나 인접 행렬보다 뛰어나다'라고는 볼 수 없지만

플래티넘 정도로 넘어가면 인접 리스트로 해결할 수 없는 문제가 훨씬 많기는 하다.

그 때부터는 데이터를 어떻게 저장하고 조회하는지 조차 문제 풀이의 요소에 포함된다.