Computational Thinking
ํ๋ก๊ทธ๋๋ฐ์ ์ด๋ ค์ด ์ ๋ ๊ฐ์ง
ํ๋ก๊ทธ๋๋ฐ ์ธ์ด ๋ฌธ๋ฒ๊ณผ ๋ผ์ด๋ธ๋ฌ๋ฆฌ ์ฌ์ฉ
๋ ผ๋ฆฌ (
Hard Logic
)
Soft Logic vs Hard Logic
์ผ์ ์ํ์์๋
Soft Logic
์ด ๋น ๋ฅด๊ธฐ ๋๋ฌธ์ ์ ์ฉ๋ ผ๋ฆฌ์ ์ผ๋ก ๋ถ์ ํํ ํํ์ ์ฌ์ฉํ์ง๋ง, ์ด๋ค ์๋ฏธ์ธ์ง ๋ชจ๋ ์ฌ๋์ด ์ด๋ฏธ ์๊ณ ์๋ค๋ ๊ฐ์ ์ด ์กด์ฌ
ํ๋ก๊ทธ๋๋ฐ์
Hard Logic
์ ์ฌ์ฉํ๋ก๊ทธ๋๋ฐ ์ธ์ด์ ํํ๋ค์ด ๋ชจ๋ ๋ ผ๋ฆฌํ์์ ๋์จ ๊ฒ
์ฌ์ฉ๋๋ ์๋ง์ ์๊ณ ๋ฆฌ์ฆ๋ค์ ์ดํดํ๊ธฐ ์ํด์๋ Hard Logic์ด ํ์
1. ๋
ผ๋ฆฌ์ ์ฆ๋ช
๋ช
์
์ฐธ์ด๋ ๊ฑฐ์ง์ ์ ์ ์๋ ์์ด๋ ๋ฌธ์ฅ
p, q, r ... ๋ก ํํ
p -> q๊ฐ ์ฐธ์ด๋ฉด ~q -> ~p๋ ์ฐธ์ด๋ค (
๋์ฐ
)
ex)
์์ธ์ ๋ํ๋ฏผ๊ตญ์ ์๋๋ค
1 + 1 = 3
๋ ๋ณ์ ๊ธธ์ด๊ฐ ๊ฐ๋ค๋ฉด ์ด๋ฑ๋ณ ์ผ๊ฐํ์ด๋ค.
-> ์ด๋ฑ๋ณ ์ผ๊ฐํ์ด ์๋๋ฉด ์ด๋ ๋ ๋ณ์ ์ ํํด๋ ๋ ๋ณ์ ๊ธธ์ด๋ ๋ค๋ฅด๋ค
์ง๋ฆฟ๊ฐ
์ฐธ์ด๋ ๊ฑฐ์ง์ ํํ
T, F or 1, 0
ํญ์ง ๋ช
์
: ์ง๋ฆฟ๊ฐ์ด ํญ์ ์ฐธ
๋ชจ์ ๋ช
์
: ์ง๋ฆฟ๊ฐ์ด ํญ์ ๊ฑฐ์ง
์ฌ๊ฑด ๋ช
์
ํญ์ง ๋ช ์ ๋ ๋ชจ์ ๋ช ์ ๋ ์๋ ๋ช ์
์ํฉ์ ๋ฐ๋ผ ๋ฌ๋ผ์ง๋ ๋ช ์
์กฐ๊ฑด ๋ช
์
p, q๊ฐ ๋ช ์ ์ผ ๋, ๋ช ์ p๊ฐ ์กฐ๊ฑด (๋๋ ์์ธ), q๊ฐ ๊ฒฐ๋ก (๋๋ ๊ฒฐ๊ณผ) ๋ก ์ ์๋๋ ๋ช ์
p -> q
(p์ด๋ฉด q์ด๋ค)p๊ฐ True์ด๊ณ , q๊ฐ False์ผ ๋๋ง False
์๋ฐฉ ์กฐ๊ฑด ๋ช
์
p, q๊ฐ ๋ช ์ ์ผ ๋, ๋ช ์ p์ q๊ฐ ๋ชจ๋ ์กฐ๊ฑด์ด๋ฉด์ ๊ฒฐ๋ก ์ธ ๋ช ์
p <-> q
(p๋ฉด q๊ณ , q๋ฉด p๋ค)p์ q์ ์ฐธ/๊ฑฐ์ง์ด ๊ฐ์ ๋์ True
๋ช
์ ์ ์ฐ์ฐ (๊ฒฐํฉ)
๋ถ์
NOT
p๊ฐ ๋ช ์ ์ผ ๋, ๋ช ์ ์ ์ง๋ฆฟ๊ฐ์ด ๋ฐ๋
~p๋ก ํ๊ธฐ
not p ๋๋ p์ ๋ถ์ ์ผ๋ก ์ฝ์
๋ ผ๋ฆฌ๊ณฑ
AND
p, q๊ฐ ๋ช ์ ์ผ ๋, p, q ๋ชจ๋ ์ฐธ์ผ ๋๋ง ์ฐธ์ด ๋๋ ๋ช ์
p ^ q
p and q
p ๊ทธ๋ฆฌ๊ณ q
๋ ผ๋ฆฌํฉ
OR
p, q๊ฐ ๋ช ์ ์ผ ๋, p, q ๋ชจ๋ ๊ฑฐ์ง์ผ ๋๋ง ๊ฑฐ์ง์ด ๋๋ ๋ช ์
p v q
p or q
p ๋๋ q
๋ฐฐํ์ ๋ ผ๋ฆฌํฉ
XOR
p, q๊ฐ ๋ช ์ ์ผ ๋, p, q ์ค ํ๋๋ง ์ฐธ์ผ ๋ ์ฐธ์ด ๋๋ ๋ช ์
p โ q
p xor q
์ฐ์ฐ์ ์ฐ์ ์์
~
>v
,^
>->
,<->
์ฆ๋ช
์ฆ๋ช ์ ๋ช ์ ์์ผ๋ก ํํํ ์ ์๋ ๊ฒ์ด์ฌ์ผ ํจ
๋ณดํต์ ์ ํํ ๋ช ์ ์๊น์ง ์ฐ์ง๋ ์์ผ๋ ๊ทผ๋ณธ์ ์ผ๋ก๋ ๋ช ์ ์์ผ๋ก ๋ฐ๊ฟ ์ ์์
์ฆ๋ช ์ ๋ํ ์๋ง์ ์คํด๊ฐ
p -> q
๋ฅผp <-> q
์ ํผ๋ํ๋ ๊ฒ์์ ์ผ์ด๋จ
์ํ์ ๊ท๋ฉ๋ฒ๊ณผ ์ฆ๋ช
์ ์์ค
์ํ์ ๊ท๋ฉ๋ฒ์ ๊ธฐ๋ณธํ
P(1)
์ด ์ฐธ์ด๊ณ ,P(n) -> P(n+1)
์ด ์ฐธ์ด๋ฉดP(n)
์ ๋ชจ๋ ์์ฐ์ n์ ๋ํ์ฌ ์ฐธ์ด๋ค
์ํ์ ๊ท๋ฉ๋ฒ์ ๊ฐํ ํํ
P(1)
์ด ์ฐธ์ด๊ณ ,P(1) ^ P(2) ^ ... ^ P(n) -> P(n+1)
์ด ์ฐธ์ด๋ฉด (๋ชจ๋ ๊ฒฝ์ฐ๊ฐ ์ฐธ์ด๋ฉด),P(n)
์ ๋ชจ๋ ์์ฐ์ n์ ๋ํ์ฌ ์ฐธ์ด๋ค
๋ฉ์ฒญ์ด (pseudo-proposition) ๋
ผ๋ฆฌ
๋๊ฐ ๊ฒฝ์ฐฐ์์ฅ์ด๋ฉด ๋ ๋ํต๋ น!
F -> () ๋ ๋ฌด์กฐ๊ฑด ์ฐธ
ํ๋ฆฐ ๋ช ์ ๋ฅผ ์ฐธ์ด๋ผ๊ณ ๊ฐ์ ํ๋ฉด ์ด๋ค ๋ช ์ ๋ ์ฐธ์ด ๋๋ค
ex) ๋ก๋ ๋น์ฒจ๋๋ฉด ์๋์ฐจ ์ฌ์ค๊ฒ
๋ก๋์ ๋น์ฒจ๋์ง ์์ผ๋ฉด ์๋์ฐจ๋ฅผ ์ฌ์ฃผ์ง ์์๋ ๊ฑฐ์ง๋ง์ด ์๋๋ฉฐ, ๋ฏธ๋น์ฒจ์ผ ๊ฒฝ์ฐ์ ์ฌ์ค๋ ๊ฑฐ์ง๋ง์ ์๋๋ค
๊ฐ์ ์๋ฆฌ๋ก 2๊ฐ ํ์๋ผ๊ณ ํ๋ฉด 5๋ ์ง์๊ฑฐ๋ ํ์์ฌ๋ ๊ฑฐ์ง์ด ์๋๋ค
T -> F ์ผ๋๋ง ํ์คํ๊ฒ ๊ฑฐ์ง์ด๋ค
2. ์์ ํํ
์ปดํจํฐ๋ 0/1์ ํํํ ์ ์๋ ๋นํธ๋ค์ ๋ชจ์ ์๋ฅผ ํํ
k๊ฐ์ ๋นํธ๋ฅผ ์ฌ์ฉํ๋ฉด 0๋ถํฐ
2^k -1
๊น์ง ํํ ๊ฐ๋ฅ (1๋ถํฐ ์์ํ๋ฉด2^k
)์ฌ์ค, ๊ผญ ์ ๋ฒ์์ธ ๊ฒ์ ์๋!
์ฝ์ํ๋ ๋ฐฉ์์ ๋ฐ๋ผ ๋ค๋ฅด์ง๋ง, ์ด๋ค ๊ฒฝ์ฐ๋ ์ต๋
2^k
๊ฐ์ง์ ๊ฐ์ ํํํ๋ ๊ฒ์ด ๊ฐ๋ฅ10์ง์๋ก k์๋ฆฌ๋ฅผ ์ฐ๋ฉด 0๋ถํฐ
10^k -1
๊น์ง ํํ์ด ๊ฐ๋ฅํ ๊ฒ๊ณผ ์์ ํ ๋์ผํ ๊ณผ์
์ด๋ค ๊ฐ n์ ํํํ๊ธฐ ์ํด์๋ ๋ช ๊ฐ์ ๋นํธ๊ฐ ํ์ํ ๊น?
2^k -1 >= n์ด ์ฑ๋ฆฝํด์ผ ํจ
์ฆ,
2^k >= n+1
๊ฐ์ ์๋ฏธ๋ก, k >= log(n+1)
-> ์ฝ logn ๋นํธ๊ฐ ํ์
x = logn๊ณผ 2^x = n ์ ๊ฐ์ ๊ฒ์ ๊ฐ๋ฆฌํด!
+
logn์ด๋
2์ ๋ช ์น์ด
n
์ด ๋๋๋์ ๋ตn์ ํํํ๋ ๋ฐ ๋ช ๋นํธ๊ฐ ํ์ํ๊ฐ์ ๋ต
1๋ก ์์ํด์ ๊ณ์ ๋ ๋ฐฐ๋ฅผ ํ ๋ ๋ช ๋ฒ ํ๋ฉด n์ด ๋๋๋์ ๋ต
n์ 2๋ก ๊ณ์ ๋๋ ๋ ๋ช ๋ฒ ๋๋๋ฉด ๊ฑฐ์ 1์ด ๋๋๋์ ๋ํ ๋ต
x = logn
์ผ ๋ x์ n์ ๋น๊ตํ๋ฉด x๊ฐ ๋ ์๊ณ , n์ด ์ปค์ง์๋ก ์์ฒญ๋๊ฒ ๋ฌ๋ผ์ง๋ค๊ธ๊ฒฉํ๊ฒ ๋ณํ๋ ๊ฒ์ ์๊ฒ ๋ํ๋ด๊ณ ์ถ์ ๋ log ์ฌ์ฉ!
100์๋ฆฌ๋ก ํํํ ์ ์๋ 10์ง์ ๊ฐ์ ์ฝ์ ์๋ ์์ ์ ๋๋ก ํฐ ๊ฐ์ด๋ค!
์ปดํจํฐ ๋ถ์ผ์์ log์ ๋ฐ์ ํญ์ 2
32๋นํธ ์ปดํจํฐ
์ ์ฃผ์ ๊ณต๊ฐ์2^32
= ์ฝ 40์ต๊ฐ ์ฃผ์๋ง์ง๋ง (1+1+ ...) ์ผ ๋
n/ 2^k = 1
n = 2^k
k = logn
์ด ๊ดํธ ์๋ logn๊ฐ
๊ทธ๋์ ์ ์ฒด ์์ n์ผ๋ก ๋ฌถ์ผ๋ฉด
nlogn
Big-O Complexity

