[2024-1] 1주차: 문제 풀이와 시간 복잡도

환영합니다!

ALPS 초급 스터디에 오신 여러분들 환영합니다. 이번 학기에 AlKor, ALPS, MatKor 소속인 여러분들과 함께 알고리즘을 함께 공부할 수 있게 되어 기쁩니다. 앞으로 9주 동안의 강의 많은 관심 가져주시고, 많은 문제 풀어봐요!

강사 소개

정보대학 컴퓨터학과 23학번 김승환
이대부속고등학교 졸업
2024 ALPS 부회장 & CAT&DOG 회장
Solved.ac: tmdghks / GOLD I
GPA: 4.46/4.5
고려대학교 SW중심대학 SW봉사단 - 우수봉사단 선정
현재 ALPS, MatKor, CAT&DOG, KUISA, KUICS, 고려대 SW교육봉사단에서 활동중!

알고리즘 초급 스터디 소개

수강 요건

아래 요건 중 하나라도 충족하면 수강하시기에 적합합니다.

본인은 입문 스터디(~2023 ALPS C언어 스터디)를 이수했다.
컴퓨터프로그래밍I, 컴퓨터프로그래밍II를 이수했다.
간단한 구현 및 프로그래밍을 할 수 있다.
자료형, 연산자, 조건문, 반복문, 함수 등 프로그래밍 과정에서의 요소를 알고 어떻게 활용하는지 알고 있다.

초급 스터디의 목표

PS에 필요한 매우 기초적인 자료구조, 알고리즘에 대해 학습한다.
배운 내용을 통해 문제를 해결함으로써 문제 해결력을 기른다.
배운 내용들을 전공 수업, 코딩테스트 등에 활용하자!
ICPC, KCPC, MatKor컵 등 다양한 CP 대회에 참여하기 위한 발판 역할!
백준 티어를 Gold V 이상으로 올린다!

강의 진행 방식

강의자는 매주 해당하는 이론에 대해 설명합니다.
백준 연습 탭에 매주 연습 문제가 과제로 주어집니다.
다음주부터는 지난주에 과제로 나왔던 문제들에 대한 풀이도 함께 진행합니다.

강의 진행 사이트 소개

백준 온라인 저지

국내 최대 규모의 알고리즘 트레이닝 사이트입니다. 약 3만개의 문제가 존재합니다.
acmicpc.net, icpc.me, boj.kr, noj.am 등의 url로 접속이 가능합니다.

solved.ac

백준 온라인 저지의 문제들에 대한 난이도를 티어 형태로 제공합니다.
티어로는 언랭, 브론즈, 실버, 골드, 플레티넘, 다이아몬드, 루비, 마스터(유저티어만 해당)가 존재합니다.

solut.kr

solut.kr에 풀이를 적어서 남겨주세요!

Solut.kr에 본인이 푼 문제에 대한 풀이를 적어주세요!
ALPS 부원 강유민님, 강근호님께서 제작하신 홈페이지입니다:)
우수 풀이 작성자에게 추첨을 통해 상품을 드립니다!(ex. 햄버거, 커피 등)
추첨을 위해 풀이를 작성하시면, 제게 개인톡으로 풀이 링크를 전송해주세요!

알고리즘이란?

넓게는 문제를 해결하기 위한 절차, 과정을 의미합니다.
대표적으로, 정렬 알고리즘, 그래프 탐색 알고리즘 등이 존재합니다.
컴퓨터과학에서는 말하는 알고리즘은 다음의 성질을 만족해야 합니다.
모든 입력값에 대해 튜링머신이 정지하도록 하는 명령이어야 합니다.
간단하게 튜링머신==우리가 쓰는 컴퓨터로 생각해도 됩니다!
알고리즘이기 위해선 다음 조건을 모두 만족해야 합니다.
- 입력: 0개 이상의 입력을 가져야 합니다.
- 출력: 1개 이상의 출력을 가져야 합니다. 출력이 없는 알고리즘은 의미가 없겠죠?
- 명확성: 각 과정은 명확해야 합니다. 모호한 명령어가 존재하면 안 됩니다.
- 유한성: 유한한 시간, 공간에서 실행될 수 있어야 합니다.
- 효율성: 알고리즘의 모든 과정은 명백하게 실행되거나 검증가능해야 합니다.

