Computational Thinking

ํ”„๋กœ๊ทธ๋ž˜๋ฐ์˜ ์–ด๋ ค์šด ์  ๋‘ ๊ฐ€์ง€

  1. ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด ๋ฌธ๋ฒ•๊ณผ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ์‚ฌ์šฉ

  2. ๋…ผ๋ฆฌ (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์ด๋ž€

  1. 2์˜ ๋ช‡ ์Šน์ด n์ด ๋˜๋А๋ƒ์˜ ๋‹ต

  2. n์„ ํ‘œํ•œํ•˜๋Š” ๋ฐ ๋ช‡ ๋น„ํŠธ๊ฐ€ ํ•„์š”ํ•œ๊ฐ€์˜ ๋‹ต

  3. 1๋กœ ์‹œ์ž‘ํ•ด์„œ ๊ณ„์† ๋‘ ๋ฐฐ๋ฅผ ํ•  ๋•Œ ๋ช‡ ๋ฒˆ ํ•˜๋ฉด n์ด ๋˜๋А๋ƒ์˜ ๋‹ต

  4. n์„ 2๋กœ ๊ณ„์† ๋‚˜๋ˆŒ ๋•Œ ๋ช‡ ๋ฒˆ ๋‚˜๋ˆ„๋ฉด ๊ฑฐ์˜ 1์ด ๋˜๋А๋ƒ์— ๋Œ€ํ•œ ๋‹ต

  • x = logn์ผ ๋•Œ x์™€ n์„ ๋น„๊ตํ•˜๋ฉด x๊ฐ€ ๋” ์ž‘๊ณ , n์ด ์ปค์งˆ์ˆ˜๋ก ์—„์ฒญ๋‚˜๊ฒŒ ๋‹ฌ๋ผ์ง„๋‹ค

    • ๊ธ‰๊ฒฉํ•˜๊ฒŒ ๋ณ€ํ•˜๋Š” ๊ฒƒ์„ ์ž‘๊ฒŒ ๋‚˜ํƒ€๋‚ด๊ณ  ์‹ถ์„ ๋•Œ log ์‚ฌ์šฉ!

  • 100์ž๋ฆฌ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋Š” 10์ง„์ˆ˜ ๊ฐ’์€ ์ฝ์„ ์ˆ˜๋„ ์—†์„ ์ •๋„๋กœ ํฐ ๊ฐ’์ด๋‹ค!

  • ์ปดํ“จํ„ฐ ๋ถ„์•ผ์—์„œ log์˜ ๋ฐ‘์€ ํ•ญ์ƒ 2

  • 32๋น„ํŠธ ์ปดํ“จํ„ฐ์˜ ์ฃผ์†Œ ๊ณต๊ฐ„์€ 2^32 = ์•ฝ 40์–ต๊ฐœ ์ฃผ์†Œ

  • image-20200427003641554

    • ๋งˆ์ง€๋ง‰ (1+1+ ...) ์ผ ๋•Œ

      • n/ 2^k = 1

      • n = 2^k

      • k = logn

    • ์ด ๊ด„ํ˜ธ ์ˆ˜๋Š” logn๊ฐœ

    • ๊ทธ๋ž˜์„œ ์ „์ฒด ์‹์„ n์œผ๋กœ ๋ฌถ์œผ๋ฉด nlogn

Big-O Complexity

Big O

Exercises

  1. 2์ง„์ˆ˜ ํ‘œํ˜„์—์„œ logn ๋น„ํŠธ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋Š” ์ˆซ์ž ๋ฒ”์œ„๋Š”?

    • n ๋น„ํŠธ ์ผ ๋•Œ -> 2^n๊ฐœ

    • logn ๋น„ํŠธ ์ผ ๋•Œ -> n๊ฐœ

  2. ์Šค๋ฌด๊ณ ๊ฐœ๊ฐ€ ์ด์ƒ์ ์œผ๋กœ ์ง„ํ–‰๋œ๋‹ค๊ณ  ํ•  ๋•Œ, ๋งž์ถœ ์ˆ˜ ์žˆ๋Š” ๋‹ต์˜ ์ข…๋ฅ˜๋Š” ๋ช‡ ๊ฐ€์ง€์ธ๊ฐ€?

    • ์งˆ๋ฌธ ํ•˜๋‚˜๋‹น ์ •๋‹ต์ด 2๊ฐœ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ์Œ

    • ์งˆ๋ฌธ ๊ฐœ์ˆ˜๋Š” ์ด 20๊ฐœ

    • ์ฆ‰, ๋งž์ถœ์ˆ˜ ์žˆ๋Š” ๋‹ต์˜ ์ข…๋ฅ˜๋Š” 2^20 ๊ฐ€์ง€

  3. n์ด ์ถฉ๋ถ„ํžˆ ํฐ ๊ฐ’ ์ผ ๋•Œ ๋‹ค์Œ์ค‘ ์–ด๋А ๊ฐ’์ด ๋” ํฐ๊ฐ€?

    1. 2n < n^2

      • ์ˆ˜๊ฐ€ ๋ฌดํ•œ๋Œ€๋กœ ํด ๊ฒฝ์šฐ n ์•ž์˜ ์ƒ์ˆ˜๋Š” ๋ฌด์‹œํ•  ์ˆ˜ ์žˆ๊ณ , n๋ณด๋‹ค n^2์˜ ์ƒ์Šน๋Ÿ‰์ด ํ›จ์”ฌ ํฌ๊ธฐ ๋•Œ๋ฌธ

    2. 2^(n/2) < โˆš(3^n)

      • โˆš(3^n) = 3^(n/2)

      • ์ฆ‰, 2^n ๊ณผ 3^n์„ ๋น„๊ตํ•˜๋ฉด 3^n์ด ๋” ํฌ๋‹ค

    3. 2^(nlogn) > n!

      • ๋ฐ‘์ด 2๋ผ๊ณ  ํ•˜๋ฉด,

      • n^n > n! ์ด๋‹ค

    4. log2^(2n) < nโˆšn

      • 2n < nโˆšn

  4. x = loga(yz) ์ผ๋•Œ x๋ฅผ 2๋ฅผ ๋ฐ‘์œผ๋กœ ํ•˜๋Š” ๋กœ๊ทธ๋“ค๋กœ ํ‘œํ˜„ํ•˜์‹œ์˜ค. ๋‹จ, ๋กœ๊ทธ ํ•จ์ˆ˜์˜ ์ธ์ž๋Š” ๋ชจ๋‘ ๋ฌธ์ž ํ•˜๋‚˜์—ฌ์•ผ ํ•œ๋‹ค.

  5. ๋‹ค์Œ ํ•จ์ˆ˜๋“ค์˜ ์—ญํ•จ์ˆ˜๋ฅผ ๊ตฌํ•˜์‹œ์˜ค

    1. f(x) = log(x-3) -5

      • f^-1(x) = 2^(x+5) +3

    2. f(x) = 3 log(x+3) +1

    3. 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

Image from iOS

Image from iOS

Image from iOS

4. ๊ธฐ์ดˆ์ˆ˜์‹

master crm

5. ์žฌ๊ท€

  • ์žฌ๊ท€๋ž€ ์ž๊ธฐ ์ž์‹ ์„ ํ˜ธ์ถœํ•˜๋Š” ํ•จ์ˆ˜

  • (๋๋‚  ์ˆ˜ ์žˆ๋Š” ๊ฐ€?)

    • ํ•จ์ˆ˜๋Š” ์ž…๋ ฅ์ด ์žˆ์œผ๋ฉฐ, ์ž๊ธฐ ์ž์‹ ์˜ ์ž…๋ ฅ๊ณผ ๋™์ผํ•œ ์ž…๋ ฅ์œผ๋กœ ์ž๊ธฐ ์ž์‹ ์„ ํ˜ธ์ถœํ•˜๋ฉด ๋‹น์—ฐํžˆ ๋๋‚  ์ˆ˜ ์—†์Œ

    • ๋‹ค๋ฅธ ์ž…๋ ฅ์œผ๋กœ ๋๋‚ผ ์ˆ˜ ์žˆ๋‹ค!

  • ํ•จ์ˆ˜๋ž€ ์–ด๋–ค ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ฝ”๋”ฉํ•œ ๊ฒƒ

    • ์–ด๋–ค ๋ฌธ์ œ์˜ ๋‹จ ํ•œ ์ผ€์ด์Šค๋งŒ์„ ํ•ด๊ฒฐํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹˜!

      • ์ œ๋Œ€๋กœ ์ฝ”๋”ฉ ๋œ ๊ฒƒ์ด๋ผ๋ฉด ํ•ด๊ฒฐํ•˜๋Š” ๋ฌธ์ œ์˜ ๋ชจ๋“  ์ผ€์ด์Šค๋“ค์„ ํ•ด๊ฒฐํ•ด์•ผ ํ•จ

  • ์ˆ˜ํ•™์  ๊ท€๋‚ฉ๋ฒ• ์ฆ๋ช… ์‚ฌ์šฉ ๊ฐ€๋Šฅ

    1. n์ด 0์ผ ๋•Œ ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ์Œ

    2. n-1์—์„œ ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ์œผ๋ฉด n์—์„œ๋„ ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ๋‹ค

      • ์œ„ ๋‘ ๊ฐ€์ง€๊ฐ€ ์‚ฌ์‹ค์ด๋ฉด ๋ชจ๋“  ๊ฐ€๋Šฅํ•œ n์— ๋Œ€ํ•ด ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด ์‚ฌ์‹ค

Last updated

Was this helpful?