문득 이런 생각이 들었습니다.
저항이 여러 개 직렬로 연결되어 있을 때 저항 1개의 전압강하는 전압강하 분배 법칙에 의해 쉽게 구할 수 있습니다.
예시로 전압원이 10[V]이고 저항이 1옴, 2옴, 3옴, 4옴이라면 1옴에 걸리는 전압강하는 10 * 1 / (1 + 2 + 3 + 4) = 1[V]가 됩니다.
그리고 1옴과 2옴이 연속적으로 연결되어 있으니 2개의 전압강하 합을 구할려면 어떻게 해야 할까요?
10 * (1 + 2) / (1 + 2 + 3 + 4) = 3[V]가 됩니다.
이것을 통해 공식을 간단하게 하면 다음과 같이 나옵니다.
(부분 구간의 전압강하 합) = (전압원) * (부분 구간의 저항 합) / (합성 저항)
여기서 합성 저항은 직렬 회로이니 모든 저항들의 합이 됩니다.
위 내용을 Python으로 구현해보면 다음과 같습니다.
예시는 1옴부터 8옴까지 직렬 회로로 이루어질 때 전압원을 입력하면 1옴부터 4옴까지 걸린 전압강하 합을 구하는 소스 코드입니다.
import sys
input = sys.stdin.readline
V:int = int(input().rstrip()) # 전압원
L:list = [1, 2, 3, 4, 5, 6, 7, 8] # 저항 리스트
R_T = sum(L) # 합성 저항
start, end = 0, 3 # 부분 구간 시작점과 끝점(여기서는 1옴 저항부터 4옴 저항까지)
R:int = 0 # 부분 구간의 저항 합
# 브루트 포스로 일일히 다 더합니다.
for index in range(start, end + 1, 1) :
R += L[index]
result:float = V * R / sum(L)
print(result)저항들의 합을 일일히 하나씩 다 더해서 부분 구간의 저항 합을 구하고 전압 분배 법칙에 따라 부분 구간의 전압강하 합을 구합니다.
저항 리스트의 크기가 고정일 때 만약 저항을 없애고 싶다면 저항값을 0옴으로 설정하면 됩니다.
예시로 [1, 2, 3, 4, 5, 6, 7, 8]에서 5옴 저항을 제거하고 싶다면 [1, 2, 3, 4, 0, 6, 7, 8]으로 변경하면 되는 것이죠.
즉, 저항의 값을 update할 때는 O(1)의 시간 복잡도를 가집니다.
하지만 부분 구간 전압 강하를 구할려면 일일히 다 더하고 다른 query가 호출되면 다시 일일히 더해야 하는 문제점이 발생합니다.
이 때 query 하나 호출할 때 O(N)의 시간 복잡도를 가지게 되어 브루트 포스 방식은 저항의 개수가 매우 적을 때 유용합니다.
그러면 만약 저항들의 값이 모두 고정인 전기 회로인데 부분 구간 전압 강하를 아주 빠르게 구할려면 어떻게 해야 할까요?
이럴 때는 누적합(prefix sum) 알고리즘을 사용하도록 하겠습니다.
import sys
input = sys.stdin.readline
V:int = int(input().rstrip()) # 전압원
L:list = [1, 2, 3, 4, 5, 6, 7, 8] # 저항 리스트
# 1. 누적합(Prefix Sum) 배열 전처리 (O(N))
# 인덱스 에러 방지를 위해 크기를 N + 1로 잡고 0으로 초기화합니다.
N:int = len(L)
P:list = [0] * (N + 1)
for index in range(N) :
P[index + 1] = P[index] + L[index]
# 2. 부분 구간 지정
start, end = 0, 3 # 1옴 저항부터 4옴 저항까지
# 3. 누적합을 활용한 구간 저항 합 조회 (O(1))
# 루프 없이 단 한 번의 뺄셈 연산으로 구간 합을 구합니다.
R:int = P[end + 1] - P[start]
# 전체 합성 저항은 누적합 배열의 가장 마지막 원소와 정확히 일치합니다.
R_T:int = P[-1]
# 4. 최종 부분 전압강하 계산
result:float = V * R / R_T
print(result)모든 저항의 값이 고정이라면 런타임 전처리 과정을 통해 누적합 리스트를 생성하고 P[end + 1] - P[start]로 부분 구간 저항들의 합을 구하는 쿼리 호출 하나당 O(1) 시간 복잡도로 아주 빠르게 구합니다.
예시로 [1, 2, 3, 4, 5, 6, 7, 8]이면 누적합 리스트는 [0, 1, 3, 6, 10, 15, 21, 28, 36]이 되고 1옴 저항(index 0)부터 4옴 저항(index 3)까지의 저항들의 합을 구할려면 P[3 + 1] - P[0] = 10 - 0 = 10옴으로 바로 구해집니다.
단, 만약 저항 1개 이상 바뀌게 되면 누적합 리스트를 다시 처음부터 만들어야 하므로 update 발생 시 O(N)의 시간 복잡도를 가집니다.
지금까지 브루트 포스 방식과 누적합 방식으로 해서 각각 다음과 같은 결론이 나옵니다.
| 브루트 포스(Brute Force) 방식 | 누적합(Prefix Sum) 방식 | |
| query 1개 호출 시간 복잡도 | O(N) (느림) | O(1) (빠름) |
| 1개의 value update 시간 복잡도 | O(1) (빠름) | O(N) (느림) |
| 사용 목적 | 저항의 개수가 적을 때 유용함 | 모든 저항의 값이 고정일 때 유용함 |
그런데 잘 생각해보니 "만약 저항들의 개수가 매우 많고 그와 동시에 빈번한 update가 발생하면 이 두 가지 방식으로는 무리인데?"입니다.
예시로 저항의 개수가 1024개이고 업데이트가 1초에 평균 1024개의 저항 값이 바뀐다고 가정합니다.
이 때 브루트 포스 방식으로 하면 부분 구간 전압 강하의 합을 최대 1024개의 전압강하들을 일일히 다 더해야 해서 너무 느리고, 반대로 누적합은 1초에 평균 1024개의 저항 값이 바뀌어 update하는데 너무 느립니다.
거기에 만약 어떤 송전선로의 저항 샘플 개수를 2^16개로 해서 대규모 전기 회로로 변환해서 아주 빠르게 구해야 하는 시스템이라면? 위 2가지 방식으로는 한계가 있습니다.
그래서 update와 query 호출을 둘 다 O(log N) 시간 복잡도를 가져야 1024번 연산해야 하는 것을 단 10번의 연산으로 줄어들게 되며 특히 2^32번 연산해야 할 것을 단 32번만에 연산이 끝나서 매우 효과적인 시스템을 구현할 수 있습니다.
이진 트리(Binary Tree) 형식으로 구현하면 될 것 같고 여기서는 구간(segment)을 다뤄야 하니 세그먼트 트리(Segment Tree) 알고리즘을 활용하면 될 것 같습니다.
이것을 Python 소스 코드로 구현하면 다음과 같습니다.
import sys
input = sys.stdin.readline
# 소스 코드가 많이 어렵죠?
# 이 자료구조의 장점은 update와 query 모두 O(log N)의 시간 복잡도를 가져서 매우 효율적인 성능이 나옵니다.
# 단점은 구현하기가 진짜 어렵습니다.
class SegmentTree:
def __init__(self, data:list) :
self.n = len(data)
# 4N 크기로 트리 배열을 안전하게 정적 할당합니다.
self.tree = [0] * (4 * self.n)
self._build(data, 1, 0, self.n - 1)
def _build(self, data:list, node:int, start:int, end:int) :
"""초기 저항 리스트를 받아 세그먼트 트리를 구축합니다 (O(N))"""
if start == end :
self.tree[node] = data[start]
return
mid = (start + end) // 2
self._build(data, 2 * node, start, mid)
self._build(data, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def update(self, index:int, value:int):
"""특정 위치의 저항을 변경/추가/삭제(0) 합니다 (O(log N))"""
self._update(1, 0, self.n - 1, index, value)
def _update(self, node:int, start:int, end:int, index:int, value:int) :
if start == end :
self.tree[node] = value
return
mid = (start + end) // 2
if start <= index <= mid:
self._update(2 * node, start, mid, index, value)
else :
self._update(2 * node + 1, mid + 1, end, index, value)
# 하위 노드가 바뀌었으므로 부모 노드의 구간합을 실시간 갱신합니다.
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def sum_query(self, left:int, right:int) -> int :
"""지정한 부분 구간 [left, right]의 저항 합을 구합니다 (O(log N))"""
return self._query(1, 0, self.n - 1, left, right)
def _query(self, node:int, start:int, end:int, left:int, right:int) -> int :
if right < start or end < left :
return 0
if left <= start and end <= right :
return self.tree[node]
mid = (start + end) // 2
p1 = self._query(2 * node, start, mid, left, right)
p2 = self._query(2 * node + 1, mid + 1, end, left, right)
return p1 + p2
def get_total_resistance(self) -> int :
"""루트 노드(1번)에서 계통의 전체 합성 저항 R_T를 뿜어냅니다 (O(1))"""
return self.tree[1]
V:int = int(input().rstrip()) # 전압원 입력 (예: 100)
L:list = [1, 2, 3, 4, 5, 6, 7, 8] # 초기 저항 리스트
# 세그먼트 트리 초기화
segtree = SegmentTree(L)
# 테스트 케이스 1 : 초기 상태에서 [1옴 ~ 4옴] 구간(인덱스 0~3)의 부분 전압강하
start, end = 0, 3
R = segtree.sum_query(start, end)
R_T = segtree.get_total_resistance() # 루트 노드 값 추출
result = V * R / R_T
print(f"[초기 상태] 구간 저항합 : {R}Ω / 총 저항: {R_T}Ω")
print(f"-> 구간 전압강하 : {result:.4f}V")
# 테스트 케이스 2 : 가변저항 조절 혹은 소자 변경 (O(log N))
# 1번 인덱스의 2옴 저항을 '0옴(Wire 단락)'으로 전격 교체!
target_index, new_value = 1, 0
segtree.update(target_index, new_value)
# 변경 후 같은 구간의 부분 전압강하 재측정 (O(log N))
R = segtree.sum_query(start, end)
R_T = segtree.get_total_resistance() # 실시간으로 고쳐진 루트 값 추출
result = V * R / R_T
print(f"[소자 변경 후] 구간 저항합: {R}Ω / 총 저항: {R_T}Ω")
print(f"-> 구간 전압강하: {result:.4f}V")이 때 0-based index으로 했습니다.
초기 세그먼트의 상태를 표현하면 아래와 같습니다.
[0-7](36) <- 최상위 루트 (R_T)
/ \
[0-3](10) [4-7](26)
/ \ / \
[0-1](3) [2-3](7) [4-5](11) [6-7](15)
/ \ / \ / \ / \
[0](1) [1](2) [2](3) [3](4) [4](5) [5](6) [6](7) [7](8) <- 리프 노드 (소자)이렇게 되어 있습니다. 여기서 []는 index 범위, ()는 해당 부분 구간의 합입니다.
여기서 start, end 쿼리 호출("0 3")을 하면 해당 세그먼트 트리에서 [0-3]의 값을 호출하여 O(log N) 시간 복잡도로 10옴을 바로 구할 수 있습니다.
그리고 update로 2옴 저항을 없애는 작업(0옴 처리)를 해서 세그먼트 트리로 표현하면 다음과 같습니다.
[0-7](34)* <- 실시간 고쳐진 전체 저항 (36 -> 34)
/ \
[0-3](8)* [4-7](26) (우측 트리는 통째로 유지)
/ \ / \
[0-1](1)* [2-3](7) [4-5](11) [6-7](15)
/ \ / \ / \ / \
[0](1) [1](0)* [2](3) [3](4) [4](5) [5](6) [6](7) [7](8)이제 다시 sum_query 호출("0 3")을 하면 8옴으로 출력하게 됩니다.
그 뒤 V = 100[V]로 입력하면 터미널에 다음과 같은 결과가 출력됩니다.
[초기 상태] 구간 저항합 : 10Ω / 총 저항: 36Ω
-> 구간 전압강하 : 27.7778V
[소자 변경 후] 구간 저항합: 8Ω / 총 저항: 34Ω
-> 구간 전압강하: 23.5294V
그러면 만약 연속된 부분 구간의 저항들의 값을 한꺼번에 바꿀려면 어떻게 해야 할까요?
저항 1개의 값을 바꿀려면 O(log N)의 시간 복잡도를 가지나 만약 여러 개의 저항들을 바꿀려면 최대 O(N log N)의 시간 복잡도를 가집니다.
그런데 연속된 부분 구간의 저항들의 값을 한꺼번에 바꾸고 싶은데 O(N log N)의 시간 복잡도를 가지면 골치 아프겠죠?
그래서 지연 전파를 활용해서 (여기 구간은 업데이트 하기로 예약했으니 해당 구간의 끝부분에 lazy tag를 추가해서 나중에 갱신할게요)라고 하면 O(log N)의 시간복잡도를 가지고 나중에 query 호출하면 그 때서야 진짜 갱신을 하면서 구간합을 빠르게 구할 수 있습니다.
import sys
input = sys.stdin.readline
# 재귀 한도 증가
sys.setrecursionlimit(1 << 20)
class DualLazySegmentTree:
def __init__(self, data: list):
self.n = len(data)
self.tree = [0] * (4 * self.n)
# 두 종류의 Lazy 태그 배열 준비
self.lazy_set = [-1] * (4 * self.n) # -1이면 Set 태그 없음
self.lazy_add = [0] * (4 * self.n) # 0이면 Add 태그 없음
self._build(data, 1, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
self.tree[node] = data[start]
return
mid = (start + end) // 2
self._build(data, node * 2, start, mid)
self._build(data, node * 2 + 1, mid + 1, end)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def _push(self, node, start, end):
"""쌓여있는 set 태그와 add 태그를 자식에게 밀어냅니다."""
# 1. 덮어쓰기(Set) 태그가 존재할 경우 먼저 처리
if self.lazy_set[node] != -1:
value_set = self.lazy_set[node]
self.tree[node] = (end - start + 1) * value_set
if start != end:
# 자식들에게 Set 태그를 넘기고, 자식들이 예전에 갖고 있던 Add 태그는 폐기!
self.lazy_set[node * 2] = value_set
self.lazy_add[node * 2] = 0
self.lazy_set[node * 2 + 1] = value_set
self.lazy_add[node * 2 + 1] = 0
self.lazy_set[node] = -1
# 2. 더하기(Add) 태그가 존재할 경우 이어서 처리
if self.lazy_add[node] != 0:
value_add = self.lazy_add[node]
self.tree[node] += (end - start + 1) * value_add
if start != end:
# 자식들의 Add 태그에 누적
self.lazy_add[node * 2] += value_add
self.lazy_add[node * 2 + 1] += value_add
self.lazy_add[node] = 0
# ---------------------------------------------------------
# Update 1: 구간 덮어쓰기 (Set)
# ---------------------------------------------------------
def update_set(self, left, right, value):
self._update_set(1, 0, self.n - 1, left, right, value)
def _update_set(self, node, start, end, left, right, value):
self._push(node, start, end)
if right < start or end < left:
return
if left <= start and end <= right:
self.lazy_set[node] = value
self.lazy_add[node] = 0 # 덮어쓸 거니까 기존 add 태그 파기
self._push(node, start, end)
return
mid = (start + end) // 2
self._update_set(node * 2, start, mid, left, right, value)
self._update_set(node * 2 + 1, mid + 1, end, left, right, value)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
# ---------------------------------------------------------
# Update 2: 구간 더하기 (Add)
# ---------------------------------------------------------
def update_add(self, left, right, value):
self._update_add(1, 0, self.n - 1, left, right, value)
def _update_add(self, node, start, end, left, right, value):
self._push(node, start, end)
if right < start or end < left:
return
if left <= start and end <= right:
self.lazy_add[node] += value
self._push(node, start, end)
return
mid = (start + end) // 2
self._update_add(node * 2, start, mid, left, right, value)
self._update_add(node * 2 + 1, mid + 1, end, left, right, value)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
# ---------------------------------------------------------
# Query: 구간 합 (Sum)
# ---------------------------------------------------------
def query(self, left, right):
return self._query(1, 0, self.n - 1, left, right)
def _query(self, node, start, end, left, right):
self._push(node, start, end)
if right < start or end < left:
return 0
if left <= start and end <= right:
return self.tree[node]
mid = (start + end) // 2
p1 = self._query(node * 2, start, mid, left, right)
p2 = self._query(node * 2 + 1, mid + 1, end, left, right)
return p1 + p2
def get_R_total(self):
return self.tree[1]
# =====================================================================
# 엄밀한 테스트 케이스 및 검증 시뮬레이션
# =====================================================================
def run_simulation():
print("--- ⚡ 765kV 계통 듀얼 레이지 시뮬레이터 테스트 ---")
# [1] 초기화
# 인덱스 0~4, 총 5개의 소자. 초기값 모두 10옴
# 초기 상태 배열: [10, 10, 10, 10, 10]
initial_data = [10, 10, 10, 10, 10]
segtree = DualLazySegmentTree(initial_data)
print(f"1. 초기 상태 [0~4]: 전체 저항 = {segtree.get_R_total()}Ω (예상: 50)")
# [2] 구간 덮어쓰기 (Set) 테스트
# 인덱스 1~3 구간을 0옴으로 단락(Short) 시킴
# 예상 배열: [10, 0, 0, 0, 10]
segtree.update_set(1, 3, 0)
print(f"2. [1~3] 구간 0옴 단락 후 전체 저항 = {segtree.get_R_total()}Ω (예상: 20)")
# [3] 구간 더하기 (Add) 테스트
# 인덱스 2~4 구간에 과열 발생, 각 소자당 +5옴씩 저항 증가
# 예상 배열: [10, 0, (0+5), (0+5), (10+5)] -> [10, 0, 5, 5, 15]
segtree.update_add(2, 4, 5)
# [4] 구간 쿼리 테스트
# 변경된 후 인덱스 1~3 (구간합) 확인
# 예상: 0 + 5 + 5 = 10옴
sum_1_to_3 = segtree.query(1, 3)
print(f"3. [1~3] 구간 합 쿼리 결과 = {sum_1_to_3}Ω (예상: 10)")
# 전체 저항 쿼리 확인
# 예상: 10 + 0 + 5 + 5 + 15 = 35옴
print(f"4. 모든 이벤트 종료 후 전체 저항 = {segtree.get_R_total()}Ω (예상: 35)")
if __name__ == "__main__":
run_simulation()와우 상당히 어렵네
이렇게 저는 컴퓨터공학과의 PS(Programming Solving)에서 나온 심화 알고리즘으로 전기전자공학과에서 송전선로에서 각 저항이 실시간으로 변할 때 아주 빠르게 부분 구간의 전압 강하를 구하는 프로그램을 만들었습니다.
update_set 함수는 특정 구간을 단락시킬 때, update_add는 특정 구간에서 일정 온도로 상승하여 저항의 온도 계수 공식에 의하여 저항값이 증가할 때 사용됩니다.
그 외 제가 아직 놓치는 부분이 있어 미숙한 점이 많으나 나중에 제가 컴공 PS 알고리즘에 대해 좀 더 공부하고 전기전자공학과에서 전력전자 및 전력계통에 대하여 좀 더 공부해서 나중에 프로그램 퀄리티를 올리고 싶습니다.
'나의 작은 연구 기록' 카테고리의 다른 글
| [장문 주의]Big 5의 30개 하위 척도 Z점수 기반으로 상위 요인의 Z점수 그리고 RMSD 구하는 Python 소스 코드를 만들어 봅니다. (1) | 2026.07.10 |
|---|---|
| 백준 지애 상수(22222번) 정답 소스 코드(Python) (0) | 2026.06.27 |
| 에라토스테네스의 체를 비트마스킹으로 최적화 해보자.(Python, C++) (0) | 2026.06.27 |
| 음... RLC 직렬 회로에 다이오드 하나 추가하면 어떻게 될까? (0) | 2026.05.16 |
| PS에서 공부했던 알고리즘이 전기전자 분야에서 이렇게도 활용할 수 있구나. (0) | 2026.05.15 |