의사코드

우리는 알고리즘의 각 과정을 표현하기 위해 의사 코드를 사용합니다!
흔히 Pseudo code라고 불립니다.
프로그래밍 언어와 유사한 형태를 지니지만 프로그래밍 언어에 비해 형식에 자유롭습니다.
따라서, 쓰기도 쉽고 이해하기 쉽습니다. 하지만, 이것만으로 컴퓨터가 알고리즘을 이해할 수는 없습니다🥹
알고리즘의 밑그림을 그린다고 생각하면 됩니다!

의사 코드 예시: 구구단 코드

a단부터 b단까지 출력하는 알고리즘의 의사코드는 다음과 같습니다.

Procedure guguDan(a, b)
    for i = a, a + 1, … , b
        for j = 1, 2, 3, … , 9
            print(“i * j = (i * j)”)
        end for
    end for

알고리즘의 효율성 판단

알고리즘의 효율성을 어떻게 판단할 수 있을까?
알고리즘이 사용하는 자원은 무엇일까?
대표적으로 시간과 공간 자원을 이용한다.
각각의 자원을 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 판단할 수 있습니다.
복잡도가 낮을수록 효율적인 알고리즘입니다.

시간복잡도 판단 방법

시간 복잡도는 알고리즘이 거치는 과정의 수를 이용해 예측할 수 있습니다.
컴퓨터의 모든 명령에 사용되는 과정의 소요 시간이 같진 않습니다. 다만, 시간 복잡도 계산에서는 모든 과정의 소요 시간이 같다고 가정합니다.
예를 들어, 나눗셈, 곱셈 연산은 덧셈, 뺄셈 연산보다 오래 걸립니다. 하지만, 시간 복잡도 계산에서는 모두 소요 시간이 같다고 가정합니다.
입력이 $n$개라고 가정했을 때, 과정을 계산해보면 다음과 같은 식들을 얻을 수 있습니다.

\[n^2, \lg n, n \lg n, 2^n\]

점근적 표기 방법 (Asymptotic Notation)

하지만, 모든 알고리즘에 대해 입력 개수 $n$에 대한 식을 만드는 것은 비효율적일 것입니다.
그렇기 때문에 우리는 충분히 큰 수 $n$에 대하여 $f(n)$의 증가 속도를 표현하는 방식으로 시간복잡도를 표현합시다.
우리는 이러한 표기 방법을 점근적 표기법(Asympotitic Notation)으로 부릅니다.
주어진 함수 $g(n)$에 대해 Big-O $O(g(n))$는 다음과 같은 집합으로 나타냅니다.

\[O(g(n)) = \lbrace f(n) \,|\, \exists n_0, c \geq 0 ~ \forall n \geq n_0 ~ 0 \le f(n) \le cg(n) \rbrace\]

위 식에서 Big-O Notation은 다음과 같은 성질을 가집니다.

\[\lim_{n \rightarrow \infty} \left| \frac{f(n)}{g(n)} \right| < \infty\]

시간 복잡도의 식의 점근적 상한을 알 때에 사용합니다. 위 정의를 통해 $g(n)$이 점근적 상한임을 알 수 있습니다.
일반적으로 다음의 부등식이 성립합니다.

\[O(1) < O(\lg n) < O(n) < O(n \lg n) < O(n^2) < O(n^p) < O(2^n)\]

로그함수의 Big-O 표기법

알고리즘에서는 일반적으로 이진 로그 (밑이 $2$인 로그) $\lg n$을 사용합니다.
로그의 밑변환 공식에 따라 다음 공식이 성립합니다.

\[\begin{aligned} &\log_b a = \frac{\log_c a}{log_c b}= \frac{\lg a}{\lg b} \\ &\therefore \log_c n = O(\lg n) \end{aligned}\]

Big-O 표기법의 성질

\[O(g(n)) = \lbrace f(n) \,|\, \exists n_0, c \geq 0 ~ \forall n \geq n_0 ~ 0 \le f(n) \le cg(n)\rbrace\]

가장 높은 차수만 남기고, 낮은 차수는 버릴 수 있습니다.
일반적으로 차수를 다음과 같이 생각할 수 있습니다.
로그함수 «« 다항함수 «< 지수함수 «« 계승(팩토리얼)

