๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
[์๊ณ ๋ฆฌ์ฆ] ์ ํ๊ฒ์, ์ด์ง๊ฒ์, ํธ๋ฆฌ๊ตฌ์กฐ(BFS, DFS) ๋ณธ๋ฌธ
[์๊ณ ๋ฆฌ์ฆ] ์ ํ๊ฒ์, ์ด์ง๊ฒ์, ํธ๋ฆฌ๊ตฌ์กฐ(BFS, DFS)
์ง์ง์ํ์นด 2022. 9. 30. 10:59220930 ์์ฑ
<๋ณธ ๋ธ๋ก๊ทธ๋ "๊ฐ์ฅ ์ฌ์ด ๋ ํ_์๊ณ ๋ฆฌ์ฆ ์ฒซ๊ฑธ์ํธ python ํธ"์ ์์ ๋ฅผ ์ฐธ๊ณ ํด์ ๊ณต๋ถํ๋ฉฐ ์์ฑํ์์ต๋๋ค>
1๏ธโฃ์ ํ๊ฒ์
: ๋ฐ์ดํฐ๋ฅผ ๋ฆฌ์คํธ์ ์ ์ฅํ๊ณ ํด๋น ๋ฆฌ์คํธ์ ๋งจ ์๋ถํฐ ๋๊น์ง ์์๋๋ก ์กฐ์ฌํ์ฌ ์ํ๋ ๋ฐ์ดํฐ ์ฐพ๊ธฐ
: ๊ฐ์ ์ฐพ์ ๋๊น์ง ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ ๊ฒ์ํด์ผ ํ๋ฏ๋ก, ๋ฐ์ดํฐ ์๊ฐ ์ฆ๊ฐํ๋ฉด ์ฒ๋ฆฌ์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค
- ๋ฐ์ดํฐ ์ n์ด๋ผ ํ๋ฉด ๋น๊ตํ์์ ํ๊ท ์ (n+1) / 2
- O(n)
# ์ ํ๊ฒ์
# ์ํ๋ ๊ฐ ์ฐพ๊ธฐ
num_list = [23, 12, 55, 32, 45, 76, 88, 52]
def linear (n) :
for i in num_list :
if i == n :
return True
return False
print(linear(5))
# result
# False
2๏ธโฃ ์ด์ง๊ฒ์
: ๋ฐ์ดํฐ ์๊ฐ ๋์ด๋๋ ๋น ๋ฅธ ์๋๋ก ๊ฒ์์ ์ฒ๋ฆฌํ๊ธฐ
: ๊ฒ์ ๋ฒ์๋ฅผ ์์ด๋ ๋ค์ ์ ๋ฐ์ผ๋ก ๋๋ ๊ฒ์ํ๋ ๊ฒ์ ๋ฐ๋ณต
: ๋ฆฌ์คํธ์ ์ผ์ชฝ ๋๊ณผ ์ค๋ฅธ์ชฝ ๋์์๋ถํฐ ์ฐพ๋ ์์น๋ฅผ ์ ๋ฐ์ผ๋ก ์ขํ๋ฉด์ ๊ฒ์
- ๋ฐ์ดํฐ ์๊ฐ ์ฆ๊ฐํ์ ๋ ๋น๊ต ํ์๋ก ๋ํ๋จ
- ์ฒ๋ฆฌ ์๋๋ ๋ ๋น ๋ฅด์ง๋ง, ์ฌ์ ์ ๋ฐ์ดํฐ๋ฅผ ์ค๋ฆ์ฐจ์, ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ ํ์๊ฐ ์์
- O(logn)
# ์ด์ง๊ฒ์
# ๋ฆฌ์คํธ์ ์ผ์ชฝ ๋๊ณผ ์ค๋ฅธ์ชฝ ๋์์๋ถํฐ ์ฐพ๋ ์์น๋ฅผ ์ ๋ฐ์ผ๋ก ์ขํ๋ฉด์ ๊ฒ์
data = [10, 15 , 22, 26, 38, 42, 56, 61]
def binary_search (data, value) :
left = 0
right = len(data) - 1
while left <= right :
mid = (left + right) // 2
if data[mid] == value :
return mid
elif data[mid] < value :
left = mid + 1
else :
right = mid - 1
return False
print(binary_search(data, 61))
# result
# 7
3๏ธโฃ ํธ๋ฆฌ๊ตฌ์กฐ ํ์
: ๋ฆฌ์คํธ์ ์ ์ฅ๋ ๊ฐ๋จํ ๋ฐ์ดํฐ๋ฟ๋ง ์๋๋ผ ๊ณ์ธต ๊ตฌ์กฐ์ ๋ฐ์ดํฐ๋ฅผ ๊ฒ์
: ํธ๋ฆฌ๊ตฌ์กฐ๋, ์๊ณผ ์ ์ ์ฌ์ฉํด ๊ณ์ธต ๊ตฌ์กฐ์ ๋ถ๊ธฐ๋ฅผ ํํ! ๊ฐ์ง๊ฐ ๋ฒ์ด์๋ ๊ฒ์ฒ๋ผ ๋ณด์ด๋ฏ๋ก ํธ๋ฆฌ ๊ตฌ์กฐ๋ผ ๋ถ๋ฆผ
: ๊ฐ ์์ ๋ ธ๋ (node), ์ ์ ์์ง (edge)
- ๋๋น ์ฐ์ ํ์ (breadth - first search)
- ํ์์ ์์ํ๋ ๊ณณ์์๋ถํฐ ๊ฐ๊น์ด ๊ฒ์ ๋์ดํ๊ณ ๊ฐ๊ฐ์ ์์ธํ ์กฐ์ฌํด๋๊ฐ๋ ๋ฐฉ๋ฒ
- ํ์ํ ์กฐ๊ฑด์ ๋ถํฉ๋๋ ๊ฒ์ ํ๋๋ง ์ป์ผ๋ฉด ๋๋ฉฐ, ๊ฒฐ๊ณผ๋ฅผ ๋ฐ๊ฒฌ๋ ์์ ์ ์ฒ๋ฆฌ ์ข ๋ฃ ํ ์ ์์ด ์ฒ๋ฆฌ์๋ ๋น ๋ฆ
# ๋๋น์ฐ์ ํ์
# ํธ๋ฆฌ์ ์๋ ๋
ธ๋ ๊ฐ๊ฐ์ ๋ฆฌ์คํธ๋ก ํํ
# ๋ฆฌ์คํธ์ ์ธ๋ฑ์ค๋ฅผ ์์๋๋ก ์ถ๋ ฅ -> ํธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ์์์๋ถํฐ ์ฐจ๋ก๋๋ก ํ์ํ ๊ฒ์
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [ 9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []] # ๋น ๋ฆฌ์คํธ๋ ๊ฐ ๋
ธ๋์ ํ์ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ ์์ญ์ ํ๋ณดํ๋ ค๋ ๊ฒ
data = [0]
while len(data) > 0 :
pos = data.pop(0) # pop : ๋งจ ์์์ ๊บผ๋ด๊ธฐ
print(pos, end = " ")
for i in tree[pos] :
data.append(i) # ๋์ ์ถ๊ฐ
# result
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
- ๊น์ด ์ฐ์ ํ์ (depth - first search)
- ์ํ๋ ๋ฐฉํฅ์ผ๋ก ํ์์ ์งํํ๋ค๊ฐ ๋ ์งํ๋์ง ์์ผ๋ฉด, ์ด์ ์์น๋ก ๋์๊ฐ๋ ๋ฐฉ๋ฒ
- ๋ฐฑํธ๋(backtrack) ์ด๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋ฉฐ, ๋ฌธ์ ์ ๋ชจ๋ ๋ต์ ์ฐพ์ ๋ ์์ฃผ ์ฌ์ฉ
- ์ฌ๊ท๋ฅผ ์ฌ์ฉํ๋ ๊ฒฝ์ฐ๊ฐ ๋ง์
- ๋ชจ๋ ๋ต์ ์ฐพ์ง ์๊ณ ์ ํด์ง ๊น์ด๊ฐ์ง ํ์ํ๋ ๋ฐฉ๋ฒ์๋ ๋ง์ด ์ฌ์ฉ
- ์ ์ ์ํ (pre-order traversal)
- ์ค์ ์์ (in-order traversal))
- ํ์ ์์ (post-order traversal)
# ๊น์ด ์ฐ์ ํ์
# ์ฃผ๋ก ์ฌ๊ท ์ฌ์ฉ
# 1) ์ ์ ์ํ๋ฅผ ์ด์ฉํ ํ์
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [ 9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []] # ๋น ๋ฆฌ์คํธ๋ ๊ฐ ๋
ธ๋์ ํ์ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ ์์ญ์ ํ๋ณดํ๋ ค๋ ๊ฒ
def search(pos) :
print(pos, end = " ") # ์์ ๋
ธ๋๋ฅผ ํ์ํ๊ธฐ ์ ์ ํ์ฌ ๋
ธ๋ ์ถ๋ ฅ
for i in tree[pos] : # ์์ ๋
ธ๋ ํ์
search(i) # ์ฌ๊ท ํ์
search(0)
# result
# 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14
# 2) ํ์ ์ํ๋ฅผ ์ด์ฉํ ํ์
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [ 9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []] # ๋น ๋ฆฌ์คํธ๋ ๊ฐ ๋
ธ๋์ ํ์ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ ์์ญ์ ํ๋ณดํ๋ ค๋ ๊ฒ
def search(pos) :
for i in tree[pos] : # ์์ ๋
ธ๋ ํ์
search(i) # ์ฌ๊ท ํ์
print(pos, end = " ") # ์์ ๋
ธ๋ ํ์ ํ ์ถ๋ ฅ
search(0)
# result
# 7 8 3 9 10 4 1 11 12 5 13 14 6 2 0
# 3) ์ค์ ์ํ๋ฅผ ์ด์ฉํ ํ์
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [ 9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []] # ๋น ๋ฆฌ์คํธ๋ ๊ฐ ๋
ธ๋์ ํ์ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ ์์ญ์ ํ๋ณดํ๋ ค๋ ๊ฒ
def search(pos) :
if len(tree[pos]) == 2 : # ์์ ๋
ธ๋๊ฐ 2๊ฐ ์์ ๋
search(tree[pos][0])
print(pos, end = " ") # ์ผ์ชฝ ๋
ธ๋์ ์ค๋ฅธ์ชฝ ๋
ธ๋ ์ฌ์ด์ ์ถ๋ ฅ
search(tree[pos][1])
elif len(tree[pos]) == 1 : # ์์ ๋
ธ๋๊ฐ 1๊ฐ ์์ ๋
search(tree[pos][0])
print(pos, end = " ")
else :
print(pos, end = " ")
search(0)
# result
# 7 3 8 1 9 4 10 0 11 5 12 2 13 6 14
- ๊ฒฝ๋ก๊ฐ ๋ณต์กํ ๋ชจ๋ ๋
ธ๋ ํ์ํ ๊ฒฝ์ฐ
- ๋๋น ์ฐ์ ํ์ : ํ์ ์ค์ธ ๋ชจ๋ ๋ ธ๋๋ฅผ ์ ์ฅํด์ผ ํจ
- ๊น์ด ์ฐ์ ํ์ : ํ์ฌ ๊ฒฝ๋ก์์ ๋ ธ๋๋ฅผ ์ ์ฅํ๋ ๊ฒ๋ง์ผ๋ก๋ ํ์ ์งํ ๊ฐ๋ฅ (๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋ ์ค์)
- ์ต๋จ์ผ๋ก ๋๋ฌํ ๊ธธ์ ํ๋๋ง ํ์ํ ๊ฒฝ์ฐ
- ๋๋น ์ฐ์ ํ์ : ๋ฐ๊ฒฌ๋ ์์ ์ ์ฒ๋ฆฌ ์ข ๋ฃํจ
- ๊น์ด ์ฐ์ ํ์ : ๋ชจ๋ ๋ ธ๋๋ฅผ ์กฐ์ฌํ ๋ค ์ต๋จ์ธ์ง ์ฌ๋ถ ํ์
'๐ฉโ๐ป ์ปดํจํฐ ๊ตฌ์กฐ > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ ์ํ ํ๋ฐ์ง ๋๋ฐ์ง๐พ] ์ฐ๊ฒฐ๋ฆฌ์คํธ (Linked List) (0) | 2023.06.26 |
---|---|
[์๊ณ ๋ฆฌ์ฆ ์ํ ํ๋ฐ์ง ๋๋ฐ์ง๐พ] ๋น ์ค(Big-O)ํ๊ธฐ๋ฒ (0) | 2023.06.26 |
[์๊ณ ๋ฆฌ์ฆ] ๋ณต์ก๋,๋น ์ค ํ๊ธฐ๋ฒ O, ์๋ฃ๊ตฌ์กฐ(๋ฆฌ์คํธ, ์ฐ๊ฒฐ๋ฆฌ์คํธ) (0) | 2022.09.28 |
[python] class์ def __init__(self) ์ดํดํ๊ธฐ (0) | 2022.09.07 |
[์๊ณ ๋ฆฌ์ฆ] ํด์ํ ์ด๋ธ_๊ตฌํ (0) | 2022.06.17 |