지난 게시글에서 다룬 선분 교차 2(https://www.acmicpc.net/problem/17387) 문제에 교차 여부만이 아닌 교점의 좌표까지 구해야하는 응용문제. 교차하는 경우 중에서도 교점이 한 개인 케이스와 여러 개인 케이스를 구분하고 교점이 한 개인 경우에도 교점의 좌표를 구하기 위해 따져야할 조건이 제법 많아 주의할 필요가 있는 문제이다. 이 문제를 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.read
INF = float('inf')
def sol20149():
# 두 선분을 이루는 네 점의 좌표
x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
p1, p2, p3, p4 = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
# CCW 값의 곱
v1, v2 = ccw(p1, p2, p3) * ccw(p1, p2, p4), ccw(p3, p4, p1) * ccw(p3, p4, p2)
# 두 선분의 기울기
try:
a1 = (y2 - y1) / (x2 - x1)
except:
a1 = INF
try:
a2 = (y4 - y3) / (x4 - x3)
except:
a2 = INF
# v1, v2 둘 중 하나라도 0 보다 크다면 두 선분은 교차하지 않음
if v1 > 0 or v2 > 0:
return 0
# 셋 이상의 점이 일직선상에 존재하는 경우
elif v1 == v2 == 0:
# p1 <= p2 , p3 <= p4 가 되도록 한다
if p1 > p2:
p1, p2 = p2, p1
if p3 > p4:
p3, p4 = p4, p3
# 선분 l2의 점 중 선분 l1에 가장 가까운 점이 l1과 떨어져있는 경우
# 두 선분은 교차하지 않음
if p2 < p3 or p4 < p1:
return 0
# 그 외의 경우
else:
# 두 선분의 기울기가 같고 선분의 끝부분에서 만나는 경우
if a1 == a2:
if p2 == p3:
return '\n'.join(['1', ' '.join(map(str, p2))])
if p1 == p4:
return '\n'.join(['1', ' '.join(map(str, p1))])
return 1
# 두 선분의 기울기가 다르고 선분의 끝부분에서 만나는 경우
# 또는 한 선분의 길이가 0인 경우(시작과 끝점이 같은 경우)
else:
p = p1 if p1 == p2 or p1 == p3 or p1 == p4 else p2 if p2 == p3 or p2 == p4 else p3 if p3 == p4 else p4
return '\n'.join(['1', ' '.join(map(str, p))])
# 반드시 한 점에서 교차하는 경우
else:
# 두 선분의 기울기가 무한이 아닐 경우 일차방정식 그래프의 교점을 찾는 방식으로
# 교점을 구한다.
if a1 != INF and a2 != INF:
k1 = -a1 * x1 + y1
k2 = -a2 * x3 + y3
resx = (k2 - k1) / (a1 - a2)
if int(resx) == resx:
resx = int(resx)
resy = a1 * resx + k1
if int(resy) == resy:
resy = int(resy)
return '\n'.join(['1', f'{resx} {resy}'])
# 두 선분중 어느 하나의 기울기가 무한인 경우 교점 탐색
else:
if a1 == INF:
resx = x1
resy = a2 * resx - a2 * x3+ y3
else:
resx = x3
resy = a1 * resx - a1 * x1 + y1
if int(resx) == resx:
resx = int(resx)
if int(resy) == resy:
resy = int(resy)
return '\n'.join(['1', f'{resx} {resy}'])
# CCW 함수
def ccw(a, b, c):
res = (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (b[0] * a[1] + c[0] * b[1] + a[0] * c[1])
return 1 if res > 0 else -1 if res < 0 else 0
시작점의 좌표와 끝 점의 좌표로 이루어진 선분의 정보가 N개 주어지고, 서로 교차하는 선분은 하나의 그룹이 된다고 할 때, 선분의 그룹의 갯수와 가장 큰 그룹의 크기를 구하는 문제. 선분 교차 여부의 검증은 ccw 알고리즘을 활용하여 해결 가능하며 선분의 그룹을 관리하는 것은 Disjoint Set 알고리즘(union-find 알고리즘)으로 해결 가능하다. 다만,
Python 의 경우 시간제한이 상당히 아슬아슬하기 때문에 상당한 최적화를 거치지 않으면 시간초과가 발생한다. 이를 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2162():
# 선분의 갯수
n = int(input())
# 선분의 그룹을 관리하기 위한 union 리스트
u = [-1] * n
# 선분들의 정보
lines = [[*map(int, input().split())] for i in range(n)]
# 선분 그룹의 갯수 - 선분의 갯수로 초기화
cnt = n
# 선분 리스트에서 두 선분을 뽑는 모든 경우의 수를 따져
# 두 선분의 교차여부를 검증
# 두 선분이 교차한다면 union 연산을 통해 그룹짓는다
for i in range(n):
for j in range(i+1, n):
if cross_check(lines[i], lines[j]):
# union의 결과를 선분 그룹의 갯수에 반영
cnt += union(u, i, j)
# 선분 그룹의 갯수와 가장 큰 그룹의 크기 반환
return str(cnt) + '\n' + str(-min(u))
# 선분의 교차 검증 함수
def cross_check(l1, l2):
x1, y1, x2, y2 = l1
x3, y3, x4, y4 = l2
v1, v2 = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4), ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2)
return v1 <= 0 and v2 <= 0 and min(x1, x2)<=max(x3, x4) and min(x3, x4)<=max(x1, x2) and min(y1, y2)<=max(y3, y4) and min(y3, y4)<=max(y1, y2)
# CCW 함수
def ccw(x1, y1, x2, y2, x3, y3):
res = (x2-x1) * (y3-y1) - (y2-y1) * (x3-x1)
return 1 if res > 0 else -1 if res < 0 else 0
# union 연산
def union(u, a, b):
a = find(u, a)
b = find(u, b)
if a != b:
if u[a] < u[b]:
u[a] += u[b]
u[b] = a
else:
u[b] += u[a]
u[a] = b
return -1
return 0
# find 연산
def find(u, x):
if u[x] < 0:
return x
u[x] = find(u, u[x])
return u[x]
CCW 함수와 선분의 교차검증 함수가 기존의 코드보다 간략하게 바뀐 것을 확인할 수 있다.
CCW는 2차원 좌표 세 개를 주어진 대로 이었을 때 선분의 방향(시계, 반시계, 일직선)을 벡터의 외적 공식을 사용하여 구하는 알고리즘이다. 삼각형의 세 좌표가 주어질 때 넓이를 쉽게 구하기 위해 배웠던 신발끈 공식이 이것을 말한다. 이번에는 CCW를 활용하여 풀 수 있는 문제들에 대해 알아본다.
2차원 평면상에 다각형을 이루는 순서대로 N개의 좌표가 주어졌을 때 다각형의 넓이를 구하는 문제. CCW 알고리즘을 사용하면 간단하게 구할 수 있다.
예를들어 주어진 좌표가 (x1, y1), (x2, y2), (x3, y3), (x4, y4) 라고 할 때, 좌표를 아래와같이 나열한다.
그 다음 붉은색 선으로 이어진 수 끼리 곱한 값을 더한 값에서 파란색 선으로 이어진 수 끼리 곱한 값을 더한 값을 빼준 뒤 절댓값을 취하고 2로 나누면 위 좌표들로 구성된 다각형의 넓이가 된다. 이 공식을 사용하여 문제를 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2166():
n = int(input())
# 외적공식을 사용하기 위해 다각형을 이루는 좌표리스트 뒤에 첫 좌표를 덧붙여준다
pos = [list(map(int, input().split())) for _ in range(n)]
pos.append(pos[0])
# 공식에 따라 값을 더한다
res = 0
for i in range(n):
res += (pos[i][0] * pos[i+1][1] - pos[i+1][0] * pos[i][1])
# 값에 절댓값을 취한 뒤 2로 나누어 소수 첫째자리까지 반환
return '%.1f' % (abs(res)/2)
2차원 평면상에 좌표 세개가 주어졌을 때, 좌표를 순서대로 이은 선분의 방향성이 반시계인지, 시계인지, 세 점이 일직선인지 구하는 문제. 조건문을 세세하게 나누어 모든경우를 따지면 공식을 몰라도 해결은 가능하지만 빼먹는 경우의 수가 생기기 쉽고 헷갈리는 탓에 생각보다 구현에 많은 시간이 걸렸다. 이 문제 또한 CCW 알고리즘으로 쉽게 해결할 수 있다.
import sys
input = sys.stdin.read
def sol11758():
# 세 점의 좌표
ax, ay, bx, by, cx, cy = map(int, input().split())
# CCW 알고리즘 적용
res = (ax*by + bx*cy + cx*ay) - (bx*ay + cx*by + ax*cy)
# 결과값이 0이라면 일직선, 0보다 크다면 반시계방향, 작다면 시계방향
return 0 if res == 0 else (1 if res > 0 else -1)
두 선분의 시작점과 끝점이 각각 주어졌을 때(이 때, 세 점이 일직선상에 놓여있는 경우는 없다.), 두 선분이 교차하는지 여부를 구하는 문제. 이 문제 또한 CCW 알고리즘으로 쉽게 해결할 수 있다.
CCW(X, Y, Z) 는 X Y Z를 잇는 선분이 반시계방향이라면 1, 시계방향이라면 -1, 세 점이 일직선상에 있다면 0이라 하자.
위 그림의 교차하는 선분 AB 와 CD를 보자. 선분 AB를 기준으로 CCW(A, B, C) 와 CCW(A, B, D)는 각각 시계방향, 반시계방향으로 반대의 방향성을 가진다. 선분 CD를 기준으로 CCW(C, D, A) 와 CCW(C, D, B) 를 봐도 마찬가지로 각각 반시계방향, 시계방향으로 반대의 방향성을 가진다.
이번엔 교차하지 않는 선분 AB와 CD를 보자. 선분 AB를 기준으로 CCW(A, B, C) 와 CCW(A, B, D)는 각각 시계방향, 반시계방향으로 반대의 방향성을 가지지만 선분 CD를 기준으로 CCW(C, D, A) 와 CCW(C, D, B) 를 보면 둘 다 반시계 방향으로 같은 방향성을 가진다.
서로 교차하지 않는 선분의 경우, 어느 한 선분 위의 모든 점은 반드시 다른 선분을 기준으로 한쪽방향에만 존재하게 된다. 그렇기 때문에 선분 AB 와 CD에 대해 CCW(A, B, C) * CCW(A, B, D) 와 CCW(C, D, A) * CCW(C, D, B) 중 어느 하나라도 1이라면 선분 AB 와 CD는 서로 교차하지 않는다고 할 수 있다. 그 외의 경우에는 선분 AB와 CD는 교차한다.(이 문제의 경우 세 점이 일직선상에 존재하는 경우가 없기 때문에 CCW는 반드시 1 또는 -1이므로 CCW가 0인 경우는 따질 필요가 없다) 이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.read
def sol17387():
# 네 점의 좌표
x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
p1, p2, p3, p4 = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
# 선분 p1-p2 와 p3-p4를 각각 기준으로 한 CCW값의 곱
v1, v2 = ccw(p1, p2, p3) * ccw(p1, p2, p4), ccw(p3, p4, p1) * ccw(p3, p4, p2)
# 두 값중 하나라도 0보다 크다면 두 선분은 교차하지 않는다.
if v1 > 0 or v2 > 0:
return 0
# 그 외의 경우 두 선분은 교차한다.
return 1
# CCW 함수
def ccw(p1, p2, p3):
res = (p1[0]*p2[1] + p2[0]*p3[1] + p3[0]*p1[1]) - (p2[0]*p1[1] + p3[0]*p2[1] + p1[0]*p3[1])
return 1 if res > 0 else (-1 if res < 0 else 0)
선분 교차 1 문제와 조건 한가지를 제외하고는 완전히 동일하다. 이 문제에는 세 개 이상의 점이 일직선상에 놓이지 않는다는 조건이 없다. 즉, CCW 값이 0이 나올 경우를 상정해야 한다. 편의상 선분 교차 1 과 같이 CCW(A, B, C) * CCW(A, B, D) 와 CCW(C, D, A), CCW(C, D, B) 를 각각 v1, v2 라고 하자.
* 먼저, v1이나 v2 중 어느 하나가 0보다 클 경우 두 선분이 교차하지 않는다는 사실은 변하지 않는다.
if v1 > 0 or v2 > 0:
return 0
* 그 다음으로 살펴봐야할 것은 세개 이상의 점이 일직선상에 놓이는 경우, 즉 v1또는 v2중 어느 하나라도 0이 되는 경우이다. (v1 == 0 or v2 == 0)
① 네 개의 점이 일직선상에 놓이는 경우 (V1 == V2 == 0)
A <= B < C <= DA <= B == C <= DA <= C <= B <= D
C <= A <= B <= D
② 세 개의 점이 일직선상에 놓이는 경우
v1 == 0, v2 == -1
v1 == 0, v2 == 1v1 == v2 == 0
① 케이스들의 경우, 결국 두 선분이 일직선상에 있지만 떨어져있는 경우(A <= B < C <= D 또는 C <= D < A <= B)를 제외하면 교차하는 경우라고 볼 수 있다. ② 의 세 번째 케이스는 네 점이 일직선상에 존재하지 않는데도 v1 == v2 == 0이 되는 특이한 케이스이다.
elif v1 == v2 == 0:
return 0 if B < C or D < A else 1
② 의 첫 번째 케이스의 경우 v1이나 v2중 어느 것도 0보다 크지 않으며 v1과 v2가 모두 0이 아닌 경우, 즉 지금까지의 경우들을 배제하고 남은 기타 케이스에 포함된다. 이 경우 두 선분은 교차한다.
else:
return 1
이에 따라 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.read
def sol17387():
# 선분을 이루는 네 점
x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
p1, p2, p3, p4 = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
# 각 선분을 기준으로 한 CCW 값의 곱
v1, v2 = ccw(p1, p2, p3) * ccw(p1, p2, p4), ccw(p3, p4, p1) * ccw(p3, p4, p2)
# v1, v2 중 하나라도 0보다 클 경우 선분은 교차하지 않음
if v1 > 0 or v2 > 0:
return 0
# 셋 이상의 점이 일직선상에 있는 경우
elif v1 == v2 == 0:
# p1 <= p2 , p3 <= p4 가 되도록 함
if p1 > p2:
p1, p2 = p2, p1
if p3 > p4:
p3, p4 = p4, p3
# 세 점이 일직선상에 있지만 선분 l2의 점 중 l1에 가장 가까운 점이 l1과 떨어져있어 교차하지 않는 경우를 제외하면
# 두 선분은 교차한다.
return 0 if p2 < p3 or p4 < p1 else 1
# 그 외의 경우 두 선분은 교차함
else:
return 1
# CCW 함수
def ccw(p1, p2, p3):
res = (p1[0]*p2[1] + p2[0]*p3[1] + p3[0]*p1[1]) - (p2[0]*p1[1] + p3[0]*p2[1] + p1[0]*p3[1])
return 1 if res > 0 else (-1 if res < 0 else 0)
이러한 잘 알려진 수학공식을 활용하는 문제들은 공식을 알고있다면 한없이 쉽지만 모른다면 아예 손도 대지 못하거나 풀더라도 많은 시간을 소비할 가능성이 높기 때문에 잘 기억해둘 필요가 있다.
트리의 노드가 N개이며 루트가 R번일 때, 주어진 N-1 개의 간선으로 트리를 구성하고 이어서 주어지는 Q 개의 임의의 노드에 대해 각 노드를 루트로 하는 서브트리에 속한 노드의 갯수를 구하는 문제이다.
트리를 구성하는 방법은 인접리스트로 양방향 그래프를 구성하는 것과 같다. 그래프와 달리 인접 노드중 부모노드만 방문 대상에서 제외하면 이미 방문한 노드를 다시 방문할 일은 없기 때문에 별도의 방문처리는 필요하지 않다. 트리를 탐색할 dfs(<노드번호>) 함수가 그 결과로 인자로 받은 노드를 루트로 하는 서브트리의 크기(포함하는 노드의 갯수)를 반환하도록 하면 쿼리로 주어진 각 노드번호 q 에 대해 dfs(q) 가 해답이 된다. 물론 쿼리마다 탐색을 진행하면 비효율적이기 때문에 동적계획법을 적용하여 이미 구한 서브트리의 크기는 메모리에 저장해두고 재사용한다. 이를 구현한 코드는 다음과 같다.
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def sol15681():
n, r, q = map(int, input().split())
# 트리 구성
g = [[] for _ in range(n+1)]
for _ in range(n-1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# 서브트리의 크기
sub = [0] * (n+1)
# 탐색 함수
def dfs(node):
# 자기 자신을 포함하기 때문에 시작 크기는 1
sub[node] = 1
# 자식 노드를 루트로 하는 서브트리의 크기를 모두 더한다
for c in g[node]:
if not sub[c]:
sub[node] += dfs(c)
# 자신이 루트 노드인 서브트리의 크기 반환
return sub[node]
# 루트 노드로부터 탐색 시작
dfs(r)
# 각 쿼리에 대한 해답을 반환
return '\n'.join([str(sub[int(input())]) for _ in range(q)])
쿼리가 들어올 때 마다 dfs를 실행할 수도 있지만 편의상 루트 노드에 대해 dfs를 호출하는것으로 전처리를 마친 뒤 답을 반환하였다.
노드가 N개인 트리와 각 노드의 가중치가 주어졌을 때, 트리의 최대 독립 집합의 크기와 최대 독립 집합을 구하는 문제.
그래프의 독립 집합이란 그래프의 정점의 부분집합 중 집합 안의 모든 정점이 서로 직접 인접해있지 않은 것을 의미한다.
최대 독립 집합을 구하는 문제는 그래프에서는 효율적인 알고리즘을 찾지 못한 NP-하드 문제이지만 트리의 경우 서브트리로 문제를 분할하여 효율적으로 해결할 수 있다. 이 문제를 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2213():
# 노드의 갯수
n = int(input())
# 노드의 가중치
w = [0] + list(map(int, input().split()))
# 트리 구성
g = [[] for _ in range(n + 1)]
for i in sys.stdin:
u, v = map(int, i.split())
g[u].append(v)
g[v].append(u)
# 각 노드를 루트로 하는 서브트리의 경우별 최대 독립 집합 크기
# mis[<노드번호>][0] 은 해당 노드가 포함되지 않았을 경우를,
# mis[<노드번호>][1] 은 해당 노드가 포함된 경우의 최대 독립집합의 크기를 의미한다
mis = [[-1, -1] for _ in range(n + 1)]
# mis의 값을 채우기 위한 탐색 함수
def make_set(prev, cur):
# 현재 노드가 독립집합에 포함되지 않은 경우와 포함된 경우의 최대 독립 집합 크기를 초기화
mis[cur] = [0, w[cur]]
# 현재 노드의 자식 노드 순회하며 최대 독립집합의 크기를 합산
for nxt in g[cur]:
if nxt != prev:
# 자식노드를 포함하지 않는 경우와 포함하는 경우의 최대 독립 집합 크기
inc, ninc = make_set(cur, nxt)
# 현재 노드가 포함된 상태일 경우 자식노드는 포함되지 않은 경우만 고를 수 있다.
mis[cur][1] += inc
# 현재 노드가 포함되지 않은 상태일 경우 자식노드는 모든 경우중 더 큰 값을 고를 수 있다.
mis[cur][0] += max(inc, ninc)
# 현재 노드에서의 최대 독립 집합의 크기를 반환
return mis[cur]
# 실제 최대 독립 집합을 구하기 위한 추적 함수
def trace_set(prev, cur, include):
# 반환할 실제 최대 독립 집합
res = set()
# 현재 노드가 독립 집합에 포함될 수 있으며
# 현재 노드가 포함되는 경우가 포함되지 않는 경우보다 독립 집합의 크기가 커진다면
# 최대 독립 집합에 현재 노드를 최대 독립 집합에 포함
# 현재 노드가 독립집합에 포함되었기 때문에 자식노드들은 포함될 수 없음
if include and mis[cur][1] > mis[cur][0]:
res.add(cur)
include = 0
# 현재 노드가 최대 독립 집합에 포함되지 않는 경우
# 다음 노드가 독립집합에 포함될 가능성이 있음
else:
include = 1
# 현재 노드의 자식노드를 순회
# 각 자식노드를 루트로 하는 서브트리의 최대독립집합을 반환할 최대 독립집합에 합한다.
for nxt in g[cur]:
if nxt != prev:
res |= trace_set(cur, nxt, include)
# 최대 독립 집합 반환
return res
# 탐색 시작
make_set(0, 1)
# 루트 노드로 삼을 1번 노드가 포함된 경우와 포함되지 않은 경우중 큰 쪽을 선택
# 최대 독립 집합의 크기와 최대 독립집합을 오름차순 정렬한 결과를 반환
if mis[1][0] > mis[1][1]:
return str(mis[1][0]) + '\n' + ' '.join(map(str, sorted(trace_set(0, 1, 0))))
else:
return str(mis[1][1]) + '\n' + ' '.join(map(str, sorted(trace_set(0, 1, 1))))
문제 해결의 요점은 트리를 탐색하는 dfs 함수가 현재 노드를 루트로 하는 서브 트리에서 현재 노드의 포함 여부에 따른 최대 독립집합의 크기를 반환하도록 하는 것이다. 즉, dfs(p, c) 는 부모 노드가 p인 현재 노드 c 에 대해 c를 루트 노드로 하는 서브트리에서 c가 최대 독립 집합에 포함되지 않는 경우가 포함되는 경우의 최대 독립 집합의 크기를 반환해야한다.
하지만 여기까지만으로는 최대 독립 집합의 크기밖에는 알 수가 없다. 실제로 최대 독립 집합을 구하려면 추적 함수가 필요하다. 특정 노드 k가 최대 독립집합에 포함되기 위한 조건은 다음과 같다.
① k의 부모 노드는 최대 독립 집합에 포함되지 않는다.
② k가 포함되는 경우의 최대 독립 집합의 크기가 포함되지 않는 경우의 최대 독립 집합의 크기보다 크다.
말은 조금 바뀌었지만 사실상 최대 독립 집합 문제이다. 다만 실제로 독립집합을 구하는 것이 아니라 가중치의 최대합만을 구하는 문제이기에 추적함수는 구현할 필요가 없다. 이를 구현한 코드는 다음과 같다.
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def sol1949():
# 노드의 갯수
n = int(input())
# 각 노드의 가중치
w = [0]+list(map(int, input().split()))
# 트리 구성
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# 탐색함수
def dfs(pre, cur):
# 현재 노드가 우수마을에 포함될지 여부에 따른 우수마을 주민 수 합의 최댓값
res = [0, w[cur]]
# 현재 노드의 자식노드들에 대해
for nxt in g[cur]:
if nxt != pre:
inc, ninc = dfs(cur, nxt)
# 현재 노드가 우수마을이 아니라면 다음 노드는 우수마을이거나 우수마을이 아닐 수 있다.
res[0] += max(inc, ninc)
# 현재 노드가 우수마을이라면 다음 노드는 우수마을이 아니어야 한다.
res[1] += inc
return res
# 우수 마을 주민 수 합의 최댓값 반환
return max(dfs(0, 1))
추가) 이 문제의 경우 독립집합에 포함되지 않는 노드는 반드시 인접한 노드중에 독립집합에 포함된 노드가 있어야한다는 조건을 추가로 제시하는데, 이는 사실 의미없는 함정 조건이다. 독립집합에 포함되지 않으면서 인접한 노드중 독립집합에 포함되는 노드가 하나도 없는경우가 있다면 본인이 독립집합에 추가될 수 있는데도 추가되지 않은 경우이다. 즉, 이 경우 최대 독립집합이 될 수 없기때문에 평범하게 최대 독립집합을 구하면 자연스레 만족되는 조건이다. 이와같이 굳이 필요없는 조건인데도 혼동을 주기위해 넣는 경우도 있으니 주의가 필요하다.
어떤 노드의 인접 노드가 모두 얼리어답터라면 그 노드가 얼리어답터가 아니어도 얼리어답터가 된다. 노드의 갯수가 N인 트리가 주어졌을 때, 트리의 모든 노드가 얼리어답터가 되도록 하기 위해서 최소 몇 개의 노드를 얼리어답터로 만들어야 하는지 구해야한다.
모든 노드를 얼리어답터로 만들기 위해서는 루트 노드가 얼리어답터가 아니라면 그 자식노드는 모두 얼리어답터여야 한다. 루트 노드가 얼리어답터라면 자식노드는 얼리어답터일 수도, 아닐 수도 있다.(둘 중 최적의 값을 고를 수 있다) 이는 최대 독립 집합 문제와는 정반대의 조건이라고 할 수 있다. 즉, 이 문제는 최대 독립 집합을 구했을 때, 최대 독립집합에 포함되지 않은 노드의 갯수를 구하는 문제가 된다. 이를 구현한 코드는 다음과 같다.
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def sol2533():
# 노드의 갯수
n = int(input())
# 트리 구성
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# 탐색 함수
def dfs(pre, cur):
# 현재 노드가 최대 독립 집합에 포함되지 않을 때, 포함 될 때의 최대 독립 집합의 크기
res = [0, 1]
# 현재 노드의 자식 노드에 대해
for nxt in g[cur]:
if nxt != pre:
inc, ninc = dfs(cur, nxt)
# 현재 노드가 최대 독립 집합에 포함되지 않는다면
# 자식 노드는 최대 독립 집합에 포함될 수도, 포함되지 않을 수도 있다.
res[0] += max(inc, ninc)
# 현재 노드가 최대 독립 집합에 포함된다면
# 자식 노드는 최대 독립 집합에 포함될 수 없다.
res[1] += inc
return res
# 전체 노드 수에서 최대 독립 집합의 크기를 뺀 값 반환
return n - max(dfs(0, 1))
풀이 1 - 최대 독립 집합의 크기를 구하는 코드의 반환 값을 전체 노드 수에서 최대 독립 집합의 크기를 뺀 값으로 변경
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def sol2533():
# 노드의 갯수
n = int(input())
# 트리 구성
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# 탐색 함수
def dfs(pre, cur):
# 현재 노드가 얼리어답터가 아닐 때, 얼리어답터일 때의 최소 얼리어답터 수
res = [0, 1]
# 현재 노드의 자식 노드에 대해
for nxt in g[cur]:
if nxt != pre:
inc, ninc = dfs(cur, nxt)
# 현재 노드가 얼리어답터가 아니라면 자식노드는 반드시 얼리어답터여야 한다
res[0] += ninc
# 현재 노드가 얼리어답터라면 자식노드는 얼리어답터일 수도, 아닐 수도 있다.
res[1] += min(inc, ninc)
return res
# 최소 얼리어답터 수 반환
return min(dfs(0, 1))
BFS는 시작노드의 인접노드를 모두 방문한 뒤, 그 인접 노드들의 인접노드를 모두 방문하는 형태로 탐색해나가는 방식의 완전 탐색 알고리즘이다. 방문 순서를 그림으로 나타낸다면 다음과 같다.
위와 같이 트리를 방문할 경우 방문 순서는 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 이 된다.
DFS의 경우 재귀호출로 인접노드를 순차적으로 방문하면 자연스럽게 구현되는 형태였지만 BFS의 경우 직접 큐를 사용하여 구현해줘야 한다. 시간복잡도의 경우 DFS와 마찬가지로 인접리스트 구현이라면 O(|V|+|E|), 인접행렬 구현이라면 O(V^2) 가 된다. BFS는 일반적으로 두 노드 사이의 최단거리를 구하는 문제나 인접노드에 대한 영향이 퍼져나가는 조건이 주어졌을 때 그 영향이 특정 수준에 도달하는데 걸리는 시간 등을 알아내는 문제 등에 주로 응용된다.
2. 최단거리 탐색
시작 노드 기준으로 같은 레벨의 노드들을 탐색하는 것을 한 사이클이라 하면 BFS가 어떤 노드를 방문한 시점의 사이클 수가 그 노드까지의 최단거리가 된다. 다만 이 방법으로 최단거리를 찾을 수 있는 것은 가중치가 없거나 모두 같은 그래프인 경우 뿐이다. 가중치가 있는 그래프의 최단거리를 찾기 위해서는 Dijkstra's Algorithm이나 Bellman-Ford's Algorithm, Floyd-Warshall Algorithm 등을 사용해야 한다. 이 방법을 통해 가중치가 없는 그래프의 최단거리 문제(https://www.acmicpc.net/problem/2178)를 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2178():
n, m = map(int, input().split())
# 미로
laby = [list(input().rstrip()) for _ in range(n)]
# 시작 위치
q = [(0, 0)]
# 사이클 수
cnt = 1
while q:
nq = []
for r, c in q:
# 현재 위치가 이미 방문된 상태일 경우 continue
if laby[r][c] != '1':
continue
# 현재 시점의 사이클 수 = 최단거리 로 갱신
laby[r][c] = cnt
# 인접 위치중 아직 방문하지 않았으며 갈 수 있는 위치를 큐에 삽입
for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
if 0<=nr<n and 0<=nc<m and laby[nr][nc]=='1':
nq.append((nr, nc))
# 다음 사이클을 위한 큐로 교체
q = nq
# 사이클 수 증가
cnt += 1
# n, m까지의 최단거리 반환 (인덱스가 0부터 시작하도록 구현했기에 n-1, m-1)
return laby[n-1][m-1]
queue 나 deque 모듈을 사용하여 실제로 큐를 사용한 구현도 가능하지만 같은 레벨의 노드를 방문하는 사이클을 구분하고 싶을 경우 위와 같이 별도의 큐에 다음 방문 노드들을 삽입한 뒤 큐를 교체하는 방식도 사용할 수 있다.
3. 상태 전이
어떠한 상태가 한 노드로부터 인접 노드로 일정 시간이 지날 때 마다 전이가 된다는 전제가 주어졌을 경우, 얼마만큼의 시간이 지나야 전이가 특정 수준까지 도달하는지 알아내는 문제를 해결하는 데에도 BFS를 사용할 수 있다. 사실 말이 바뀌었을 뿐 결국 최단거리 문제와 같은 이치이기 때문에 문제만 제대로 이해한다면 쉽게 해결 가능하다. 관련 문제(https://www.acmicpc.net/problem/7576)를 BFS로 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol7576():
m, n = map(int, input().split())
# 토마토 상태
tomato = [input().split() for _ in range(n)]
# BFS 큐
q = []
# 익지 않은 토마토 수
tc = 0
for i in range(n):
for j in range(m):
# 익지 않은 토마토가 있다면 익지 않은 토마토 갯수 증가
if tomato[i][j] == '0':
tc += 1
# 익은 토마토가 있다면 좌표를 BFS 큐에 삽입
elif tomato[i][j] == '1':
q.append((i, j))
# 익지않은 토마토가 없다면 0을 반환 - 이미 다 익어있음
if tc == 0:
return 0
# 익는데 필요한 날짜
res = 0
while q:
nq = []
for r, c in q:
# 익은 토마토에 인접한 토마토 중 익지 않은것이 있는 경우
# 토마토를 익히고 익지 않은 토마토 수를 감소시킨다
# 만약 익지 않은 토마토의 갯수가 0이된다면 지난 일수 res에 당일을 포함하여 res+1 반환
# 익은 토마토의 좌표를 큐에 삽입
for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
if 0<=nr<n and 0<=nc<m and tomato[nr][nc]=='0':
tomato[nr][nc] = '1'
tc -= 1
if tc == 0:
return res+1
nq.append((nr, nc))
# 큐 교체
q = nq
# 일수 + 1
res += 1
# 큐를 빠져나올 때 까지 익지 않은 토마토 수가 0이 되지 않았다면
# 모든 토마토를 익힐 수 없는 배치이기 때문에 -1 반환
return -1
위에서도 언급했지만 문제의 형태는 바뀌었지만 사실상 최단거리문제와 다를바가 없다. 다른 점이라면 시작 위치가 한 군데가 아니라는 것 정도이다. 시작부터 이미 전이가 완료된 상태이거나 전이가 완료될 수 없는 케이스인 경우의 예외처리를 잊지않고, 전이가 완료됐으면 바로 답을 반환하여 쓸데없는 추가연산을 하지 않도록 신경 써준다면 큰 어려움 없이 해결 가능한 문제이다.
DFS와 BFS는 처음에도 말했듯 코딩 테스트에서 굉장히 자주 사용하게 되는 알고리즘이고 결국 같은 완전탐색 알고리즘이지만 어느 한쪽으로는 해결이 불가능하거나 비효율적인 해결책이 되는 경우가 있기 때문에 두 방식 모두 잘 알아두고 여러 문제를 풀어보며 더 적합한 쪽을 골라 사용하는 습관을 들일 필요가 있다.
모든 경우의 수를 탐색하여 답을 찾아야 하는 완전 탐색 문제는 단순하지만 코딩 테스트 문제로 상당히 자주 출제된다. 특히 복잡한 규칙이 주어지고 그 규칙에 따라 완전탐색을 구현하여 해결하는 문제가 자주 보이는데 어렵지는 않지만 문제를 이해하는 데도 오래걸리고 구현과 디버깅에도 시간을 상당히 많이 소모하게 되기 때문에 많이 풀어서 익숙해질 필요가 있는 영역이다. 이번에는 완전탐색 중에도 DFS(깊이 우선 탐색)와 DFS 관련 문제들을 알아본다.
1. DFS(Depth First Search)
DFS는 시작 노드에서부터 갈 수 있는 데 까지 계속해서 다음 노드로 이동하다가 더이상 이동할 수 있는 노드가 없다면 이동할 수 있는 노드를 찾을 떄 까지 이전 노드로 돌아가기를 반복하는 방식의 완전탐색 알고리즘이다. 그림으로 표현하자면 다음과 같다.
위와 같이 트리를 DFS로 방문할 경우 방문 순서는 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 이 된다.
본래 DFS는 스택으로 구현되는 탐색 알고리즘이지만 실제로 구현할 때는 대부분 직접 스택을 사용하여 구현하기보다는 재귀를 사용하여 구현하게 된다. 인접리스트 방식으로 그래프를 표현할 경우 모든 정점과 간선을 탐색하기에 O(|V|+|E|), 인접행렬 방식일 경우 O(|V|^2)의 시간복잡도를 보인다. DFS는 두 정점의 연결 여부를 확인하거나 서로 연결된 노드들을 하나의 부분집합으로 볼 때 부분집합의 갯수를 세는 등의 문제에 활용된다.
2. 두 정점의 연결여부 확인
한 노드에서 시작하여 DFS를 호출하면 그 노드와 직/간접적으로 연결된 모든 노드를 탐색하기 때문에 두 정점이 연결되어있는지 확인 가능하다. 관련 문제(https://www.acmicpc.net/problem/2606)를 DFS를 활용하여 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2606():
# 정점의 수
n = int(input())
# 간선의 수
m = int(input())
# 인접리스트 그래프
g = [[] for _ in range(n+1)]
for i in range(m):
s, e = map(int, input().split())
g[s].append(e)
g[e].append(s)
# DFS 함수
def dfs(node):
# 현재 노드의 모든 인접 노드중 아직 방문하지 않은 노드에 대해
# 방문처리 및 DFS함수 재귀호출
for adj in g[node]:
if not visit[adj]:
visit[adj] = True
dfs(adj)
# 1번 컴퓨터부터 탐색 시작
visit = [False]*(n+1)
visit[1] = True
dfs(1)
# 방문표시된 컴퓨터 수 - 1 (1번컴퓨터는 포함하지 않음)
return visit.count(True)-1
DFS를 사용하여 1번 컴퓨터와 연결된 정점의 갯수를 모두 찾아내는 문제였다. 간단하지만 DFS에 대한 기본적인 이해를 다지고 넘어가기엔 적당하다.
3. 연결된 부분집합의 갯수 세기
연결그래프가 아닌 경우, 한 노드에서 시작하여 DFS를 실행하더라도 방문되지 않는 노드가 있을 수 있다.
이러한 경우 그 노드들에 대해서도 순차적으로 DFS를 호출하면 DFS의 호출 횟수(재귀호출 제외)로 연결된 부분집합의 갯수를 알아낼 수 있다. 관련 문제(https://www.acmicpc.net/problem/2667)를 DFS로 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2667():
n = int(input())
land = [list(input().rstrip()) for _ in range(n)]
# 깊이우선탐색 함수
def dfs(r, c):
# 방문한 땅에 표시
land[r][c] = 'x'
# 단지에 포함된 집의 갯수 카운트
cnt = 1
# 상/하/좌/우 칸 중 집이 있고 아직 방문하지 않은 경우
# 단지에 포함시키고 dfs 재귀호출
for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
if 0<=nr<n and 0<=nc<n and land[nr][nc]=='1':
cnt += dfs(nr, nc)
# 단지에 포함된 집의 수 반환
return cnt
# 지도를 순차적으로 순회하며 방문하지 않은 집마다 dfs 호출
res = [0]
for i in range(n):
for j in range(n):
if land[i][j] == '1':
res.append(dfs(i, j))
# 단지의 수와 단지에 포함된 집의 수를 오름차순정렬한 결과를 반환
res.sort()
res[0] = len(res) - 1
return '\n'.join(map(str, res))
if __name__ == '__main__':
print(sol2667())
dfs를 이러한 형태로 활용하는 문제는 굉장히 자주 등장한다. 다만 이 문제처럼 간단한 것 보다는 좀더 복잡한 경우가 대부분이다. 재귀를 활용하는 만큼 작은 실수로 예상치 못한 버그가 발생할 수 있으며 python의 경우 재귀가 그다지 효율적이지 못해 정상적으로 코드를 짜더라도 AC를 받지 못하는 문제도 종종 있기 때문에 보조언어로 C++ 등의 속도가 빠른 언어를 하나쯤 익혀둘 필요가 있다.
동적 계획법은 어떤 문제를 보다 쉽게 해결하기 위해 작은 문제로 나누어 해결하는 방식의 알고리즘이다. 마찬가지로 큰 문제를 분할하여 해결하는 분할 정복(Divide and Conquer) 알고리즘과의 차이는 분할 정복과는 달리 동적 계획법의 분할된 문제들끼리는 중복되는 부분이 존재한다는 것이다.
1. 메모이제이션(Memoization)
피보나치 수는 동적 계획법을 설명할 때 굉장히 자주 언급되는 문제이다. n번째 피보나치 수를 f(n) 이라고 할 때, f(n) = f(n-1) + f(n-2) 이다. 이에 따라 5 번째 피보나치 수를 구한다고 할 때, 과정을 트리형태로 나타내면 다음과 같은 형태가 된다.
그림 1
보다시피 같은 피보나치 수를 구하는 연산이 여러번 중복되어있다. 고작 f(5)를 구하는데도 이정도의 중복연산이 발생한다면 n이 좀더 커지면 어떻게 될지는 짐작이 갈 것이다. 이를 해결하기 위해 한번 실행된 연산의 결과를 메모리에 저장해두고 재사용하는 기법을 사용하는데, 이를 메모이제이션(memoization)이라고 하며 동적 계획법을 핵심이라고 볼 수 있는 부분이다. 간단한 예시지만 동적 계획법을 활용한 문제풀이는 대체로 이와같이 점화식을 찾아 문제를 분할하여 해결하도록 구현한 뒤, 중복되는 연산은 한번만 실행하고 값을 메모리에 저장하여 재사용 하는 것으로 최적화한다는 흐름으로 이루어진다.
2. Top-Down 동적 계획법
동적 계획법을 실제로 구현하는 형태중 하나로 함수의 재귀호출을 사용하는 top-down 방식이 있다. 피보나치 수를 예시로 들었을 때의 트리(그림 1)가 top-down의 형태를 가장 잘 나타낸다고 할 수 있을 것이다. 재귀함수를 다루는데 익숙하다면 구현이 편하고 가독성이 좋다는 장점이 있다. 하지만 재귀호출이라는 방식 자체의 한계로 속도 면에서 불이익이 있을 수 밖에 없다. 다만 간혹 n번째 값을 구하기 위해 n-1까지의 모든 값이 필요하지 않은 경우, top-down 형태의 구현이 불필요한 연산 횟수가 줄어들어 이후에 설명할 bottom-up 방식보다 더 나은 성능을 보이는 경우도 있어 어느쪽이 더 좋은지는 문제마다 다르다고 생각하는 것이 좋다.
Top-down 방식으로 피보나치 수를 구하는 문제를 해결한 코드는 다음과 같다.
dp = {}
def fibo(n):
# n이 1 이하일 경우 자기 자신을 반환 => f(0) = 0, f(1) = 1
if n <= 1:
return n
# fibo(n-1)가 아직 계산되지 않았다면 계산하여 메모리에 저장
if dp.get(n - 1, -1) == -1:
dp[n - 1] = fibo(n - 1)
# fibo(n-2)가 아직 계산되지 않았다면 계산하여 메모리에 저장
if dp.get(n - 2, -1) == -1:
dp[n - 2] = fibo(n - 2)
# fibo(n) = fibo(n-1) + fibo(n-2)
return dp[n - 1] + dp[n - 2]
3. Bottom-Up 동적 계획법
동적 계획법을 실제로 구현하는 또다른 형태로 bottom-up 방식이 있다. bottom-up 방식은 초기값 몇개를 구한 뒤 점화식을 토대로 계속해서 다음 값을 채워나가는 형태로 문제를 해결한다. 이미 계산된 값으로 다음값을 구해나가기 때문에 단순반복문으로 구현되며 초기값을 제대로 설정하고 점화식만 제대로 알아낸다면 놀라울정도로 간단하게 문제를 해결할 수 있고, 모든 경우를 따져봐야 답을 구할 수 있는 문제의 경우 재귀함수를 사용한 top-down 방식의 구현보다 속도가 빠르다. 다만 실제로 해결하려는 문제에 굳이 필요하지 않더라도 중간의 모든 값을 채워나가기 때문에 불필요한 연산이 추가적으로 발생할 수 있다는 단점도 존재한다.
bottom-up 방식으로 피보나치 수를 구하는 문제를 해결한 코드는 다음과 같다.
def fibo(n):
# f(0) = 0, f(1) = 1
fibo = [0, 1]
# fibo(n) = fibo(n-1) + fibo(n-2)
for i in range(2, n+1):
fibo.append(fibo[i-1] + fibo[i-2])
return fibo[n]
4. 동적 계획법이 적용될 수 있는 경우
동적 계획법은 특정 문제를 풀기위한 알고리즘이 아닌 문제를 해결하기위한 접근 방식, 방법론이기 때문에 그 활용도가 굉장히 높아 관련 문제도 다양하고 난이도 또한 문제에 따라 천차만별이다. 어떤 문제를 봤을 때, 동적계획법을 적용하여 해결 가능한지와 동적계획법을 어떻게 적용할 것인지를 빠르게 파악하는 것이 중요하다. 동적 계획법으로 풀 수 있는 문제들의 공통적인 특징 두가지에 대해 알아보자.
① 중복 문제의 발생
동적 계획법은 문제를 작게 쪼갠 뒤 중복연산의 결과를 메모리에 저장해두고 재활용하는 것으로 쪼개진 문제들을 빠르게 해결하는 방법론이다. 달리 말하면 분할된 문제들이 서로 중복되는 부분이 없다면 동적 계획법이 적용될 여지는 없다. 이 경우는 분할 정복의 영역이 될 것이다. 이진 탐색 문제나 병합정렬 등이 이와 같은 경우이다.
② 분할 가능 여부
문제에 따라서는 부분문제로 나누어 최적해를 취한 것이 전체로 볼 때는 최적해가 아닌 경우도 존재한다. 그런 경우를 예시로 하나 살펴보자.
* A 에서 B로 가는 경로
시간
요금
경로 1
3
15
경로 2
5
10
* B에서 C로 가는 경로
시간
요금
경로 1
7
25
경로 2
4
37
A에서 B로, B에서 C로 가는 경로별로 걸리는 시간과 요금이 위와같이 주어졌을 때, A에서 B를 경유하여 C로 가야할 때, 비용이 50을 넘지 않으면서 가장 짧은 시간 내에 갈 수 있는 경로의 조합을 구해야 한다면 각 구간으로 문제를 나누어 더 짧은 시간이 걸리는 쪽을 고르던 더 적은 요금이 드는 쪽을 고르던 전체 문제의 최적해에는 도달하지 못한다.
이러한 문제가 발생하는 것은 부분 문제들이 서로 독립적이지 않기 때문이다. 비용이 50을 넘어선 안되기 때문에 A에서 B로 가는 경로를 하나 고를 경우 B에서 C로 가는 경로를 고를 때는 비용의 한도가 A에서 B로 가기위한 비용만큼 줄어든다. 즉, 한 부분 문제에서의 선택이 다른 부분 문제에 영향을 미친다. 이런 형태의 문제에서는 동적 계획법을 적용하기 어렵다.
즉, 동적 계획법을 적용하기 위해서는 문제를 독립적인 부분문제들로 분할 가능해야하며 그 부분문제들 사이에 중복되는 부분이 있어야 한다 고 볼 수 있다. 다만 실전에서 문제를 봤을때 이런 부분들을 하나하나 계산해가며 동적 계획법을 적용할지 고민할 시간은 없기 때문에, 실제로 문제를 봤을때 동적 계획법의 적용 가능 여부를 판단할 수 있는 능력은 많은 문제를 풀어보며 경험으로 몸에 익히는 수 밖에 없을 것 같다.
대기열(Queue)은 본래 먼저 삽입된 데이터가 먼저 나가는 FIFO 자료구조이다. 하지만 경우에 따라서 나중에 들어왔더라도 먼저 처리해야하는 데이터가 존재할 수도 있다. 이러한 경우에는 들어온 순서와는 관계없이 우선순위가 높은 것을 먼저 내보내는 우선순위 큐를 사용한다. 물론 매번 데이터를 삽입할 때 마다 우선순위 기준으로 정렬을 실행하는 비효율적인 방식을 사용할 수는 없으니 우선순위 큐에는 힙(heap)이 사용된다. 우선순위 큐와 힙은 그 기능이 완전히 동일하다고 봐도 좋다.
1. 힙(Heap) 의 원리
힙(heap)은 완전 이진트리형태의 자료구조이다. 삽입, 삭제시에 항상 느슨한 정렬상태, 즉 부모노드가 자식노드보다 항상 크거나(최대 힙) 항상 작은(최소 힙) 상태를 유지하도록 하여 언제든지 루트노드를 참조하면 들어있는 데이터중 최소/최대 값을 바로 알아낼 수 있다.
힙의 구현은 주로 배열을 사용하여 이뤄진다. 트리라곤 해도 완전 이진트리 형태이기에 그쪽이 훨씬 구현이 쉽기 때문이다. 힙의 삽입, 삭제 절차와 이에따라 힙을 구현한 코드는 다음과 같다. 여기서는 최대힙을 기준으로 설명한다.
* 삽입
① 힙으로 쓸 배열의 맨 끝에 원소를 삽입한다.
② 삽입된 위치에서부터 부모노드를 탐색하여 부모노드가 존재하고 자신보다 값이 작다면 서로 위치를 바꾼다.
③ ② 과정을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.
* 삭제
① 반환할 힙의 최댓값(루트노드 값)을 별도의 변수에 저장해둔다.
② 루트노드의 값에 힙의 맨 끝의 값을 덮어씌우고 맨 끝의 값은 제거한다.
③ 루트노드에서부터 자식노드를 탐색하여 자신보다 더 큰 자식노드가 있다면 서로 위치를 바꾼다.
두 자식노드 모두 자신보다 크다면 둘 중 더 큰 쪽과 위치를 바꾼다.
④ ③ 과정을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.
⑤ 미리 저장해둔 힙의 최댓값을 반환한다.
def heappush(h, e):
# 삽입할 원소를 힙의 맨 끝에 삽입
h.append(e)
# 삽입된 원소의 현재위치
i = len(h) - 1
# 삽입된 원소의 부모노드
p = i // 2 - 1 + i % 2
# 삽입한 원소가 루트노드가 아닐 동안 반복
while i > 0:
# 부모 노드
p = i // 2 - 1 + i % 2
# 만약 부모노드의 값이 삽입된 원소보다 작다면 삽입된 노드와 자리를 바꾼다
# 계속해서 탐색하기 위해 삽입된 원소의 현재위치를 부모노드의 위치로 갱신
if h[p] < h[i]:
h[p], h[i] = h[i], h[p]
i = p
# 부모노드의 값이 삽입된 원소보다 크다면 더이상 탐색할 필요가 없음
else:
break
def heappop(h):
# 비어있는 힙에서 값을 얻으려한다면 None 반환
if not h:
return None
# 힙에 원소가 하나뿐이라면 pop한 결과 반환
if len(h) == 1:
return h.pop()
# 반환할 루트노드 값을 저장
res = h[0]
# 힙의 마지막 값을 pop하여 루트노드에 저장
h[0] = h.pop()
# 현재 노드
i = 0
while True:
# 좌, 우 자식 노드
l, r = i * 2 + 1, i * 2 + 2
# 값을 바꿀 타겟 노드를 현재 노드로 설정
t = i
# 좌측 자식 노드가 존재하고 그 값이 타겟 노드의 값 보다 크다면
# 좌측 자식 노드를 타겟 노드로 설정
if l < len(h) and h[l] > h[t]:
t = l
# 우측 자식 노드가 존재하고 그 값이 타겟 노드의 값 보다 크다면
# 우측 자식 노드를 타겟 노드로 설정
if r < len(h) and h[r] > h[t]:
t = r
# 타겟 노드를 찾았다면 현재 노드와 서로 값을 바꾼다
# 현재 노드를 타겟 노드로 갱신하고 좌우 자식노드를
if t != i:
h[i], h[t] = h[t], h[i]
i = t
# 타겟 노드를 찾지 못했다면 더이상 탐색할 필요가 없음
else:
break
# 미리 저장해둔 루트 노드 값 반환
return res
배열(리스트)를 인자로 받아 힙을 유지하도록 삽입/삭제하는 함수를 구현하는 방식으로 힙을 구현하였다. 힙의 삽입/삭제 연산은 O(logN)의 시간복잡도를 가지기에 삽입에 시간이 조금더 걸리긴 하지만 최댓값, 최솟값을 자주 구해야하는 경우 단순 배열에 삽입한 뒤 선형탐색을 하는 것 보다 훨씬 효율적이다. 삽입/삭제의 과정을 조금만 수정하면 최소힙, 절댓값 힙도 구현 가능하다.
2. heapq 모듈
힙의 구현이 그리 어려운 것은 아니지만 시간이 제한된 코딩테스트에서 힙을 직접 구현해가며 쓰는것은 시간낭비일 수 있다. python에서는 heapq 모듈을 제공하고 있어 굳이 직접 구현할 필요 없이 힙 삽입, 삭제, 변환 연산을 사용할 수 있다.
* heapq.heappush(h, e)
리스트 h에 힙 구조를 유지하도록 e를 삽입한다.
* heapq.heappop(h)
리스트 h에서 힙 구조를 유지하도록 최솟값을 제거하고 제거된 값을 반환한다.
* heapq.heapify(h)
리스트 h를 힙 구조로 변환한다.
python의 heaqp 모듈은 기본적으로 최소 힙으로 구현되어있다. 최대 힙으로 사용할 경우 넣으려는 값에 음수를 취해주고 꺼낼 때도 마찬가지로 음수를 취하는 방식을 사용해야한다.
k개의 랜선의 길이와 필요한 랜선의 갯수 n이 주어졌을 때, 같은 길이의 n개의 랜선을 만들 수 있는 랜선의 최대길이를 구하는 문제이다. 해결하는 절차와 이를 구현한 코드는 다음과 같다.
① 랜선을 m만큼의 길이로 자른다고 가정한다.
② 길이는 정수이며 0으로 자르는것은 의미가 없기 때문에 m의 최솟값은 1이 된다.
③ k개의 랜선을 손실을 최소화하여 잘라도 n개의 선을 만들기 위해서는 m은 랜선의 길이를 모두 합한 값을
n으로 나눈 것 보다 작거나 같기 때문에 m의 최댓값은 sum(lans) // n이 된다.
④ 1이상 sum(lans) // n 이하의 정수에서 이분탐색을 실시한다
⑤ 만약 랜선을 m만큼씩 잘랐을 때 n개보다 적다면 더 작게 잘라서 수를 늘리기 위해 e = m - 1
⑥ 만약 랜선을 m만큼씩 잘랐을 때 n개 이상이라면 최댓값을 찾기 위해 s = m + 1
⑦ 탐색이 종료된 시점에서 s는 마지막으로 n개의 랜선을 만드는데 성공한 m에 1을 더한 값이므로 문제의 답은 s -1
import sys
input = sys.stdin.read
def sol1654():
k, n, *lans = map(int, input().split())
# 2, 3
s, e = 1, sum(lans)//n
# 4
while s <= e:
# 1
m = (s + e) // 2
# 5
if sum([lan//m for lan in lans]) < n:
e = m - 1
# 6
else:
s = m + 1
# 7
return s-1
이런 식으로 이분 탐색을 활용하여 어떤 조건을 만족하는 최소/최대 값을 찾는 방식을 parametric search라고 한다. 최소/최대값을 찾으려는 값의 범위내에서 이분탐색을 실행하여 중간값에 대하여 조건의 만족여부를 검사한 뒤 조건을 만족한다면 좀더 최적의 값을 찾아내기 위한 방향으로 범위를 좁히고, 조건을 만족하지 못한다면 조건을 만족할 수 있는 방향으로 범위를 좁혀나가며 최적의 값을 탐색하는 것이다. 같은 방식이지만 좀더 어려운 문제로 백준의 1300번 문제(https://www.acmicpc.net/problem/1300)가 있지만 parametric search를 활용한다는 것만 염두에 두면 쉽게 해결 가능한 문제이니 따로 다루지는 않는다.
수열 A의 크기 N과 수열 A가 주어졌을 때 가장 긴 증가하는 부분수열의 길이를 구하는 문제이다. 랜선 자르기 문제의 경우 문제 해결의 핵심이 이분탐색의 응용이었다면 이 문제에서는 문제를 해결하기 위한 알고리즘(LIS 알고리즘)을 최적화하기 위한 수단으로 사용된다. 문제를 해결하는 절차와 이를 구현한 코드는 다음과 같다.
① 비어있는 배열(리스트) lis 를 생성
② A의 원소 a에 순차적으로 접근
③ 만약 lis가 비어있거나 a가 lis의 마지막 값보다 크다면 증가수열의 길이가 늘어난 것으로 볼 수 있기에
lis에 a를 append
④ 그렇지 않다면 이 수를 포함한 증가하는 부분 수열이 길이가 가장 길 수도 있기 때문에 lis 내의 원소 중에서
a보다 크거나 같은 수 중에서 가장 작은 수를 대체
⑤ A의 순회가 끝난 후 lis의 길이가 최장 증가 수열의 길이가 된다.
import sys
input = sys.stdin.read
def sol12015():
n, f, *seq = map(int, input().split())
# 1
lis = [f]
# 2
for num in seq:
# 3
if num > lis[-1]:
lis.append(num)
# 4
else:
s, e = 0, len(lis)-1
while s <= e:
m = (s + e) // 2
if lis[m] < num:
s = m + 1
else:
e = m - 1
lis[e+1] = num
# 5
return len(lis)
이 풀이의 4번 과정에서, 오름차순 정렬된 배열 lis에서 num 보다 크거나 같은 수 중 최솟값의 위치를 찾기 위해 이분탐색이 활용된 것을 볼 수 있다. 이분 탐색의 응용이긴 해도 parametric search의 형태였던 1번 문제와는 달리 여기서의 이분탐색은 정렬된 배열에 대해 실시하는 일반적인 이분 탐색이다.
3. bisect 모듈
2번 문제를 직접 구현한 이분 탐색으로 풀 경우 시간초과는 발생하지 않지만 상당히 느리다. 또한 이분탐색의 구현이 어려운 편은 아니지만 이분 탐색이 필요할 때 마다 매번 직접 구현하는 것은 꽤나 귀찮고 시간을 잡아먹는 일이다. 파이썬에서는 bisect 모듈을 사용하여 직접 구현할 필요 없이 이분탐색을 실시할 수 있다.
import sys
# bisect 모듈의 bisect_left 함수 import
from bisect import bisect_left
input = sys.stdin.read
def sol12015():
n, f, *seq = map(int, input().split())
lis = [f]
for num in seq:
if num > lis[-1]:
lis.append(num)
# lis에서 num이 들어갈 자리를 탐색
else:
lis[bisect_left(lis, num)] = num
return len(lis)
bisect 모듈의 bisect_left, bisect_right 는 탐색할 리스트와 키가 될 값을 입력받아 해당 값을 리스트가 정렬된 상태를 유지하며 삽입하기 위한 인덱스를 반환한다. 배열에 키 값과 중복되는 값이 존재할 경우, bisect_left는 중복 값중 가장 앞쪽에 있는 값의 인덱스를 반환하며, bisect_right는 키 값보다 큰 값중 최솟값의 인덱스를 반환한다는 것이다. 여기서는 num 보다 크거나 같은 값중 최솟값을 찾아야 하기에 bisect_left를 사용하였다.
위쪽이 bisect 모듈을 사용한 코드, 아래쪽은 직접 이분탐색을 구현 한 코드를 제출한 것이다.
bisect 모듈을 사용하면 코드 작성의 시간도 절약하고 편리할 뿐만 아니라 퍼포먼스 상에서도 이점이 있다. 탐색할 배열의 크기가 커질수록 bisect 모듈을 사용한 탐색이 대체로 더 좋은 성능을 보인다.
접속 가능한 로컬 서버와 데이터를 나타낼 모델까지 준비가 끝났으니 이제 실제로 서버에 접속한 사용자에게 데이터를 보여줄 차례이다.
pybo\views.py 의 내용을 위와 같이 수정한다. Question 데이터를 생성 날짜순으로 내림차순 정렬한 뒤 pybo\question_list.html 이라는 템플릿으로 넘겨주고 그 결과를 렌더링하여 웹상에서 보여주겠다는 내용이다.
DIRS 에 templates 디렉토리를 추가.
이제 데이터를 넘겨줄 템플릿을 실제로 만들어야한다. 우선 템플릿들을 저장할 templates 디렉토리를 mysite 디렉토리 하위에 생성한다. pybo 디렉토리 내에 templates 디렉토리를 생성해도 되고 그렇게하면 별도의 설정없이도 django에서 템플릿 디렉토리로 인식하지만 여러 앱이 공유하는 템플릿의 위치 문제등을 고려하면 화면을 구성하는 템플릿들은 하나의 디렉토리에 모아두는게 좋다고 한다. 그러니 여기서는 mystie 하위에 templates 디렉토리를 생성하고 그 내부에 각 앱들의 템플릿을 모아둘 디렉토리를 생성한 뒤 config\settings.py에서 템플릿 디렉토리로 등록해준다.
templates\pybo\question_list.html 을 위와같이 수정한다. html코드 사이에 들어간 중괄호로 둘러쌓인 코드를 템플릿 코드라 한다. 이처럼 HTML태그와 템플릿 코드를 혼용하여 작성한 파일을 템플릿이라 한다. python의 문법을 아는 사람이라면 템플릿코드의 의미는 어렵지않게 이해할 수 있다. 위의 템플릿의 경우 question_list가 비어있지 않다면 question_list 내의 question들을 하나씩 순회하며 각 question의 id번호에 매칭되는 url을 하이퍼링크로 가지는 텍스트를 리스트형태로 보여주는 것이다. 텍스트의 내용은 각 question의 제목이 된다. 만약 question_list가 비어있다면 "질문이 없습니다." 라는 메시지가 출력된다.
이제 localhost:8000/pybo/ 에 접속하면 위와 같이 저장한 question 들이 리스트의 형태로 표시된다.
2. Question Detail
pybo 페이지에서 각 question들에 걸린 하이퍼링크를 따라가면 당연하게도 에러가 발생한다. 하이퍼링크의 url은 ~/pybo/{id번호} 의 형태로 되어있는데, 우리는 아직 그런 페이지의 url 매핑을 해주지 않았기 때문이다.
pybo\urls.py 를 위와 같이 수정한다. pybo/{question_id} 형태의 url에 대해 pybo\views.py의 detail 메소드를 매핑한 것이다.
get_object_or_404는 Question.get() 을 호출한 것과 같은 기능이지만 찾으려는 모델이 존재하지 않을 경우 get을 사용하면 500에러가 발생하는데 비해 get_object_or_404는 404에러(page not found)를 일으킨다. 없는 데이터를 요청했을 때의 에러는 404페이지가 출력되는 것이 바람직하기에 get_object_or_404쪽을 쓰기로한다. pk는 primary key, 즉 모델의 기본키를 의미한다.
마지막으로 detail 에서 렌더링할 pybo\question_detail.html 템플릿을 위와같이 작성한다. 매우 간단하게 질문의 제목과 내용만을 표시하는 템플릿이다.
