➊ 서론
① 문제
1부터 N번까지로 수로 이루어진 순열이 있다.
그리고 이 순열과 연관된 "Inversion sequence"라고 부르는 수열이 있다. 이 수열의 i번째 원소에는 순열에서 i보다 뒤에 나오면서 i보다 작은 수의 개수가 들어간다.
2 4 5 1 7 6 3 8
위의 순열이 있다면 이것의 Inversion sequence는
0 1 0 2 2 1 2 0 이 된다.
문제는 역으로 어떤 Inversion sequence가 주어지면 이것에 해당하는 순열을 찾는 프로그램을 작성하는 것이다.
② 문제를 이해해보자!
나 자신이 '컴퓨터'라 생각하고 반전 수열로부터 원래 수열을 도출해보자!
# 반전 수열
inversion_sequence = [ 0 1 0 2 2 1 2 0 ]
# 원래 수열
original_sequence = [ ? ? ? ? ? ? ? ? ]반전 수열에서,
1번째에 위치하는 0이라는 수는 다음을 의미한다.
→ 1 뒤에 위치하는 1보다 작은 수는 0개 존재한다.
2번째에 위치하는 1이라는 수는 다음을 의미한다.
→ 2 뒤에 위치하는 2보다 작은 수는 1개 존재한다.
⋮
8번째에 위치하는 0이라는 수는 다음을 의미한다.
→ 8 뒤에 위치하는 8보다 작은 수는 0개 존재한다.
이를 일반화하면 다음과 같다.
inversion_sequence[i-1] = i보다 뒤에 나오면서 i보다 작은 수의 개수
(index가 0부터 시작하기 때문에 i-1이라 적었다!)
따라서 우리는 반전 수열을 for문으로 순회하면서
1부터 N까지의 수가 원래 수열에서 위치해야 할 index을 구해야 한다!
➋ 풀이 과정
아이디어 ① - 뒤에서부터 순회
반전 수열을 순회할 때,
앞에서부터 순회하는 방법이 있고 뒤에서부터 거꾸로 순회하는 방법이 있다.
결론부터 말하자면 뒤에서부터 거꾸로 순회해야 index을 결정할 수 있다!
왜일까? 앞에서부터 순차적으로 순회한다고 가정해보자.
1→2→...→8 순으로 이 숫자가 원래 수열에서 위치하는 index을 찾아야 한다.
먼저, 1이 원래 수열에서 위치하는 index을 결정해야 하는데
1이 어느 곳에 위치하든 1 뒤에 위치하는 1보다 작은 수는 0개가 될 수밖에 없다!
왜냐하면 1부터 N까지의 수 중에서 1이 가장 작은 수이기 때문이다.
그렇다면 뒤에서부터 거꾸로 순회하는 방법을 생각해보자.
8→7→...→1 순으로 이 숫자가 원래 수열에서 위치하는 index을 찾아야 한다.
먼저 8을 생각해보자!
8 뒤에 위치하는 8보다 작은 수는 0개이다.
8이 가장 큰 수이기 때문에 1~7 수가 들어올 빈 자리를 남겨두면 안 된다.
즉, 8은 리스트의 마지막에 위치해야 한다.
7을 생각해보자!
7 뒤에 위치하는 7보다 작은 수는 2개이다.
7보다 작은 수가 들어올 빈 자리를 2개 남겨두어야 한다.
따라서 위 그림과 같이 7의 자리(index)를 결정할 수 있다.
이처럼 반전 수열의 뒤부터 거꾸로 순회하면서
원래 수열을 알아낼 수 있다!
이를 파이썬 코드로 작성하면 다음과 같다 ⬇️
N = int(input())
# 반전 수열
inversion_sequence = [0] + list(map(int, input().split()))
# 원래 수열
original_sequence = [0] * N
def get_index():
(원래 순열에 위치해야 할 index을 찾는 코드)
for i in range(N, 0, -1):
index = get_index()
original_sequence[index] = i아이디어 ② - 세그먼트 트리
그렇다면 get_index 함수는 어떻게 구현할 수 있을까?
가장 단순하게 생각하면,
원래 수열을 뒤에서부터 탐색하며 빈 자리가 몇 개 있는지 계산하는 방법이 있을 것이다.
하지만 위의 방법은 이중 for문을 사용해야 하기 때문에 시간복잡도가 O(N^2)이 된다.
O(N^2)은 시간 초과가 발생하기 때문에 다른 방법을 생각해야 한다.
그렇다면 🤔
빈 자리의 개수를 미리 구해두고 이를 그대로 가져오는 방법은 어떨까?
(여기서부터는 세그먼트 트리에 대한 기본적인 알고리즘 지식이 있다고 가정하고 설명하겠습니다.)
구간 별 빈 자리의 개수를 미리 구해두고 세그먼트 트리에 저장한다.
아래의 세 단계를 거쳐 세그먼트 트리를 활용해 인덱스를 구한다!
- 트리 초기화 (init)
구간 별 빈 자리의 개수를 미리 구하여 트리에 저장한다.
-
인덱스 구하기 (get_index)
루트 노드에서부터 시작하여
빈 자리의 개수에 따라 왼쪽 노드로 갈지 오른쪽 노드로 갈지 결정한다.
최종적으로 리프 노드에 도달하면 인덱스를 반환한다. -
트리 갱신 (update)
빈 자리에 숫자가 하나 채워지면 해당 구간의 빈 자리의 개수를 1 감소시킨다.
단계별로 더 자세히 설명하도록 하겠다!
㉠ 트리 초기화 (init)
처음에는 original_sequence(원래 수열)의 모든 자리가 비어있기 때문에 모든 리프 노드를 1로 초기화해야 한다.
이때 루트 노드는 index 0부터 7까지의 구간 안에 존재하는 빈 자리의 개수이다.
그리고 이 루트 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 이어져 있는데,
왼쪽 자식 노드는 index 0부터 3까지의 구간 안에 존재하는 빈 자리의 개수이며
오른쪽 자식 노드는 index 4부터 7까지의 구간 안에 존재하는 빈 자리의 개수이다.
이처럼 리프노드에 도달할 때까지 반으로 쪼개기를 반복한다!
이 세그먼트 트리를 초기화하는 코드는 다음과 같다!
재귀 함수를 통해 구현하였다.
# 세그먼트 트리 초기화
# start와 end는 구간의 경계
# node는 세그먼트 트리 내 노드의 index
def init(start, end, node):
if start == end:
tree[node] = 1
return tree[node]
mid = (start + end) // 2
tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1)
return tree[node]㉡ 인덱스 구하기 (get_index)
트리를 초기화했으면 이제 원래 수열에 위치해야 할 index를 구할 차례이다.
여기서부터는 이해하기 조금 어렵다.
예시를 들어 설명하도록 하겠다!
(예시 1)
inversion_sequence = [ 0 1 0 2 2 1 2 0 ]
8이 위치해야 할 index을 찾아보자!
8 뒤에 위치하는 8보다 작은 숫자의 개수를 의미하는 0을 value로 칭하도록 하겠다.
루트 노드부터 시작하여 리프 노드에 도달할 때까지 아래로 내려간다.
이때 왼쪽 노드로 이동할지 오른쪽 노드로 이동할지 결정해야 하는데,
오른쪽 노드(4~7)의 빈 자리는 4개이며 value 보다 크다!
숫자 8 뒤에는 value만큼의 자리만 남겨야 한다.
그러므로 오른쪽 노드로 이동한다.
마찬가지로 어느 방향의 자식 노드로 갈지 결정해야 한다.
오른쪽 노드(6~7)의 빈 자리는 2개이며 value 보다 크다!
따라서 오른쪽 노드로 이동한다.
오른쪽 노드(7)의 빈 자리는 1개이며 value 보다 크다!
따라서 오른쪽 노드로 이동하여 리프 노드에 도달하였다.
도착한 리프 노드의 구간은 7이며 이는 8이 원래 수열에서 위치해야 할 index가 된다.
(예시 2)
8, 7, 6의 index을 찾았다고 가정하고 이제 5의 index을 찾아보자!
빈 자리가 3군데 채워졌으므로 트리 또한 업데이트 됐다고 가정한다.
루트 노드에서 시작하여 왼쪽 노드로 갈지 오른쪽 노드로 갈지 결정해야 한다.
오른쪽 노드(4~7)의 빈 자리는 고작 1개뿐이다.
그러나 value은 2이기 때문에 빈 자리 2개가 필요하다.
오른쪽 노드(4~7)의 빈 자리가 부족하므로 왼쪽 노드로 이동한다.
여기서 중요한 점 🚨
왼쪽 노드로 이동할 때 value = value - 1을 해준다.
왜냐하면 4~7 구간에 빈 자리가 1개 있기 때문에 이를 반영해주어야 한다.
value의 값이 1로 바뀌었으며 마찬가지로 왼쪽 노드로 이동할지 오른쪽 노드로 이동할지 결정해야 한다.
오른쪽 노드(2~3)의 빈 자리의 개수는 2이고 value보다 크다.
따라서 오른쪽 노드로 이동한다.
마지막으로 오른쪽 노드(3)의 빈 자리는 1개이고 value와 같다.
value의 의미를 다시 상기시켜보자.
value는 숫자 뒤에 남겨두어야 할 빈 자리의 개수다.
따라서 빈 자리 1개가 필요하기 때문에 왼쪽 노드로 이동한다.
이로써 2를 가리키는 리프 노드에 도달하였다.
이는 숫자 5가 원래 수열에서 위치해야 할 index를 가리킨다.
위와 같은 과정을 반복하여 모든 숫자의 index을 찾는다.
이 과정을 담은 파이썬 코드는 아래와 같다.
# 원래 순열에 위치해야 할 index을 찾는다!
def get_index(start, end, node, value):
if start == end:
return start
mid = (start + end) // 2
if value < tree[node * 2 + 1]:
return get_index(mid + 1, end, node * 2 + 1, value)
else:
return get_index(start, mid, node * 2, value - tree[node * 2 + 1])㉢ 트리 갱신 (update)
사실 original_sequence의 빈 자리가 하나씩 채워질 때마다 세그먼트 트리를 갱신해야 한다.
세그먼트 트리를 갱신할 때도 루트 노드부터 시작하여 아래로 내려가면서 빈 자리의 개수를 1 감소시킨다.
이때, original_sequence에서 채워진 자리의 index가 구간 안에 포함일 때만 1 감소시킨다.
아래는 세그먼트 트리를 갱신하는 파이썬 코드이다.
# 세그먼트 트리 갱신
def update(start, end, node, index):
# index가 구간 안에 포함되지 않으면
if not (start <= index <= end):
return
# 구간 안에 포함되면 1 감소시킴
tree[node] -= 1
# 리프 노드에 도달하면 update을 멈춤
if start == end:
return
mid = (start + end) // 2
update(start, mid, node * 2, index)
update(mid + 1, end, node * 2 + 1, index)➌ 전체 코드
import math
# 세그먼트 트리 초기화
def init(start, end, node):
if start == end:
tree[node] = 1
return tree[node]
mid = (start + end) // 2
tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1)
return tree[node]
# 원래 순열에 위치해야 할 index을 찾는다!
def get_index(start, end, node, value):
if start == end:
return start
mid = (start + end) // 2
if value < tree[node * 2 + 1]:
return get_index(mid + 1, end, node * 2 + 1, value)
else:
return get_index(start, mid, node * 2, value - tree[node * 2 + 1])
# 세그먼트 트리 갱신
def update(start, end, node, index):
if not (start <= index <= end):
return
tree[node] -= 1
if start == end:
return
mid = (start + end) // 2
update(start, mid, node * 2, index)
update(mid + 1, end, node * 2 + 1, index)
N = int(input())
# 반전 수열
inversion_sequence = [0] + list(map(int, input().split()))
# 원래 수열
original_sequence = [0] * N
# 트리의 높이
h = math.ceil(math.log2(N))
# 세그먼트 트리 생성
tree = [0] * (2 ** (h+1))
init(0, N-1, 1)
for i in range(N, 0, -1):
index = get_index(0, N-1, 1, inversion_sequence[i])
original_sequence[index] = i
update(0, N-1, 1, index)
print(*original_sequence)
최대한 쉽게 설명해보려고 노력했는데 어떨지 모르겠습니다
질문 사항이나 이해가 안 가는 부분이 있다면 언제든지 댓글 남겨주세요
감사합니다 🙂
