์‹ ์ฐฌ์ˆ˜-์ž๋ฃŒ๊ตฌ์กฐ์™€์•Œ๊ณ ๋ฆฌ์ฆ˜

ํ•œ๊ตญ์™ธ๋Œ€ ์‹ ์ฐฌ์ˆ˜ ๊ต์ˆ˜๋‹˜ ์ž๋ฃŒ๊ตฌ์กฐ์™€์•Œ๊ณ ๋ฆฌ์ฆ˜

์ž๋ฃŒ๊ตฌ์กฐ(Data Structure), ์•Œ๊ณ ๋ฆฌ์ฆ˜(Algoritm)

์ž๋ฃŒ: data -> [์ €์žฅ๊ณต๊ฐ„(memory) + ์ฝ๊ธฐ,์“ฐ๊ธฐ,์‚ฝ์ž…,์‚ญ์ œ,ํƒ์ƒ‰(์—ฐ์‚ฐ)] => ๊ตฌ์กฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜: data (์œ ํ•œํ•œ ํšŸ์ˆ˜์˜ ์—ฐ์‚ฐ๋“ค) ์ž…๋ ฅ-> ์ •๋‹ต ์ถœ๋ ฅ

์ž๋ฃŒ๊ตฌ์กฐ (์˜ˆ:) 1. ๋ณ€์ˆ˜(variable) 2.๋ฐฐ์—ด(array), ๋ฆฌ์ŠคํŠธ(list)
์•Œ๊ณ ๋ฆฌ์ฆ˜ (์˜ˆ:) 100๊ฐœ์˜ ์ •์ˆ˜: ๋ฆฌ์ŠคํŠธ A:์ž…๋ ฅ -> ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ:์ถœ๋ ฅ

explnation.py
1
2
3
4
5
6
7
8
9
10
11
12
a = 5 # ์“ฐ๊ธฐ ์—ฐ์‚ฐ
print(a) # ์ฝ๊ธฐ ์—ฐ์‚ฐ

A = [3, -1, 5, 7]
'''
์ ‘๊ทผ: ์›์†Œ์˜ index
์ฝ๊ธฐ, ์“ฐ๊ธฐ: A[3]
์‚ฝ์ž…: A.append(9) # ๋งจ ๋์— ์ถ”๊ฐ€,
A.insert(0, 100) # 0๋ฒˆ์งธ idx์— 100 ๊ฐ’ ์ถ”๊ฐ€
์‚ญ์ œ: A.pop() # ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ์ œ๊ฑฐ,
A.pop(2) # 2๋ฒˆ์จฐ idx ๊ฐ’ ์ œ๊ฑฐ
'''

์ธ๋ฅ˜ ์ตœ์ดˆ์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜

ac, ํŽ˜๋ฅด์‹œ์•„, Algebra ์ˆ˜ํ•™์ž Al-khwarizmi
-> Algorismus + Arithmos => [Algorithm]

์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(GCD)๊ณ„์‚ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜ by Euclid

greatest_common_divisor.py
1
2
3
4
5
def gcd(a, b):
while a!=0 and b!=0:
if a>b: a = a-b
else: b = b-a
return a+b

big-O

date: 2022-09-20 23:26:03
Big O notation
Big ฮฉ notation/ Big ฮธ notation
Big O notation

์‹œ๊ฐ„ ๋ณต์žก๋„(์ ๊ทผ์  ์‹คํ–‰ ์‹œ๊ฐ„, asymptotic runtime)

  • O(big-O): ์‹œ๊ฐ„์˜ ์ƒํ•œ
    ๋ฐฐ์—ด์˜ ๋ชจ๋“  ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ O(N)์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์ง€๋งŒ
    O(N^3),O(N^2),O(2^N)๋„ ์˜ณ์€ ํ‘œํ˜„์ด๋‹ค.
    ๋‹ค์‹œ ๋งํ•˜์ž๋ฉด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์€ ์ ์–ด๋„ ์ด๋“ค ์ค‘ ํ•˜๋‚˜๋ณด๋‹ค ๋น ๋ฅด๊ธฐ๋งŒ ํ•˜๋ฉด ๋œ๋‹ค.

  • ฮฉ (big-Omega): ์‹œ๊ฐ„์˜ ํ•˜ํ•œ
    ๋ฐฐ์—ด์˜ ๋ชจ๋“  ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ฮฉ(N) ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ ฮฉ(logN) ํ˜น์€ ฮฉ(1)๋กœ๋„ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.๊ฒฐ๊ตญ, ํ•ด๋‹น ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ฮฉ ์ˆ˜ํ–‰ ์‹œ๊ฐ„๋ณด๋‹ค ๋น ๋ฅผ ์ˆ˜ ์—†๊ฒŒ ๋œ๋‹ค.

  • ฮธ (big-theta): ๋”ฑ ๋งž๋Š” ์ˆ˜ํ–‰ ์‹œ๊ฐ„
    ฮธ๋Š” O์™€ ฮฉ ๋‘˜ ๋‹ค ์˜๋ฏธํ•œ๋‹ค. ์ฆ‰, ์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰์‹œ๊ฐ„์ด O(N)์ด๋ฉด์„œ ฮฉ(N)์ด๋ผ๋ฉด, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์„ ฮธ(N)๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

๊ณต๊ฐ„ ๋ณต์žก๋„

  • ์‚ฌ์šฉํ•˜๋Š” ์Šคํƒ ๊ณต๊ฐ„ ๋˜๋Š” ๊ณต๊ฐ„ ๋ณต์žก๋„ ๊ณ„์‚ฐ์— ํฌํ•จ๋œ๋‹ค.
  • ํ•จ์ˆ˜๋“ค์ด ํ˜ธ์ถœ ์Šคํƒ์— ๋™์‹œ์— ์กด์žฌํ•˜์ง€ ์•Š์œผ๋ฉด ๊ณ„์‚ฐ์— ํฌํ•จ๋˜์ง€ ์•Š๋Š”๋‹ค.

  1. ์ƒ์ˆ˜ํ•ญ์€ ๋ฌด์‹œํ•˜๋ผ
    O(N) = O(2N)
  2. ์ง€๋ฐฐ์ ์ด์ง€ ์•Š์€ ํ•ญ์€ ๋ฌด์‹œํ•˜๋ผ
    O(N^2) = O(N^2 + N)
  3. ์—ฌ๋Ÿฌ ๋ถ€๋ถ„์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ์•Œ๊ณ ๋ฆฌ์ฆ˜: ๋ง์…ˆ vs ๊ณฑ์…ˆ
  • O(A+B)
    ๋งŒ์•ฝ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด โ€œA ์ผ์„ ๋ชจ๋‘ ๋๋งˆ์นœ ํ›„์— B์ผ์„ ์ˆ˜ํ–‰ํ•˜๋ผโ€์˜ ํ˜•ํƒœ๋ผ๋ฉด A์™€ B์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์„ ๋”ํ•ด์•ผ ํ•œ๋‹ค.
  • O(A*B)
    ๋งŒ์•ฝ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด โ€œA ์ผ์„ ํ•  ๋–„๋งˆ๋‹ค B ์ผ์„ ์ˆ˜ํ–‰ํ•˜๋ผโ€์˜ ํ˜•ํƒœ๋ผ๋ฉด A์™€ B์˜ ์ˆ˜ํ–‰์‹œ๊ฐ„์„ ๊ณฑํ•ด์•ผ ํ•œ๋‹ค.