hugDog
Android DevLog
hugDog
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๐Ÿ™Œ Hello? (162)
    • ๐Ÿงฉ์•ˆ๋“œ๋กœ์ด๋“œ (12)
      • ๊ฐœ๋… ์ •๋ฆฌ (5)
      • ๋ฒ„๊ทธ ํ•ด๊ฒฐ (4)
      • ๊ธฐํƒ€ (3)
    • ๐Ÿ”์•Œ๊ณ ๋ฆฌ์ฆ˜ (54)
      • ๊ฐœ๋… (0)
      • ๋ฐฑ์ค€ (48)
      • ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค (6)
    • ๐Ÿ“„๊ฐœ๋ฐœ ์ผ์ง€ (0)
      • FINPO (0)
    • ๐Ÿ”คํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด (71)
      • C++ ์ •๋ฆฌ (49)
      • C++๊ธฐ์ดˆํ”Œ๋Ÿฌ์Šค ์—ฐ์Šต๋ฌธ์ œ (20)
      • Kotlin (2)
    • โญProject (1)
    • ๐ŸšดTIL (13)
      • Clean Code (13)
    • ๐Ÿšฉ๊ธฐํƒ€ (9)
      • ๋ชฉํ‘œ (6)
      • ์ผ์ƒ (3)
      • ๋ฌธ์„œ (0)

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

hELLO ยท Designed By ์ •์ƒ์šฐ.
hugDog
๐Ÿ”์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฐฑ์ค€

[Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 14942๋ฒˆ: ๊ฐœ๋ฏธ

[Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 14942๋ฒˆ: ๊ฐœ๋ฏธ
๐Ÿ”์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฐฑ์ค€

[Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 14942๋ฒˆ: ๊ฐœ๋ฏธ

2022. 1. 21. 19:51
728x90

๋ฌธ์ œ

 

ํ’€์ด

1. ์ฃผ์–ด์ง„ ์ž…๋ ฅ์€ ์–‘๋ฐฉํ–ฅ ๊ฐ„์„ ์ด๋ฏ€๋กœ ๋‹จ๋ฐฉํ–ฅ ๊ฐ„์„ ์œผ๋กœ ๋งŒ๋“ค์–ด์ค˜์•ผํ•จ

2. ํฌ์†Œ๋ฐฐ์—ด ์‚ฌ์šฉ

https://hello-capo.netlify.app/algorithm-sparse-table/

 

๐Ÿงฉ [Algorithm] ํฌ์†Œ ๋ฐฐ์—ด(Sparse Table) ์•Œ๊ณ ๋ฆฌ์ฆ˜ | hello-capo!

ํฌ์†Œ ๋ฐฐ์—ด(Sparse Table) ๋ฐฐ์—ด ์›์†Œ์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋ฌด์กฐ๊ฑด ๋ฐฐ์—ด์˜ length ๊ฐ’๋ณด๋‹ค ์ž‘์€ ๋ฐฐ์—ด ๋ฐ์ดํ„ฐ๊ฐ€ ์ €์žฅ๋˜์ง€ ์•Š์€ ๊ฒฝ์šฐ๊ฐ€ ๋” ๋งŽ์€ ํฌ์†Œ ํ–‰๋ ฌ๊ณผ ๊ฐ™์ด, ํฌ์†Œ ๋ฐฐ์—ด์€ ๋ฐฐ์—ด์˜ ์›์†Œ ์œ„์น˜๊ฐ€ ์—ฐ์†์ ์ด์ง€ ์•Š์€ ๋ฐฐ

hello-capo.netlify.app

3. LCA์™€ ์œ ์‚ฌํ•˜๊ฒŒ ๋…ธ๋“œ ํƒ์ƒ‰

https://cyberflower.github.io/2019/07/22/LCA.html

 

LCA(Least Common Ancestor) - CyberFlower Algorithm

 

cyberflower.github.io

 

์ฝ”๋“œ

import sys, math
input = sys.stdin.readline

#์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋ฅผ ๋‹จ๋ฐฉํ–ฅ์œผ๋กœ ๋ฐ”๊ฟˆ
def dfs(x):
    visited[x] = True
    for next, power in tmp[x]:
        if not visited[next]:
            arr[next] = [x, power]
            dfs(next)

#ํฌ์†Œ ํ–‰๋ ฌ ์ด์šฉ
def lca(j, w):
    for i in range(int(math.log2(n)), -1, -1):
        if spareTable[i][j][1] <= w and spareTable[i][j][0] != 0:
            w -= spareTable[i][j][1]
            j = spareTable[i][j][0]
    return j
    
n = int(input().rstrip())
ant = [0] + [int(input().rstrip()) for _ in range(n)] #๊ฐœ๋ฏธ ์—๋„ˆ์ง€
arr = [[] for _ in range(n + 1)] #๋‹จ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„
tmp = [[] for _ in range(n + 1)] #์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(์ž„์‹œ)
visited = [False] * (n + 1) #๋ฐฉ๋ฌธ ์—ฌ๋ถ€

#์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„ ์ž…๋ ฅ
for _ in range(n - 1):
    a, b, c = map(int, input().rstrip().split())
    tmp[b].append([a, c])
    tmp[a].append([b, c])

#๋‹จ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„๋กœ ๋งŒ๋“ค์–ด์คŒ
dfs(1)
arr[1] = [1, 0]

#ํฌ์†Œ ํ–‰๋ ฌ ์ƒ์„ฑ
spareTable = [[[0, 0] for _ in range(n + 1)] for _ in range(int(math.log2(n)) + 1)]
for i in range(1, n + 1):
    spareTable[0][i] = arr[i]

for k in range(1, int(math.log2(n)) + 1):
    for i in range(1, n + 1):
        next, power = spareTable[k - 1][i]
        spareTable[k][i] = [spareTable[k - 1][next][0], power + spareTable[k - 1][next][1]]

for i in range(1, n + 1):
    print(lca(i, ant[i]))

 

๋งˆ๋ฌด๋ฆฌ

๊ฐœ์ธ์ ์œผ๋กœ ๋„ˆ๋ฌด ์–ด๋ ค์› ๋‹ค... ๊ตฌ๊ธ€๋งํ•ด์„œ ๊ฒจ์šฐ ํ’ˆ

 

728x90
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ (์ƒˆ์ฐฝ์—ด๋ฆผ)
  • ๋ฌธ์ œ
  • ํ’€์ด
  • ์ฝ”๋“œ
  • ๋งˆ๋ฌด๋ฆฌ
'๐Ÿ”์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฐฑ์ค€' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 1695๋ฒˆ: ํŒฐ๋ฆฐ๋“œ๋กฌ ๋งŒ๋“ค๊ธฐ / ํŒŒ์ด์ฌ ๋ฉ”๋ชจ๋ฆฌ์ดˆ๊ณผ ํ•ด๊ฒฐ
  • [Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 17404๋ฒˆ: RGB๊ฑฐ๋ฆฌ 2
  • [Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 16437๋ฒˆ: ์–‘ ๊ตฌ์ถœ ์ž‘์ „
  • [Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 17616๋ฒˆ: ๋“ฑ์ˆ˜ ์ฐพ๊ธฐ
hugDog
hugDog
์•ˆ๋“œ๋กœ์ด๋“œ ๊ณต๋ถ€ ์ค‘์ธ ํ•™์ƒ์ž…๋‹ˆ๋‹ค!

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.