이 글은 "문제 해결력을 높이는 알고리즘과 자료구조" 책을 읽고 간단하게 주관적인 중요한 부분만 정리한 글입니다.

복잡도와 빅오 표기법

복잡도란?

실제로 알고리즘을 구현하지 않아도 계산 시간이 얼마나 걸릴지 어림짐작할 수 있는 척도 역할을 하는 것

복잡도는 왜 배우나요?

• 구현하려는 알고리즘을 실제로 프로그래밍해 보지 않아도 컴퓨터에서 실행할 때 걸리는 시간을 미리 대략적으로 파악할 수 있습니다.

복잡도와 빅오 표기법

• 알고리즘 A의 계산 시간 $T(N)$ 이 대략 $P(N)$ 에 비례하면 $T(N) = O(P(N))$ 이라 표현하고, 알고리즘 A의 복잡도는 $O(P(N))$ 이라 부릅니다.

복잡도를 빅오 표기법으로 표시하는 이유

• 최고차항 이외를 제외해도 되는 이유는 N의 크기가 커질수록 분명해집니다.
• 계수를 생략하는 이유는, 대략적인 성능을 가름할 때 계수차이가 무시해도 될 정도로 작기 때문입니다.

복잡도 사용법

알고리즘을 설계하기 전에는 다음 내용을 미리 확인해야 합니다.

• 계산 실행 시간 제약은 어느 정도인가?
• 풀고 싶은 문제 크기는 어느 정도인가?

위와 같은 내용을 알고 있으면 복잡도를 어느 정도까지 허용할 수 있는지 역산할 수 있습니다.

일반적인 1초 간 처리 가능한 계산 횟수는 $`10^9 = 1,000,000,000`$ 회 정도입니다.

란다우 빅오 표기법 상세 설명

• 빅오 표기법은 점근적 상한선(asymptotic upper bound)으로 아무리 나쁜 상황이더라도 비교 함수보다 같거나 좋다는 뜻입니다.

설계 기법(1): 전체 탐색

전체 탐색(1): 선형 탐색법

• 요소를 하나하나 순서대로 조사하는 탐색법입니다.
• N개 값을 순서대로 조사하므로 $O(N)$입니다.

선형 탐색법의 응용 (flag)

조건을 만족하는 위치 파악 가능

• 수열에 조건을 만족하는 값이 있는지 판정할 뿐만 아니라 위치를 알고 싶을 때도 사용합니다.

최소값 구하기

• for문으로 반복할 때 min_value 변수에 지금까지 확인한 값 중 가장 작은 값을 저장합니다.

전체 탐색 (2): 쌍 전체 탐색

앞선 문제보다 조금 더 발전된 다음과 같은 문제를 생각해 봅시다.

• 주어진 데이터 안에서 최적의 쌍을 탐색하는 문제
• 주어진 두 쌍의 데이터에서 각각의 요소를 추출하는 방법을 최적화하는 문제

이런 문제는 이중 for문을 사용하면 풀 수 있습니다.

→ 모든 경우의 수를 조사해 보는 것이죠.

전체 탐색 (3): 조합 전체 탐색

부분 합 문제와 같은 것들은 부분 집합 $2^N$개를 모두 조사하면 풀 수 있습니다.

→ 아래와 같이 정수의 이진법 표현인 비트 연산을 사용하는 방법도 있습니다.

//
// Created by 최우영 on 2022/07/12.
//
#include <iostream>
#include <vector>

using namespace std;

void code_3_6() {
    // 입력
    int N, W;
    cin >> N >> W;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    // bit는 2^N개 존재하는 부분 집합 전체를 대상으로 동작
    bool exist = false;
    for (int bit = 0; bit < (1 << N); ++bit) {
        int sum = 0;    // 부분 집합에 포함된 요소의 합
        for (int i = 0; i < N; ++i) {
            // i번째 요소 a[i]가 부분 집합에 포함되는지 여부
            if (bit & (1 << i)) {
                sum += i;
            }
        }

        // sum이 W와 일치하는지 여부
        if (sum == W) exist = true;
    }

    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
}