1. 좌표 압축
주어진 수의 범위가 매우 클 때, 수의 값을 수의 순서(대소관계)로 치환하여 전체 범위를 줄이는 테크닉을 말합니다.
좌표 압축만 가지고 문제를 해결하기 보다는 복잡한 문제를 단순하게 만드는 데 많이 활용됩니다.
주로 세그먼트 트리 자료구조와 스위핑 알고리즘과 함께 많이 사용됩니다.
10. 좌표 압축
## 좌표 압축 좌표 압축은 알고리즘이라기 보다 테크닉에 가깝습니다. 좌표 압축을 통해 어떤 문제를 해결하기 보다는 복잡한 문제를 해결하는데 도움을 주기 때문입니다. 여러 좌표…
wikidocs.net
좌표 압축 과정을 살펴봅시다.
5, 2, 10, 4, 2 이 다섯 개의 숫자를 좌표 압축하는 과정을 그림을 보며 알아보겠습니다.
가. 인덱스 값(순서 값)을 지정
각 숫자들에게 순서에 따라 인덱스 값을 지정합니다.
나. 값 기준으로 정렬
각 숫자들의 값을 기준으로 정렬합니다.
중복된 값은 같은 자리에 세웁니다.
다. 정렬된 순서로 값 치환(좌표 압축)
정렬된 순서대로 새로운 인덱스 값으로 원래의 값을 치환합니다.
치환된 값은 좌표 압축된 새로운 값입니다.
같은 자리는 같은 값으로 치환합니다.
라. 인덱스 값을 기준으로 정렬
이제 다시 인덱스 값을 기준으로 정렬하게 되면 좌표 압축이 완료됩니다.
좌표 압축 결과 (5, 2, 10, 4, 2)는 (3, 1, 4, 2, 1)로 바뀌게 되었습니다.
2. 파이썬 코드
가. 변수 설정
숫자들을 리스트 타입 자료형으로 초기화합니다.
예제의 5, 2, 10, 4, 2를 순서대로 담았습니다.
li = [5, 2, 10, 4, 2]나. 인덱스 값(순서) 지정
숫자들에게 인덱스 값을 지정해줍니다.
내장 객체인 enumerate를 사용하여 코드 한 줄로 처리할 수 있습니다.
li = [*map(list, enumerate(li))]
print(li)
# [[0, 5], [1, 2], [2, 10], [3, 4], [4, 2]]다. 값 기준으로 정렬
원래 숫자를 기준으로 정렬합니다.
인덱스 값이 아님에 주의합니다.
li.sort(key=lambda item: item[1])
print(li)
# [[1, 2], [4, 2], [3, 4], [0, 5], [2, 10]]라. 정렬된 순서로 값 치환(좌표 압축)
중복된 값을 같은 값으로 바꾸어야하기 때문에 다음과 같이 반복문들 통해 값을 수정합니다.
prev는 이전 값을 저장하여 값의 중복 여부를 파악합니다.
첫 번 째 값은 이전 값이 없으므로 prev의 초기값은 무한대입니다.
순서를 저장하는 num의 경우도 첫 번 째 값을 확인할 때 1 커지므로 -1로 초기화합니다.
num = -1
prev = float("inf")
for i in range(len(li)):
if li[i][1] != prev:
prev = li[i][1]
num += 1
li[i][1] = num
print(li)
# [[1, 0], [4, 0], [3, 1], [0, 2], [2, 3]]마. 인덱스 값을 기준으로 정렬
인덱스 값을 기준으로 정렬합니다.
정렬 후 인덱스 값은 제거하고, 좌표 압축된 결과를 확인합니다.
li.sort()
li = [item[1] for item in li]
print(li)
# [2, 0, 3, 1, 0]3. Set과 Dictionary를 사용하는 방법
위의 과정을 살펴보면 중복되는 수가 많을수록 효율성이 떨어진다는 것을 알 수 있습니다.
따라서 중복을 제거하고, 숫자를 키로 사용하여 순서를 값으로 가지는 해시 테이블을 만들면 더 쉽게 좌표 압축을 할 수 있습니다.
파이썬에서는 중복을 제거하는 데 Set 자료형을, 해시 테이블은 Dict 자료형을 사용합니다.
가. 해시 테이블 작성
해시 테이블은 Dict 자료형을 사용하므로 초기화합니다.
Set 자료형을 사용하여 중복된 숫자들을 정리합니다.
내장함수 sorted를 사용하여 중복이 제거된 숫자들을 정렬합니다.
내장객체 enumerate를 사용하여 해시 테이블에 숫자는 키로, 순서는 값을 저장합니다.
딕셔너리 자료형도 컴프리핸션 문법을 사용하여 작성할 수 있으므로 위의 과정을 한 줄로 작성할 수도 있습니다.
li = [5, 2, 10, 4, 2]
# 해시 테이블 초기화
hash_table = {}
# 중복 제거(Set 자료형 사용)
num_set = set(li)
# 정렬
sorted_num_set = sorted(num_set)
# 정렬된 순서로 숫자는 키, 순서는 값을 해시 테이블에 저장
for i, num in enumerate(sorted_num_set):
hash_table[num] = i
# 컴프리핸션 문법으로 한 줄로도 가능
# hash_table = {num: i for i, num in enumerate(sorted(set(li)))}
print(hash_table)
# {2: 0, 4: 1, 5: 2, 10: 3}나. 원래 숫자들을 가지고 순서를 출력
완성된 해시 테이블을 가지고, 원래의 숫자들을 순서대로 대입하여 얻어지는 순서를 저장하면 좌표 압축이 완료됩니다.
li = [hash_table[num] for num in li]
print(li)
# [2, 0, 3, 1, 0]
