📜LaTex - 컴알 과제 1

컴퓨터 알고리즘 과제가 있었는데

그냥 이렇게 내는 것보다는 

좀 공식적으로 제출하는 게 좋지 않나 해서

latex으로 바꿔 봤다.

\documentclass{article}
\usepackage{amsmath}
\usepackage[margin=1.5in]{geometry} % 여백을 1인치로 설정
\usepackage{kotex} % 한국어 설정

\begin{document}

\section*{Written Assignment 1 }
\vspace{10mm} 

 % Example 2
\subsection*{Example 2}
\[
T(n) =
\begin{cases} % {
a, & \text{if } n = 1 \\ % 줄바꿈 \\ 또는 \newline
b + 2T\left(\frac{n}{2}\right), & \text{if } n > 1
\end{cases}
\]
\\
수식을 확장하면,
\[
T(n) = b + 2T\left(\frac{n}{2}\right)
\]
\[
\begin{aligned}
2T\left(\frac{n}{2}\right) &= b + 2^2T\left(\frac{n}{2^2}\right) \\
2^2T\left(\frac{n}{2^2}\right) &= 2^2b + 2^3T\left(\frac{n}{2^3}\right) \\
& \vdots \\
2^kT\left(\frac{n}{2^k}\right) &= 2^kb + 2^{k+1}T\left(\frac{n}{2^{k+1}}\right)
\end{aligned}
\]
\\
이를 이용하여 T(n)을 만들 수 있습니다.
\[
\Rightarrow T(n) = 2^{k+1}T\left(\frac{n}{2^{k+1}}\right) + b(2^{k+1} - 1)
\]
( $b(2^{k+1} - 1)$의 도출 과정 )
\[
\begin{aligned}
T(n) &= b \sum_{d=0}^{k-1} 2^d + 2^kT\left(\frac{n}{2^k}\right) \\
&= b \frac{2^k-1}{2-1} = b(2^{k+1}-1)
\end{aligned}
\]
$\frac{n}{2^{k+1}}= 1, \quad (2^k = n)$ 로 가정하면,
\[
\begin{aligned}
T(n) &= n \cdot T(1) + b (n - 1) \\
&= \Theta(n) + bn - b \\
&= O(n)
\end{aligned}
\]
O(n)의 시간복잡도를 알아낼 수 있습니다.


\vspace{10mm} % 수직 공간

 % Example 3
\subsection*{Example 3}

\[
T(n) =
\begin{cases}
a, & \text{if } n = 1 \\
bn + 2T\left(\frac{n}{2}\right), & \text{if } n > 1
\end{cases}
\]
\newline
수식을 확장하면,
\[
\begin{aligned}
2T(n) &= b + 2T\left(\frac{n}{2}\right) \\
2^2T\left(\frac{n}{2^2}\right) &= b + 2^2T\left(\frac{n}{2^3}\right) \\
& \vdots \\
2^kT\left(\frac{n}{2^k}\right) &= b + 2^kT\left(\frac{n}{2^{k+1}}\right)
\end{aligned}
\]
이를 이용하여 T(n)을 만들 수 있습니다.
\[
T(n) = k b + 2^kT\left(\frac{n}{2^k}\right)
\]

 $n = 2^k+1$ 로 가정하면,
\[
\begin{aligned}
T(n) &= b \log_2 n + n \cdot T(1) \\
&= b \log_2 n + a \cdot n \\
&= O(n)
\end{aligned}
\]
O(n)의 시간복잡도를 알아낼 수 있습니다.

\end{document}

 

와~와~

GitHub - Goldchae/Computer-Algorithm: 컴퓨터 알고리즘 과제 아카이브

컴알 열심히 해야지...

영강은 최악의 선택이었다

하지만파이썬놓칠수없어