가장 기본적인 LCA 문제이다. 노드의 수가 최대 10,000이며 쿼리의 수도 하나 뿐이기 때문에 효율적인 알고리즘을 생각할 필요 없이 간선 정보를 토대로 각 노드의 부모노드를 저장하고 쿼리로 주어진 두 노드로부터 부모노드를 탐색해나가며 각 노드의 모든 조상노드 리스트를 구하고, 두 리스트를 뒤에서부터 비교해나갔을 때 마지막으로 같았던 두 리스트의 값이 가장 가까운 공통 조상 노드가 된다. 이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
# 3584 가장 가까운 공통 조상
# 노드의 수가 적고 쿼리도 케이스당 하나 뿐이기 때문에
# 단순한 방식으로도 해결 가능
def sol3584():
# 케이스별 정답 리스트
answer = []
for t in range(int(input())):
# 노드의 수
n = int(input())
# 각 노드의 부모노드
parent = [0] * (n + 1)
# 부모노드와 자식노드를 입력받아 부모노드를 채운다
for _ in range(n - 1):
a, b = map(int, input().split())
parent[b] = a
# 가장 가까운 공통조상을 구할 두 노드
u, v = map(int, input().split())
# 두 노드의 조상 노드 리스트를 구한다.
up, vp = [], []
while u:
up.append(u)
u = parent[u]
while v:
vp.append(v)
v = parent[v]
# 두 노드의 조상 노드 리스트를 뒤집는다.
up, vp = up[::-1], vp[::-1]
# 루트 노드부터 시작하여 두 노드의 조상 노드가 서로 달라질 때 까지 탐색
# 두 노드의 조상 노드가 마지막으로 같았을 때의 조상 노드가 가장 가까운 공통 조상 노드가 된다.
res = 0
for i in range(min(len(up), len(vp))):
if up[i] == vp[i]:
res = up[i]
else:
break
# 정답 리스트에 결과 삽입
answer.append(res)
# 출력 형식에 맞춰 정답 리스트 반환
return '\n'.join(map(str, answer))
하지만 위의 방법은 당연하게도 노드의 수와 쿼리의 수가 많아지면 쿼리마다 사용할 수 없다.
이번엔 다른 방식으로 문제를 해결해보자. 절차는 다음과 같다.
① 먼저 트리를 탐색하여 모든 노드의 깊이와 부모노드를 구한다.
② 주어진 두 노드의 깊이가 다르다면 보다 깊이 있는 노드가 다른 노드와 같은 높이가 될 때 까지 거슬러 올라온다.
③ 두 노드가 서로 같아질 때 까지 두 노드 모두 부모노드를 타고 거슬러 올라온다.
④ 두 노드가 서로 같아졌을 때, 그 노드가 가장 가까운 조상 노드가 된다.
이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol3584():
# 정답 리스트
answer = []
# 테스트케이스
for t in range(int(input())):
# 노드의 수
n = int(input())
# 그래프 생성, 부모 노드 구하기
g = [[] for _ in range(n + 1)]
parent = [0] * (n + 1)
for _ in range(n-1):
a, b = map(int, input().split())
g[a].append(b)
parent[b] = a
# 루트 노드로부터 bfs탐색으로 각 노드의 깊이를 구한다
depth = [0] * (n + 1)
root = [i for i in range(1, n+1) if not parent[i]][0]
q = [root]
while q:
nq = []
for cur in q:
for c in g[cur]:
depth[c] = depth[cur] + 1
nq.append(c)
q = nq
# 주어진 두 노드 u, v
u, v = map(int, input().split())
# 노드 u의 깊이가 노드 v의 깊이보다 크도록 한다.
if depth[u] < depth[v]:
u, v = v, u
# 두 노드의 깊이차가 0이 될 때 까지 깊은 쪽 노드인 u를 끌어올린다
while depth[u] - depth[v]:
u = parent[u]
# 두 노드가 서로 같아질 때 까지 두 노드를 끌어올린다
while u != v:
u, v = parent[u], parent[v]
# u와 v가 서로 같아지면 u == v == 가장 가까운 공통 조상 노드 가 된다.
answer.append(u)
# 출력 형식에 맞춰 정답 리스트 반환
return '\n'.join(map(str, answer))
이 방식 자체로는 보다 많은 노드와 쿼리 수가 주어지는 문제를 해결하기에 딱히 이전의 알고리즘보다 효율적이지 않다. 하지만 이 방식에 sparse table을 적용하면 얘기가 달라진다. 다음 문제에서 이 sparse table에 대해 다룬다.
함수 f(x)의 값들이 주어졌을때, fn(x) 가 f(f(f(...f(x)...))) 와 같이 함수 f를 n중첩한 결과라고 한다. 이 때, 주어진 m개의
n, x 쌍에 대해 fn(x) 를 각각 구하는 문제이다. LCA 문제는 아니지만 LCA 알고리즘의 핵심인 sparse table을 응용해서
풀 수 있는 문제이다. 절차는 다음과 같다.
① 먼저 함수 f의 값을 저장할 2차원 배열을 생성한다. 이 때, f[x][k] 는 함수 f의 k중첩에 x를 넣은 결과이다. 예를들어,
f[3][4] = f(f(f(f(3)))) 이 된다.
② f[x][0] 의 값을 입력받은 f(x)의 값으로 초기화한다.
③ f[i][j] 은 f[i][j-1] 을 2^(j-1) 중첩한 값이 되기 때문에, 점화식 f[i][j] = f[f[i][j-1]][j-1] 이 성립한다. 이 점화식에 따라
나머지 f[x][1~k] 를 채운다. 여기서 k는 함수 중첩수 최댓값인 n에 로그를 취한 뒤 올림한 값이 된다.
=> math.ceil(math.log2(n))
④ 이제 쿼리로 n, x가 주어지면 ③ 에서 구한 sparse table을 이용하여 빠르게 목표한 값으로 접근한다.
n이 0보다 큰 동안, x = f[x][int(log2(n))]; n -= (1 << int(log2(n))) 을 수행하면 가능하다. n 중첩을
1씩 좁혀나가는 것이 아니라 2의 승수단위로 좁혀나가는 것으로 탐색시간을 극적으로 줄이는 방식이다.
⑤ ④의 작업이 모두 끝났을 때, x의 값이 해당 쿼리에 대한 정답이 된다.
import sys
from math import log2, ceil
input = sys.stdin.readline
def sol17435():
# 주어진 함수값의 수
m = int(input())
# 500000 <= 2^k
k = ceil(log2(500000))
# sparse table : f[x][k] = fk(x)
f = [[-1] * k for _ in range(m + 1)]
fn = list(map(int, input().split()))
for i in range(m):
f[i + 1][0] = fn[i]
# 점화식 f[i][j] = f[f[i][j-1]][j-1] 에 따라 sparse table 나머지 채우기
for j in range(1, k):
for i in range(1, m + 1):
f[i][j] = f[f[i][j - 1]][j - 1]
# 쿼리의 수
q = int(input())
# 각 쿼리의 정답 구하기
answer = []
for _ in range(q):
# 함수 중첩수 n, 인자값 x
n, x = map(int, input().split())
# 중첩수가 0이 되면 종료
while n:
# f[x][d] == f2^d(x)
d = int(log2(n))
x = f[x][d]
# 2^d 중첩만큼 처리했기 때문에 남은 중첩수에서 감산
n -= (1 << d)
# 정답리스트에 쿼리의 정답 저장
answer.append(x)
# 출력 형식에 맞춰 정답 리스트 반환
return '\n'.join(map(str, answer))
sparse table은 말그대로 어떤 규칙에 따른 값을 지수단위로 듬성듬성하게 구해두고 원하는 값까지 로그시간으로
빠르게 접근하기 위한 자료구조이다. 이 문제의 경우 sparse table 은 구성하는데에 O(MlogN)의 시간복잡도를,
쿼리 하나를 처리하는데 O(logN) 의 시간복잡도를 보인다.(경우에 따라서는 O(1) 수준의 성능을 보일때도 있다고 한다.)
sparse table은 정적인 데이터에서의 쿼리만을 처리할 수 있기 때문에 동적 데이터(데이터가 삽입, 삭제, 변경되는 경우)
에는 대응이 불가능하다. 만약 정적인 데이터에 대해 대량의 쿼리를 처리해야하는 경우라면 sparse table을 사용하는
이제 1번 문제에서 두 번째로 사용했던 알고리즘에 sparse table을 적용할 차례다. 노드의 수가 최대 100,000개로
늘어나고 쿼리의 수도 최대 100,000개이기 때문에 O(NM)의 시간복잡도를 보이는 기존의 방식으로는 해결할 수 없다.
두 노드의 깊이를 동일하게 맞추는 작업과 동일한 깊이에 있는 두 노드의 가장 가까운 조상 노드를 찾아가는 작업을
sparse table을 사용하여 O(logN) 수준으로 최적화한다. 이를 구현한 코드는 다음과 같다.
import sys
import math
input = sys.stdin.readline
# sparse table(희소 테이블)을 활용하여 문제를 더 효율적으로 해결할 수 있다. 절차는 다음과 같다.
# 1. 각 노드의 깊이를 나타낼 depth 리스트와 부모노드를 나타낼 parent 리스트를 생성한다
# 이 때, parent 리스트는 2차원 리스트이며 parent[i][k] 는 노드 i의 2^k 번 거슬러올라간 조상노드를 의미한다.
#
# 2. dfs 혹은 bfs 로 트리를 순회하며 각 노드의 1번 거슬러올라간 조상노드(parent[i][0])와 깊이를 구한다.
# 이 때, 점화식 parent[i][j] = parent[parent[i][j-1]][j-1] 를 사용해서 O(NK) 의 시간 복잡도로 작업을 수행한다.
# K는 log(2, N) 을 올림한 값과 같다.
#
# 3. 각 질의(LCA 를 구할 두 노드 u, v) 에 대해 두 노드의 깊이가 같아질 때 까지
# 보다 깊이가 큰 노드를 끌어올린다.
#
# 4. 두 노드가 서로 같다면 그대로 어느 한쪽 노드를 출력
#
# 5. 그렇지 않다면 두 노드의 가장 먼 공통 조상으로부터 처음으로 두 노드의 조상 노드가 달라질 때 까지 탐색
# 탐색 종료 후 노드 u 또는 v의 부모노드를 출력
def sol11438():
# 각 노드의 깊이와 첫 번째 부모를 구하기 위한 탐색 함수
def bfs(root):
q = [root]
while q:
nq = []
for cur in q:
for c in g[cur]:
if depth[c] < 0:
depth[c] = depth[cur] + 1
parent[c][0] = cur
nq.append(c)
q = nq
# 노드의 수
n = int(input())
# sparse table 의 크기
k = math.ceil(math.log2(n))
# 그래프 생성
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
# 각 노드의 깊이 리스트
depth = [-1] * (n + 1)
# 각 노드의 조상 노드 리스트 (sparse table)
parent = [[-1] * k for _ in range(n + 1)]
# 루트 노드인 1의 깊이를 0으로 하고 탐색 시작
depth[1] = 0
bfs(1)
# sparse table 채우기
for j in range(1, k):
for i in range(1, n + 1):
parent[i][j] = parent[parent[i][j - 1]][j - 1]
# 각 질의에 대해 정답 구하기
answer = []
for _ in range(int(input())):
u, v = map(int, input().split())
# 노드 u가 노드 v 보다 깊이가 크도록 한다
if depth[u] < depth[v]:
u, v = v, u
# 두 노드의 깊이가 같아질 때 까지 노드 u를 끌어올린다
while depth[u] - depth[v]:
u = parent[u][int(math.log2(depth[u] - depth[v]))]
# 두 노드가 같지 않다면
if u != v:
# 가장 먼 공통 조상 노드로부터 처음으로 두 노드의 조상 노드가 달라질 때 까지 탐색
for j in range(math.ceil(math.log2(depth[u])), -1, -1):
if parent[u][j] != parent[v][j]:
u = parent[u][j]
v = parent[v][j]
# 현재 u와 v는 공통 조상노드의 자식 노드인 상태이므로 둘 중 하나는 부모노드를 방문
u = parent[u][0]
# 노드 u 혹은 v를 반환
answer.append(u)
# 출력 형식에 맞춰 정답리스트 반환
return '\n'.join(map(str, answer))
진입 차수 테이블과 큐를 사용한 방법의 경우, 진입 차수가 0인 노드를 모드 큐에 넣으며 탐색해나가는
bfs(너비우선탐색)의 형태로 구현된다. 그리고 그 방식에서는 큐에서 뽑혀 탐색된 노드 순서가 곧 정렬 순서가 되었다. dfs를 활용한 방식에서는 정확히 그 반대라고 생각하면 편하다. 즉, 탐색이 가장 먼저 종료된 순서의 역순이 곧
정렬 순서가 된다. 이 방식으로 줄 세우기 문제를 해결한 코드는 다음과 같다.
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def sol2252():
# 학생 수 n, 키 비교 결과 수 m
n, m = map(int, input().split())
# 그래프, 진입 차수 테이블 생성
# bfs 형태의 구현과 달리 진입 차수 테이블은 생성이후 수정할 일이 없음
g = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for _ in range(m):
a, b = map(int, input().split())
g[a].append(b)
degree[b] += 1
# dfs를 활용한 위상 정렬 구현
def dfs(d):
nonlocal answer
# 현재 노드 방문처리
visit[d] = True
# 아직 방문하지 않은 자식노드 방문
for child in g[d]:
if not visit[child]:
dfs(child)
# 탐색이 종료된 노드를 answer에 삽입
answer.append(d)
# 방문여부 리스트
visit = [False] * (n + 1)
# 정렬 결과 리스트
answer = []
# 처음부터 진입 차수가 0인 노드로부터 탐색 시작
for i in range(1, n + 1):
if not degree[i]:
dfs(i)
# 정렬 결과 리스트를 뒤집어 출력 형식에 맞춰 반환
return ' '.join(map(str, answer[::-1]))
건설 규칙과 건물을 완성하는데 걸리는 시간이 주어졌을 때, 특정 건물을 건설하는데 걸리는 최소시간을 구하는 문제.
건물을 노드, 건설 규칙을 간선으로 생각하면 위상 정렬로 쉽게 해결할 수 있는 문제이다. 다만 각 노드(건물)까지
소요되는 최소 시간을 매번 다시 계산할 순 없기 때문에 간단한 동적계획법을 적용할 필요가 있다. 이를 해결한 코드는
다음과 같다.
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def sol1005():
# dfs(d) = dp[d] 는 d 번 건물을 건설하기 위해 필요한 최소 비용
def dfs(d):
# 아직 건물 d를 건설하기 위한 최소비용이 계산되지 않았다면 계산에 들어간다.
# 건물 d를 건설하기 위한 최소비용은 반드시 먼저 건설되어야할 건물의 최소 비용 중
# 가장 큰 비용에 건물 d를 건설하기 위해 필요한 비용을 합친 값이 된다.
if dp[d] == -1:
dp[d] = max([dfs(p) for p in g[d]], default=0) + cost[d]
# 건물 d를 건설하기 위한 최소 비용을 반환
return dp[d]
# 케이스별 정답 리스트
answer = []
for t in range(int(input())):
# 건물 수 n, 건설 규칙 수 k
n, k = map(int, input().split())
# 각 건물을 완성하는데 필요한 시간
cost = [0, *map(int, input().split())]
# 그래프를 생성
g = [[] for _ in range(n + 1)]
for _ in range(k):
x, y = map(int, input().split())
# 이 문제의 경우 정확하게 건물 w를 짓는데 드는 최소 비용만을 구하는 문제
# 노드 전체를 위상정렬하는 문제와 다르게 건물 w를 짓기 위해 지어야 하는
# 건물들의 최소 비용만을 탐색하는 것이 효율적이기 때문에
# 역탐색을 위해 그래프의 인접리스트에 갈 수 있는 노드가 아닌
# 현재 노드로 올 수 있는 노드를 저장한다.
g[y].append(x)
# dfs(w)를 구하여 정답 리스트에 저장
dp = [-1] * (n + 1)
w = int(input())
answer.append(dfs(w))
# 출력 형식에 맞춰 정답 리스트 반환
return '\n'.join(map(str, answer))
학생의 수(노드의 갯수)와 학생들의 키를 비교한 결과(간선)가 주어졌을 때 학생들을 키순서로 줄 세우는 문제
위상 정렬의 구현을 연습할 수 있는 문제이다. 구현의 절차는 다음과 같다.
① 우선 위상 정렬을 위해 필요한 것은 그래프와 진입 차수 테이블이다. 주어진 노드의 갯수와 간선을 이용하여
이 두 가지를 먼저 구해야한다. 노드 X의 진입 차수는 X로 직접 올 수 있는 길을 가진 노드의 갯수를 의미한다.
② 진입 차수가 0인 노드를 순서에 상관없이 모두 큐에 집어넣는다.
③ 큐에서 노드를 꺼내서 해당 노드로부터 뻗은 간선을 모두 제거하고 진입 차수 테이블을 갱신한다.
④ ②, ③ 작업을 큐가 빌 때 까지 반복한다.
⑤ 작업이 끝났을 때, 큐에서 노드를 꺼낸 순서가 곧 위상 정렬된 순서가 된다.
이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2252():
# 학생의 수 n, 비교 결과의 수 m
n, m = map(int, input().split())
# 학생을 노드로, 비교 결과를 간선으로 하여 그래프로 표현
# 각 노드(학생)의 진입 차수 테이블을 생성
g = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for _ in range(m):
a, b = map(int, input().split())
degree[b] += 1
g[a].append(b)
# 진입 차수가 0인 모든 노드를 큐에 삽입
q = [i for i in range(1, n + 1) if not degree[i]]
# 정렬 결과 리스트
answer = []
# 큐가 빌 때 까지
while q:
nq = []
# 큐에서 노드를 하나씩 꺼내 정렬 결과 리스트 answer 에 삽입
# 해당 노드로부터 뻗은 간선을 제거하고 진입 차수를 갱신
# 그 결과 진입 차수가 0이 된 노드를 모두 큐에 삽입
for num in q:
answer.append(num)
for child in g[num]:
degree[child] -= 1
if degree[child] == 0:
nq.append(child)
q = nq
# 출력 형식에 맞춰 정렬 결과를 반환
return ' '.join(map(str, answer))
③ 순위가 변경된 팀의 순서쌍에서 더 낮은 순위였던 쪽을 a, 더 높은 순위였던 쪽을 b로 하여 그래프와
진입 차수 테이블을 수정한다.
④ 그래프에 대해 위상 정렬을 수행한다.
⑤ 위상정렬의 수행한 결과 리스트의 길이가 총 노드의 갯수에 미치지 못할 경우 그래프에 사이클이 존재한다는
의미이기 때문에 데이터에 일관성이 없어 순위를 정할 수 없는 경우에 속하므로 IMPOSSIBLE을 출력한다
⑥ 그렇지 않다면 정상적으로 위상 정렬이 완료된 것이기 때문에 정렬 결과를 출력한다.
이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol3665():
# 케이스별 정렬 결과 리스트
answer = []
for t in range(int(input())):
# 팀의 수(노드의 수)
n = int(input())
# 작년 순위에 따라 그래프와 차수 테이블 생성
g = [set() for _ in range(n + 1)]
degree = [0] * (n + 1)
teams = list(map(int, input().split()))
for i in range(n):
a = teams[i]
for j in range(i + 1, n):
b = teams[j]
g[a].add(b)
degree[b] += 1
# 변경된 순위에 따라 그래프와 차수 테이블 수정
m = int(input())
for _ in range(m):
a, b = map(int, input().split())
# 보다 낮은 순위였던 쪽이 a가 되게 한다
if a not in g[b]:
a, b = b, a
g[b].discard(a)
g[a].add(b)
degree[a] -= 1
degree[b] += 1
# 정렬 결과
res = []
# 위상 정렬 수행
q = [i for i in range(1, n + 1) if not degree[i]]
while q:
nq = []
for num in q:
res.append(num)
for child in g[num]:
degree[child] -= 1
if not degree[child]:
nq.append(child)
q = nq
# 사이클이 발견된 경우 -> 일관성이 없어 정렬이 불가능한 경우
if len(res) != n:
answer.append('IMPOSSIBLE')
# 정렬이 정상적으로 수행된 경우
else:
answer.append(' '.join(map(str, res)))
# 출력 형식에 맞춰 정렬 결과 반환
return '\n'.join(answer)
2. 먼저 푸는 것이 좋은 문제가 있는 문제는 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다. (문제 번호가 낮을수록 난이도가 낮다)
순서를 지켜야한다는 점에서 알 수 있듯이 위상정렬을 사용하여 해결 가능한 문제이다. 다만 같은 단계에서
진입 차수가 0이라면 순서가 상관없었던 기존의 위상정렬로는 3번 조건을 만족시킬 수 없다. 여기서는
기존의 큐를 heapq 로 대체하는 것으로 문제를 해결할 수 있다. 구현은 다음과 같다.
import sys
from heapq import heappush, heappop, heapify
input = sys.stdin.readline
def sol1766():
# 문제의 갯수 n, 먼저 푸는게 좋은 문제의 정보의 갯수 m
n, m = map(int, input().split())
# 그래프, 진입 차수 테이블 생성
g = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for _ in range(m):
a, b = map(int, input().split())
g[a].append(b)
degree[b] += 1
# 최초에 진입 차수가 0인 노드(문제)를 큐에 담는다
q = [i for i in range(1, n + 1) if not degree[i]]
# 큐를 heapq로 변환
# Python의 heapq는 기본적으로 최소 힙이기 때문에
# 더 작은 숫자, 즉 더 쉬운 문제부터 뽑게된다.
heapify(q)
# 정렬 결과 리스트
answer = []
# 위상 정렬 실행
# 기존의 방식과 같지만 큐에서 값을 꺼내고 다시 넣는 동작을
# heappop 과 heappush를 사용하여 수행한다.
# 이것으로 매번 가능하면 가장 쉬운 문제를 해결하는 3번 조건을 만족시킨다.
while q:
cur = heappop(q)
answer.append(cur)
for c in g[cur]:
degree[c] -= 1
if not degree[c]:
heappush(q, c)
# 출력 조건에 따라 정답 리스트 반환
return ' '.join(map(str, answer))
heap을 사용하면 항상 정렬된 것과 마찬가지인 상태를 유지할 수 있다는 점만 떠올리면 쉽게 해결할 수 있는 문제였다.
위상정렬의 구현은 다음에 알아볼 dfs를 사용한 구현이 보다 간단하지만 큐를 사용한 구현이 풀이에 적합한 경우도 있기 때문에 두 방법 모두 숙지해둘 필요가 있다.
누적 합은 2차원 배열에서도 1차원에서와 거의 동일하게 활용 가능하다. 이번에는 2차원 배열에서의
누적 합의 성질과 이를 활용하여 풀 수 있는 문제들을 알아본다.
1. 2차원 배열의 누적합 구하기
1차원 배열에서는 단순히 이전 인덱스의 값을 더해주면 끝이었지만 2차원 배열에서 누적합을 구하려면 각 행의
누적 합과 각 열의 누적 합을 구하는 두 단계를 거쳐야한다. 예시로 2차원 배열 하나의 누적 합을 구해보자.
① 먼저 각 행의 누적합을 구한다.
② 다음으로 각 열에 대한 누적 합을 구한다.
③ 2차원 행렬에서의 누적합 배열이 완성된다. ①과 ②의 순선느 서로 뒤바뀌더라도 문제가 없다.
2. 2차원 누적 합의 성질
2차원 배열에서의 부분 합을 구하거나 여러 구간에 대한 증감 적용을 한꺼번에 처리하는 데
활용할 수 있는 성질들을 가지고있다.
누적합 S(r, c)는 2차원 배열 A에 대해 다음과 같은 성질을 가진다.
① S(r, c) = sum([A[i][j] for i in range(r) for j in range(c)])
② S(0, 0) = A[0][0]
③ S(r, c) = S(r-1, c) + A[r][c]
④ sum([A[i][j] for i in range(r1, r2+1) for j in range(c1, c2+1)]) = S(r2, c2) + S(r1-1, c1-1) - S(r1, c2-1) - S(c1-1, r2)
② 번 성질이 성립하는 이유
1차원 배열에서의 누적 합과 조금 다르지만 거의 유사한 성질을 가진 것을 알 수 있다.
3. 2차원 배열의 합
N*M 크기의 2차원 배열이 주어졌을때 K 개의 특정 구간에 대한 부분 합을 구하는 문제. 단순히 매번 반복문을 돌려 합을 구할 경우 O(NMK)의 시간복잡도를 보인다. 하지만 누적합의 4번 성질을 이용하면 O(NM+K)만에 해결할 수 있다.
문제를 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2167():
# 행렬의 크기 n, m
n, m = map(int, input().split())
# 주어진 행렬 seq
# 누적 합의 성질 4번을 사용할 때, 0번 인덱스의 이전 인덱스를 참조할 경우를 대비해
# 행/열의 끝에 0을 추가
seq = [[*map(int, input().split()), 0] for _ in range(n)]
seq.append([0] * m)
seq.append([0] * m)
# 2차원 배열의 누적합 배열을 구한다
for i in range(n):
for j in range(m):
# 현재 위치의 누적합을 구하기 전에 같은 열의 다음 행의 값에
# 현재위치의 값을 더해주는 것으로 열에 대한 누적합을 동시에 계산해나갈 수 있다.
seq[i + 1][j] += seq[i][j]
seq[i][j] += seq[i][j - 1]
# 정답 리스트
answer = []
# 누적 합의 성질 4번을 사용하여 부분 합을 구하고 정답 리스트에 저장
for _ in range(int(input())):
i, j, x, y = map(int, input().split())
answer.append(seq[x-1][y-1] + seq[i - 2][j - 2] - seq[x-1][j - 2] - seq[i - 2][y-1])
# 출력 형식에 맞춰 정답 리스트 반환
return '\n'.join(map(str, answer))
import sys
input = sys.stdin.readline
def sol11659():
# 수열의 크기 n, 질의의 갯수 m
n, m = map(int, input().split())
# n개의 수로 이루어진 수열
seq = [0, *map(int, input().split())]
# 수열의 누적합 전처리
for i in range(1, n + 1):
seq[i] += seq[i - 1]
# 각 질의에 대해 정답을 계산하여 answer 에 삽입
answer = []
for _ in range(m):
i, j = map(int, input().split())
answer.append(seq[j] - seq[i - 1])
# 출력형식에 맞춰 정답리스트 반환환
return '\n'.join(map(str, answer))
a(i) + a(i+1) + ... + a(j-1) + a(j) = S(j) - S(i-1) 임을 이용하여 문제를 해결하였다.
영상 전체의 길이와 시청자들이 어느 구간을 재생했는지의 로그들이 주어질 때, 광고를 삽입할 최적의 위치를 찾기위해 가장 재생횟수가 많은 구간의 시작시간을 구하는 문제이다. 만약 재생횟수가 가장 많은 구간이 여러개라면 그 중 가장 빠른 시작시간을 반환한다. 위의 문제보다는 복잡하지만 역시 누적 합을 활용하여 해결할 수 있는 문제이다.
주어지는 데이터는 동영상 전체의 재생시간 play_time 과 광고의 재생시간 adv_time, 영상의 재생구간 로그들이 담긴 리스트 logs이다. 문제를 해결하는 과정은 다음과 같다.
① 먼저, 제한사항에 광고의 재생시간은 동영상의 재생시간보다 짧거나 같게 주어진다는 조건이 있다.
같을 경우에는 애초에 탐색할 필요가없다. 영상의 시작시간이 곧 광고의 시작시간이 될 수 밖에 없기 때문이다.
② play_time 과 adv_time은 'HH:MM:SS' 의 문자열 형태이기 때문에 다루기 쉽도록 정수형태로 파싱해줄 필요가 있다.
가장 작은 초단위로 시간을 변환한다. HH * 3600 + MM * 60 + SS 로 간단하게 변환 가능하다.
③ 다음은 광고가 삽입될 최적의 위치를 찾기위해 로그를 분석해야한다. 가장 먼저 떠오르는 방식은 1초에 한칸씩
0으로 초기화된 배열을 할당하여 재생된 부분마다 1씩 더해주는 것으로 가장 재생수가 많은 구간을 탐색하는
것이다. 다행히도 play_time의 범위가 00:00:00 부터 99:59:59, 즉, 0초부터 359999초 까지라는 조건이 있기 때문에
배열의 형태로 충분히 나타낼 수 있다.
④ 예를 들어 로그가 '00:00:00-00:00:04', '00:00:02-00:00:07', '00:00:06-00:00:10' 의 세 개라고 생각해보자.
문제의 제한사항에 "예를 들어, 00시 00분 01초부터 00시 00분 10초까지 동영상이 재생되었다면, 동영상
재생시간은 9초 입니다." 라는 조건이 있다. 즉, 종료시간은 재생구간에 들어가지 않는다는 것이다.
이에 따라 위 로그를 배열상에 표현하면 아래와 같은 형태가 된다.
문제는 여기서 발생한다. 로그 한번마다 구간내의 값을 모두 1 씩 증가시키려면 재생시간의 길이가 N, 로그의 갯수가
M일 때 최악의 경우(모든 로그의 범위가 영상의 재생시간과 같을 경우) O(NM) 의 시간복잡도를 보인다.
이 문제에서 N은 최대 360000, M은 최대 30만의 크기를 가지기에 이 알고리즘은 매우 비효율적이다.
⑤ 여기서 우리는 누적 합의 성질 중 하나인 S(k) = S(k-1) + a(k) 를 활용할 수 있다. 이번엔 로그의 시작 시간과
종료 시간에만 시청횟수의 증감을 더해보자. 그러면 다음과 같은 형태가 된다.
각 로그의 시작 시간인 0, 2, 6초에는 +1을, 종료 시간인 4, 7, 10초에는 -1을 더하였다. 이제 위 테이블에서
누적합의 성질에 따라 누적합을 구해보자. 그러면 다음과 같은 형태가 된다.
한눈에 봐도 ④ 에서 구했던 로그마다 전 구간의 값을 1씩 증가시키는것으로 얻었던 배열과 같음을 알 수 있다.
게다가 이 방식은 O(N+M)의 시간복잡도로 위의 O(NM)의 알고리즘과 같은 결과를 얻을 수 있다. 이와 같이
누적 합을 활용하면 어떤 배열에 여러 구간에 대한 증/감을 반영하는 작업을 굉장히 효율적으로 처리할 수 있다.
⑥ 여기까지 구하고나면 다음은 어렵지 않다. 위에서 구한 배열에서 영상의 시작시간부터 시작하여 광고 시간만큼의
구간의 합이 최대치가 되는 구간의 시작시간을 구하면 된다. 최댓값이 여러개라면 가장 빠른 시간을 구하라는 조건도
처음 찾은 최댓값이 더 큰 값이 오기 전에는 갱신되지 않도록 하면 자동으로 충족된다. 여기서 구간합이 최대가 되는
경우를 찾는 것도 두 가지 방법이 있다.
⑦ 하나는 마찬가지로 누적 합을 이용한 방법이다. a(i) + a(i+1) + ... + a(j-1) + a(j) = S(j) - S(i-1) 임을 이용하여,
위 배열의 누적합을 다시한번 구한 뒤 구간마다 구간합을 빠르게 구할 수 있다.
⑧ 다른 하나는 투 포인터를 활용하는 방법이다. 첫 번째 구간의 합만을 구한 뒤, 다음 구간으로 넘어갈때마다
첫 번째 요소를 빼고 새로운 요소를 더하는 식으로 구간합을 갱신해나갈 수 있다.
⑨ 마지막으로 구한 시작시간을 다시 'HH:MM:SS' 의 형태의 문자열로 변환하여 반환하면 된다.
위 절차에 따라 문제를 해결한 코드는 다음과 같다.
1) 누적 합의 성질을 활용하여 최대 구간합을 구한 방식 (⑦)
def solution(play_time, adv_time, logs):
# ① 광고의 재생시간이 영상의 재생시간과 같다면 영상의 첫 부분에 삽입하면 된다.
if play_time == adv_time:
return '00:00:00'
# ② 영상 재생시간과 광고 재생시간을 초단위의 정수로 변환
pt, at = stoh(play_time), stoh(adv_time)
# ③ 시간별 재생횟수를 나타내기위한 타임라인 배열을 생성
timeline = [0] * 360001
# ④, ⑤ 로그를 분석하여 재생 시작시간과 종료시간을 구한 뒤
# 누적 합을 활용하여 타임라인에 재생 횟수를 표기
for log in logs:
s, e = map(stoh, log.split('-'))
timeline[s] += 1
timeline[e] -= 1
for i in range(1, 360001):
timeline[i] += timeline[i - 1]
# ⑦, ⑧ 영상의 시작시간부터 timeline의 at(광고 재생시간)크기의 구간합이 최대가 되는 경우를 탐색
# 다시 한번 누적 합을 구하는 전처리작업을 수행하여 구간 합을 더 쉽게 구할 수 있도록 한다.
for i in range(1, 360001):
timeline[i] += timeline[i - 1]
# 최대 구간 합 maxw, 정답으로 반환할 시작시간 answer
maxw, answer = timeline[at-1], 0
# 영상의 시작시간부터 탐색 시작
for s in range(1, pt - at+1):
# 누적 합의 성질을 활용하여 구간 합을 구한다
w = timeline[s+at-1] - timeline[s-1]
# 만약 새로운 구간합이 최대 구간합 maxw보다 크다면 maxw와 answer 갱신
if w > maxw:
maxw, answer = w, s
# 광고를 삽입할 최적의 시작시간을 문자열로 변환하여 반환
answer = htos(answer)
return answer
# 문자열 형태의 시간을 초단위의 정수로 변환
def stoh(times):
h, m, s = map(int, times.split(':'))
return h * 3600 + m * 60 + s
# 초단위의 정수를 문자열 형태의 시간으로 변환
def htos(sec):
h = sec // 3600
sec %= 3600
m = sec // 60
s = sec % 60
return '%02d:%02d:%02d' % (h, m, s)
2) 투 포인터를 활용하여 최대 구간합을 구한 방식 (⑧)
def solution(play_time, adv_time, logs):
# ① 광고의 재생시간이 영상의 재생시간과 같다면 영상의 첫 부분에 삽입하면 된다.
if play_time == adv_time:
return '00:00:00'
# ② 영상 재생시간과 광고 재생시간을 초단위의 정수로 변환
pt, at = stoh(play_time), stoh(adv_time)
# ③ 시간별 재생횟수를 나타내기위한 타임라인 배열을 생성
timeline = [0] * 360001
# ④, ⑤ 로그를 분석하여 재생 시작시간과 종료시간을 구한 뒤
# 누적 합을 활용하여 타임라인에 재생 횟수를 표기
for log in logs:
s, e = map(stoh, log.split('-'))
timeline[s] += 1
timeline[e] -= 1
for i in range(1, 360001):
timeline[i] += timeline[i - 1]
# ⑦, ⑧ 영상의 시작시간부터 timeline의 at(광고 재생시간)크기의 구간합이 최대가 되는 경우를 탐색
# 최대구간합 maxw, 정답으로 반환할 시작시간 answer
maxw, answer = sum(timeline[:at]), 0
# 초기 구간합 w = maxw
w = maxw
# 영상의 시작시간부터 탐색 시작
for s in range(1, pt - at+1):
# 투 포인터를 활용하여 구간합을 갱신해나가는 방식을 사용
w = w - timeline[s-1] + timeline[s+at-1]
# 만약 새로운 구간합이 최대 구간합 maxw보다 크다면 maxw와 answer 갱신
if w > maxw:
maxw, answer = w, s
# 광고를 삽입할 최적의 시작시간을 문자열로 변환하여 반환
answer = htos(answer)
return answer
# 문자열 형태의 시간을 초단위의 정수로 변환
def stoh(times):
h, m, s = map(int, times.split(':'))
return h * 3600 + m * 60 + s
# 초단위의 정수를 문자열 형태의 시간으로 변환
def htos(sec):
h = sec // 3600
sec %= 3600
m = sec // 60
s = sec % 60
return '%02d:%02d:%02d' % (h, m, s)
구간 합을 활용하여 효율적으로 문제를 해결해야하는 경우는 코딩테스트에서 꽤 자주 보인다. 잘 기억해두자.
