https://www.acmicpc.net/problem/10989
다음 문제를 풀며 공부한 내용을 기록
처음에 접근한 방법은 입력값을 빈 배열에 appened하고, sort()로 오름차순하여 출력하는 간단한 방법이었다.
import sys
n = int(sys.stdin.readline())
n_list = []
for _ in range(n):
n_list.append(int(sys.stdin.readline()))
n_list.sort()
for i in n_list:
print(i)하지만 메모리 초과가 발생했다. 입력 수의 개수가 매우 큰 경우에는 이를 모두 리스트에 저장하면 메모리를 과도하게 사용하기 때문이다.
그래서 문제의 조건을 다시 살펴봤다.
주어진 수의 범위가 1 ~ 10,000이고, 수의 개수가 최대 10,000,000개까지 주어지며, 메모리 제한은 8MB이다.
일반적인 상황에서 정수형 데이터(4바이트) 천만 개가 들어온다고 하면, 40MB로 당연히 메모리 초과가 난다.
해결의 힌트는 정수의 범위에 있었다. 정수의 범위가 정해져 있으면서 그 값의 범위가 작기에, 빠른 속도로 정렬이 가능한 계수 정렬 알고리즘을 이용할 수 있다.
💡 계수 정렬
- 각 항목이 몇 개 있는지 카운트하는 정렬
- 기본 정렬 알고리즘과 다르게 숫자 비교 작업이 없어 빠른 속도로 정렬 가능
- 자료의 범위를 알고 있으며, 정렬할 값이 정수일 때 사용
정수의 범위에 해당하는 배열을 만들어놓고, 들어오는 숫자마다 배열의 index에 값을 더해주는 것. 개념 자체는 간단하다. 계수 정렬을 이용한 코드는 아래와 같다.
import sys
n = int(sys.stdin.readline())
n_list = [0] * 10001
for _ in range(n):
n_input = int(sys.stdin.readline())
n_list[n_input] += 1
for i in range(10001):
if n_list[i] != 0:
for j in range(n_list[i]):
print(i)시간복잡도 : O(N+K)
- K = 배열 내 최댓값
- K가 커질수록 무한대에 가까워져 떨어지는 성능 ⇒ 입력값의 범위가 작을 때 높은 효율
최댓값이 주어지지 않은 경우, 전체 배열을 탐색해야 하므로 O(n), Counting Array에 개수를 카운팅하는 과정에서 O(n)이 소요된다. 이후 결과 배열에 값을 입력하여 정렬된 배열을 얻는 과정에도 O(n)이 소요되어 최종적으로 O(n)의 시간복잡도를 가지며, 정렬 시간은 K에 종속된다.
하지만 계수 정렬은 자료의 범위를 알고 있어야 사용이 가능하다는 제약이 있다.
그렇다면 자료의 범위가 정해져있지 않다면 어떤 알고리즘을 써야할까?
물론 계수 정렬만큼의 효율은 내지 못하겠지만 시간복잡도를 조금 희생하면서 계수 정렬의 비슷하거나 동일한 개념을 적용시키는 방법이 없을지 고민하는 시간을 가져봤다.
위에서 언급했듯이, 계수 정렬은 배열 내 최댓값이 커질수록 성능이 떨어진다. 이는 선형 자료구조에서 흔히 나타나는 단점이다. 속도는 빠르나, 수의 범위가 넓어지면 그만큼의 배열이 필요하기 때문에 공간의 제약을 받는다.
위에서 언급한 내용들을 토대로 💡Map 자료구조를 생각해봤다. Map을 선택한 근거는 다음과 같다.
- 유연한 크기 조절: Map은 크기를 별도로 지정하지 않아도 되며, 동적으로 크기를 조절할 수 있다. 입력 데이터의 크기에 따라 조절되기 때문에, 위에서 언급한 “자료의 범위가 정해져있지 않다면?”에 대한 해답을 내놓음과 동시에, 선형 자료구조의 단점인 메모리 효율성 문제를 해결할 수 있는 근거가 된다.
- 데이터 저장 방식: Map은 중복을 허용하지 않으면서 각 값을 key-value 쌍으로 저장할 수 있어, 값에 대한 추가적인 정보를 저장하기에 용이하다. 또한 계수 정렬에서는 해당 index에 1을 더해줬다면, Map에서는 해당하는 key에 해당하는 value값에 1을 더해준다는 부분에서 계수 정렬과 같은 개념으로 문제를 해결한다. 따라서 Map은 계수 정렬의 성능을 떨어뜨리지 않으면서도 중복을 피하고 값을 관리할 수 있는 장점을 제공한다.
- 빠른 검색 속도: Map으로 이를 구현하기 위해서는 동적으로 요소를 생성하고, 해당하는 값을 탐색해서 값을 업데이트 해야한다. Map은 내부적으로 해시맵 또는 트리 등의 구조를 사용하여 검색 속도를 최적화하기 때문에 사용하기에 적절하다.
위의 문제에 Map을 적용한 코드는 다음과 같다. 물론 해당 문제에서는 메모리 제한이 8MB라서 메모리 초과가 나겠지만, 메모리 제한에 걸리지 않으면서 범위가 정해져있지 않은 문제라면 Map으로 풀 수 있겠다고 생각했다.
import sys
count_map = {}
n = int(sys.stdin.readline())
for _ in range(n):
num = int(sys.stdin.readline())
if num in count_map:
count_map[num] += 1
else:
count_map[num] = 1
sorted_data = []
for key, count in sorted(count_map.items()):
sorted_data += [key] * count
for num in sorted_data:
print(num)같은 문제여도 조건에 따라 써야하는 알고리즘이 달라지며, 해당 알고리즘을 구현하기 위해 어떤 자료구조를 선택하느냐가 달라지며 구현 방식이 달라진다. 심지어 같은 자료구조를 사용해도 어떻게 구현하느냐에 따라 시간복잡도는 달라진다.
코드를 작성하기 전에 문제의 조건을 살피고, 어떤 자료구조를 선택해서 어떻게 알고리즘을 구현할 것인지 설계하는 단계가 매우 중요하다는 것을 느낄 수 있었다.