예제 1

다음 식에 대한 Big-O Notation을 작성하시오.

\[\begin{aligned} 1. & \lg n + 10000000000 = \\ 2. & n^2 + n + n \lg n = \\ 3. & 3^n + 2^n = \end{aligned}\]

예제 2.1

다음 코드에 대한 시간 복잡도를 Big-O Notation으로 표현하십시오.

using ll = long long;

int alpsExample1 (ll a, ll b) {
    for (ll i = 0; i < a; i++) {
        for (ll j = 0; j < a; j++) {
            cout << "*";
        }
        cout << "\n";
    }
}

예제 2.2

다음 코드에 대한 시간 복잡도를 Big-O Notation으로 표현하십시오.

using ll = long long;

int alpsExample2 (ll a, ll b) {
    for (ll i = 0; i < a; i++) {
        for (ll j = 0; j < 10; j++) {
            cout << "*";
        }
        cout << "\n";
    }
}

다른 점근적 표기법

Big-Theta 표기법
어떤 함수의 점근 하한을 표현합니다.

\[\Theta (g(n)) = \lbrace f(n) \,|\, \exists n_0, c \geq 0 ~ \forall n \geq n_0 ~ 0 \le cg(n) \le f(n) \rbrace\]

Big-Omega 표기법
어떤 함수의 상한과 하한을 둘 다 알고 있을 때 사용 가능합니다.

\[\Omega(g(n)) = \lbrace f(n) \,|\, \exists n_0, c_1, c_2 \geq 0 ~ \forall n \geq n_0 ~ 0 \le c_1g(n) \le f(n) \le c_2g(n) \rbrace\]

재귀함수의 시간복잡도 계산

반복문 등의 시간 복잡도를 추정하는 것은 상대적으로 쉽습니다. (직관적)
하지만, 재귀함수의 시간복잡도를 계산하는 방법은 상대적으로 어렵습니다.
재귀함수의 시간복잡도를 계산하는 방법을 알아봅시다!

마스터 정리 (Master Theorem)

$n=1$일 때, 상수 시간($O(1)$)이 걸리는 재귀함수를 생각해봅시다.
그리고 재귀함수 작동에 걸리는 시간 $T(n)$에 대하여 다음 점화식이 만족된다고 생각해봅시다.

\[T(n)=aT\left(\frac{n}{b}\right) + f(n)\]

이 때, 다음 3가지 케이스가 존재합니다.

Case 1. 어떤 양수 $\epsilon > 0$에 대해, $f(n)=O(n^{\log_b{a-\epsilon}})$이면 $T(n)=\Theta\left(n^{log_b a}\right)$
Case 2. 어떤 양수 $\epsilon > 0$에 대해, $f(n)=O(n^{\log_b{a+\epsilon}})$이고 충분히 큰 수 $n$에 대하여 $aT\left(\frac{n}{a}\right) \le cf(n), c<1$이면 $T(n)=\Theta\left(n^{log_b a}\right)$
Case 3. $f(n)=O(n^{log_b a})$이면, $T(n)=\Theta\left(n^{log_b a} \lg n\right)$

Example

분할정복 알고리즘에서는 다음과 같은 점화식을 갖습니다.

\[T(n)=2T\left(\frac{n}{2}\right) + O(n)\]

풀이: $f(n)$인 $O(n)=\Theta(n^{\log_2 2})$이므로, Case 3에 해당한다!
따라서, 분할정복 알고리즘의 시간복잡도는 $\Theta (n \lg n)$이다.

문제 풀이에서 시간복잡도 활용

일반적으로 컴퓨터는 대략 $10^8$(1억)번의 연산을 1초에 수행할 수 있습니다.
일반적으로 시간 복잡도를 고려할 때 가장 최악의 경우를 고려하므로 상한 점근을 나타내는 Big-O 표기법을 주로 사용합니다.
예를 들어 입력의 크기가 $n$≤100,000일 때, $O(n^2)$은 불가능하다고 생각할 수 있습니다. $O(n)$ 등은 사용 가능합니다.
문제를 풀기 전에 구현하고자 하는 알고리즘의 시간복잡도를 미리 계산합시다!

공간 복잡도