Exercises
2์ง์ ํํ์์
logn ๋นํธ
๋ก ํํํ ์ ์๋ ์ซ์ ๋ฒ์๋?n ๋นํธ ์ผ ๋ -> 2^n๊ฐ
logn ๋นํธ ์ผ ๋ -> n๊ฐ
์ค๋ฌด๊ณ ๊ฐ๊ฐ ์ด์์ ์ผ๋ก ์งํ๋๋ค๊ณ ํ ๋, ๋ง์ถ ์ ์๋ ๋ต์ ์ข ๋ฅ๋ ๋ช ๊ฐ์ง์ธ๊ฐ?
์ง๋ฌธ ํ๋๋น ์ ๋ต์ด 2๊ฐ ๋์ฌ ์ ์์
์ง๋ฌธ ๊ฐ์๋ ์ด 20๊ฐ
์ฆ, ๋ง์ถ์ ์๋ ๋ต์ ์ข ๋ฅ๋ 2^20 ๊ฐ์ง
n์ด ์ถฉ๋ถํ ํฐ ๊ฐ ์ผ ๋ ๋ค์์ค ์ด๋ ๊ฐ์ด ๋ ํฐ๊ฐ?
2n
<n^2
์๊ฐ ๋ฌดํ๋๋ก ํด ๊ฒฝ์ฐ n ์์ ์์๋ ๋ฌด์ํ ์ ์๊ณ , n๋ณด๋ค n^2์ ์์น๋์ด ํจ์ฌ ํฌ๊ธฐ ๋๋ฌธ
2^(n/2)
<โ(3^n)
โ(3^n) = 3^(n/2)
์ฆ, 2^n ๊ณผ 3^n์ ๋น๊ตํ๋ฉด 3^n์ด ๋ ํฌ๋ค
2^(nlogn)
>n!
๋ฐ์ด 2๋ผ๊ณ ํ๋ฉด,
n^n > n! ์ด๋ค
log2^(2n)
<nโn
2n < nโn
x = loga(yz) ์ผ๋ x๋ฅผ 2๋ฅผ ๋ฐ์ผ๋ก ํ๋ ๋ก๊ทธ๋ค๋ก ํํํ์์ค. ๋จ, ๋ก๊ทธ ํจ์์ ์ธ์๋ ๋ชจ๋ ๋ฌธ์ ํ๋์ฌ์ผ ํ๋ค.
๋ค์ ํจ์๋ค์ ์ญํจ์๋ฅผ ๊ตฌํ์์ค
f(x) = log(x-3) -5
f^-1(x) = 2^(x+5) +3
f(x) = 3 log(x+3) +1
f(x) = 2 x 3^x -1
์งํฉ๊ณผ ์กฐํฉ๋ก
์งํฉ
๋ ์งํฉ A์ B์ ๋ํด A๊ฐ B์ ๋ถ๋ถ์งํฉ์์ ์ฆ๋ช ํ๋ค๋ ๊ฒ์ A์ ์์์ ์์๊ฐ B์ ํฌํจ๋จ์ ๋ณด์ด๋ ๊ฒ๊ณผ ๊ฐ๋ค
ex) ๋ชจ๋ 4์ ๋ฐฐ์๋ 2์ ๋ฐฐ์๋ผ๋ ๊ฒ์ ์ฆ๋ช ํ๋ ค๋ฉด, 4k = 2(2k) ์์ ๋ณด์ด๋ฉด ๋๋ ๊ฒ!
๋ ์งํฉ A์ B๊ฐ ๊ฐ๋ค๋ ๊ฒ์ ์ฆ๋ช ํ๊ธฐ ์ํด์๋ A๊ฐ B์ ๋ถ๋ถ์งํฉ์ด๊ณ B๊ฐ A์ ๋ถ๋ถ์งํฉ์์ ์ฆ๋ช ํ๋ฉด ๋๋ค
์กฐํฉ
์กฐํฉ๋ก ์ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ฐ์ง๋ ๋ฌธ์ ๋ค์ ๋ณดํต ๋งํ๋ค
์กฐํฉ์ ๊ฐ์๋ C๋ฅผ ์ด์ฉํ์ฌ ํํํ๊ธฐ๋ ํ์ง๋ง (5 ๋ฐ์ 2) = 10 ๊ณผ ๊ฐ์ ๊ดํธ ํํ์ ๋ ๋ง์ด ์ด๋ค
+
์ํ์ ๊ท๋ฉ๋ฒ
์ํ์ ์ฆ๋ช ๋ฐฉ๋ฒ ์ค ํ๋๋ก, ์ฃผ๋ก ์ด๋ ํ ๋ช ์ ๊ฐ ๋ชจ๋ ์์ฐ์์ ๋ํ์ฌ ์ฑ๋ฆฝํจ์ ๋ณด์ด๋ ค๊ณ ํ ๋ ์ด์ฉ๋๋ค.
์ํ์ ๊ท๋ฉ๋ฒ์ ๋ ๋จ๊ณ๋ก ์ด๋ฃจ์ด์ง๋ค.
๋จผ์ ์ฃผ์ด์ง ๋ช ์ ๊ฐ 1์ ๋ํ์ฌ (์ผ๋ฐ์ ์ผ๋ก k์ ๋ํ์ฌ) ์ฑ๋ฆฝํจ์ ๋ณด์ธ๋ค.
๋ค์์ผ๋ก, ๊ทธ ๋ช ์ ๊ฐ 1 ์ด์์ (k ์ด์์) ์์์ ์์ฐ์ n์ ๋ํ์ฌ ์ฑ๋ฆฝํ๋ฉด, n+1์์๋ ์ฑ๋ฆฝํจ์ ๋ณด์ธ๋ค.
๊ทธ๋ฌ๋ฉด ์ํ์ ๊ท๋ฉ๋ฒ์ ์ํ์ฌ ์ฃผ์ด์ง ๋ช ์ ๊ฐ ๋ชจ๋ ์์ฐ์์ (k ์ด์์ ์์ฐ์์) ๋ํ์ฌ ์ฑ๋ฆฝํ๊ฒ ๋๋ค.
+
๊ท๋ฅ๋ฒ
๋ช ์ ๋ฅผ ์ฆ๋ช ํ๋ ค๊ณ ํ ๋, ๊ทธ ๋ช ์ ์ ๋ถ์ ์ ์ฐธ์ด๋ผ๊ณ ๊ฐ์
๊ทธ ๊ฐ์ ์ด ์ฐธ์ด ์๋(๋ชจ์์)์ ํตํด ์๋ ๊ฐ์ ์ด ์ฐธ์์ ๋ณด์ฌ์ค
Exercises