문제풀이에서 공간 제한은 128MB부터 2048MB까지 매우 다양합니다.
사용하는 공간 = 메모리 사용 공간 = 변수 종류와 개수에 비례합니다.
Int, float 형은 4 byte, long long, double 형은 8 byte를 차지합니다.
char 형은 1 byte, bool은 1비트(1/8바이트)를 차지합니다.
대부분의 경우 int 400만개 정도 선언 가능합니다.

문제 풀이에서 공간 복잡도

일반적으로 문제 풀이에서는 시간이 공간보다 훨씬 더 중요합니다
시간과 공간을 일반적으로 반비례 관계를 갖습니다. (DP, Memoization… 등 알고리즘)
시간과 공간의 제약을 모두 충족하는 알고리즘을 생각해야 합니다!

알고리즘의 정당성 증명

어떤 알고리즘을 증명할 때 루프 불변성(Loop Invariant)을 보임으로써 알고리즘을 증명하는 데에 도움을 줄 수 있습니다.
루프 불변성을 보이기 위해 다음 세 가지 조건을 보여야 합니다.
- 초기 조건: 첫 번째 반복 시작 전에 루프 불변성이 참이어야 합니다.
- 유지 조건: 루프의 반복 시작 전에 루프 불변성이 참이었다면 다음 반복 시작 전에도 참이어야 합니다.
- 종료 조건: 루프가 종료될 때 불변식이 알고리즘의 정당성을 증명하는 데에 도움이 되어야 합니다.
수학적 귀납법, 구조적 귀납법과 매우 유사한 형태!

예시

다음 알고리즘의 루프 불변성을 증명하십시오.

procedure insertionSort(A)
    for i = 1, 2, ... n - 1 do
        key = A[i]
        j = i - 1
        while j < 0 and AND A[j] > key do
            A[j+1]=A[j]
            j = j - 1
        end while
        A[j+1] = key
    end for

풀이
초기 조건: i=1일 때, 부분 수열 $A[0]$는 정렬되어 있습니다.
유지 조건: i=k일 때, 초기 조건 만족한다고 가정하면, 루프가 끝날 때, 부분 수열 $A[0], … A[k]$는 정렬된 상태입니다.
종료 조건: 루프가 종료될 때, 수열 $A[0], … ,A[n]$은 정렬된 상태입니다.

따라서, 삽입 정렬 알고리즘은 정당합니다.

문제를 풀 때마다 루프 불변성을 증명할 필요는 없습니다.
하지만, 증명 과정에 이런 것들이 사용된다는 것을 알면 알고리즘을 더 쉽게 이해할 수 있을 것입니다!

과제 및 다음 시간 예고

과제는 백준 그룹을 참고해주세요. (금요일 업로드 예정)
2주차: 자료구조와 STL, 정렬, 이분탐색
과제 문제

번호	문제번호	제목	난이도	분류
1	24642	알고리즘 수업 - 알고리즘의 수행 시간 1	B5	Big-O Notation
2	24643	알고리즘 수업 - 알고리즘의 수행 시간 2	B4	Big-O Notation
3	24644	알고리즘 수업 - 알고리즘의 수행 시간 3	B3	Big-O Notation
4	24645	알고리즘 수업 - 알고리즘의 수행 시간 4	B3	Big-O Notation
5	24646	알고리즘 수업 - 알고리즘의 수행 시간 5	B3	Big-O Notation
6	24647	알고리즘 수업 - 알고리즘의 수행 시간 6	B2	Big-O Notation
7	24313	알고리즘 수업 - 점근적 표기 1	S5	Big-O Notation
8	24314	알고리즘 수업 - 점근적 표기 2	S5	Big-O Notation
9	24315	알고리즘 수업 - 점근적 표기 3	S4	Big-O Notation
10	24368	알고리즘 수업 - 점근적 표기 4	S1	Big-O Notation
11	24369	알고리즘 수업 - 점근적 표기 5	S1	Big-O Notation
12	24370	알고리즘 수업 - 점근적 표기 6	S1	Big-O Notation
13	11332	시간 초과	S4	Big-O Notation
14	25206	너의 평점은	S5	구현
15	18110	solved.ac	S4	구현
16	16956	늑대와 양	S3	애드 혹
17	4307	개미	S1	애드 혹