4. ๊ธฐ์ด์์
master crm
5. ์ฌ๊ท
์ฌ๊ท๋ ์๊ธฐ ์์ ์ ํธ์ถํ๋ ํจ์
(๋๋ ์ ์๋ ๊ฐ?)
ํจ์๋ ์ ๋ ฅ์ด ์์ผ๋ฉฐ, ์๊ธฐ ์์ ์ ์ ๋ ฅ๊ณผ ๋์ผํ ์ ๋ ฅ์ผ๋ก ์๊ธฐ ์์ ์ ํธ์ถํ๋ฉด ๋น์ฐํ ๋๋ ์ ์์
๋ค๋ฅธ ์ ๋ ฅ์ผ๋ก ๋๋ผ ์ ์๋ค!
ํจ์๋ ์ด๋ค ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ ์ฝ๋ฉํ ๊ฒ
์ด๋ค ๋ฌธ์ ์ ๋จ ํ ์ผ์ด์ค๋ง์ ํด๊ฒฐํ๋ ๊ฒ์ด ์๋!
์ ๋๋ก ์ฝ๋ฉ ๋ ๊ฒ์ด๋ผ๋ฉด ํด๊ฒฐํ๋ ๋ฌธ์ ์ ๋ชจ๋ ์ผ์ด์ค๋ค์ ํด๊ฒฐํด์ผ ํจ
์ํ์ ๊ท๋ฉ๋ฒ ์ฆ๋ช ์ฌ์ฉ ๊ฐ๋ฅ
n์ด 0์ผ ๋ ๋ฌธ์ ๋ฅผ ํ ์ ์์
n-1์์ ๋ฌธ์ ๋ฅผ ํ ์ ์์ผ๋ฉด n์์๋ ๋ฌธ์ ๋ฅผ ํ ์ ์๋ค
์ ๋ ๊ฐ์ง๊ฐ ์ฌ์ค์ด๋ฉด ๋ชจ๋ ๊ฐ๋ฅํ n์ ๋ํด ๋ฌธ์ ๋ฅผ ํ ์ ์๋ค๋ ๊ฒ์ด ์ฌ์ค
Last updated
Was this helpful?