오늘은 자료구조 설계에 대한 흥미로운 문제를 가져왔습니다. 겉으로 봤을 때는 해당 문제가 쉽게 풀릴 것입니다. 즉, O(1)이 아니고서는 문제 구현이 쉬울 것 입니다. 하지만, 이 문제에서는 O(1)의 시간 복잡도로 요소를 삽입, 삭제 및 무작위로 가져오는 자료 구조를 구현하는 것이 핵심입니다.
저는 이 문제를 처음 시도했을 때, 파이썬의 'set'자료구조를 사용했습니다. 'set'을 사용하면 삽입과 삭제는 평균적으로 O(1)의 시간 복잡도를 가지기 때문이죠.(자세한 이유는 이 링크를 참조하세요)
하지만, 문제는 getRandom() 메소드에 있었습니다. rand()와 같은 함수는 해시 집합에서 사용할 수 없기 때문에, 'set'을 'list'로 변환하는 과정이 필요합니다. 이 때, O(n) 시간이 걸리므로, O(1) 요구 사항을 충족시키지 못합니다.
처음 제가 풀이한 코드입니다.
import random
class RandomizedSet(object):
def __init__(self):
self.sets = set()
def insert(self, val):
"""
:type val: int
:rtype: bool
"""
if val in self.sets:
return False
self.sets.add(val)
return True
def remove(self, val):
"""
:type val: int
:rtype: bool
"""
if val in self.sets:
self.sets.remove(val)
return True
return False
def getRandom(self):
"""
:rtype: int
"""
if len(self.sets) == 0:
return False
return random.choice(list(self.sets))
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
정답 처리가 됐지만, 이 문제를 제대로 푼 방법이 아닙니다. 문제 제목에서 조차 O(1) 으로 구현하라고 했기 때문이죠.
실제로, 어느 한 유저분께서는 이 문제가 자신의 deshaw 인터뷰에서 나왔다고 말했습니다. deshaw는 뉴욕시에 본사를 둔 다국적 투자 관리 회사로 대표적인 퀀트 헤지펀드입니다.
아마, 인터뷰에서도 O(1)의 알고리즘으로 어떻게 삽입, 삭제, 랜덤추출을 할 수 있을까를 물어봤을 것입니다.
그럼, 대체 O(1)의 시간복잡도로 어떻게 삽입, 삭제, 랜덤추출을 동시에 구현할 수 있을까요? Discussion에서 다른 유저의 말을 통해 힌트를 얻을 수 있습니다.
해당 유저는 O(1) 랜덤 액세스에 대한 알고리즘 전략을 말하고 있습니다.
"O(1) 랜덤 액세스의 필요성은 이 문제를 약간 복잡하게 만듭니다. O(1) 삽입 및 제거를 위한 해시맵과 O(1) 랜덤 액세스를 위한 정수 배열이 필요합니다. 해시맵 항목에는 배열의 위치를 나타내는 각각의 값을 가진 인덱스가 포함되어야 합니다.
배열에서 O(1) 시간에 요소를 제거하기 위한 한 가지 방법은 모든 요소를 이동시키는 대신 배열의 마지막 요소를 빈 공간(제거하려는 요소의 위치)으로 이동시키는 것입니다. 이 특정 값의 새로운 인덱스를 저장하는 것을 잊지 마세요."
.
..
...
이게 도대체 무슨 말일까요? 여기서 언급된 주요 개념들을 하나씩 살펴보겠습니다.
1. O(1) 무작위 접근의 필요성
→ 문제는 무작위로 요소를 선택하는 작업이 상수 시간(O(1)) 내에 이뤄져야 한다고 요구합니다. 이것은 곧, 리스트나 배열과 같은 인덱스 기반의 데이터 구조가 필요함을 의미합니다. (변환하는 순간 O(n)이 되어버리기 때문에 애초에 리스트를 필요로 하는 것이겠죠)
2. 해시맵과 정수 리스트의 사용
→ 두 가지 주요 데이터 구조가 언급되었습니다. 해시맵(또는 딕셔너리)은 삽입과 삭제를 O(1) 시간에 할 수 있게 해주며, 정수 배열(또는 리스트)은 O(1) 무작위 접근을 가능하게 합니다.
3. 해시맵의 엔트리와 인덱스
→ 해시맵에서 각 값은 배열 내에서의 위치를 나타내는 인덱스와 함께 저장되어야 합니다. 이렇게 하면, 어떤 요소가 배열의 어느 위치에 있는지 즉시 알 수 있게 됩니다.
4. 리스트에서의 O(1) 삭제를 위한 전략
→ 리스트에서 요소를 삭제할 때, 모든 요소를 이동시키는 대신, 배열의 마지막 요소를 삭제하려는 요소가 있던 위치로 이동시키는 방법이 언급되었습니다. 이렇게 하면, 삭제 연산도 O(1) 시간에 가능해집니다.
5. 새로운 인덱스 저장
→ 배열의 마지막 요소를 새 위치로 이동시킨 후, 그 요소에 대한 새로운 인덱스를 해시맵에 업데이트해야 합니다. 이렇게 해야 해시맵이 항상 정확한 요소의 위치를 반영하게 됩니다.
즉, 이 문제를 효율적으로 해결하기 위해서는 'list' 와 'dictionary'를 결합한 방식을 사용해야 합니다. 이 방법은 모든 메소드에 대해 O(1)의 시간 복잡도를 유지합니다. 'dictionary'는 요소와 그 인덱스를 매핑하고, 'list'에는 실제 요소를 저장합니다. 이렇게 되면, set()을 사용하지 않고도 O(1)의 연산으로 요소 삭제를 할 수 있고, 'getRandom' 메소드도 O(1)로 개선됩니다.
이런 개념을 가지고 코드를 작성해보면 아래와 같습니다. 코드를 통해 살펴보겠습니다.
import random
class RandomizedSet(object):
def __init__(self):
# 데이터 저장을 위한 딕셔너리와 리스트 초기화
self.data_map = {}
self.data = []
def insert(self, val):
# val이 이미 존재하는 경우, 삽입을 거부
if val in self.data_map:
return False
# 딕셔너리에 val 과 해당 인덱스 매핑 저장(리스트의 길이는 새요소의 인덱스와 동일함)
self.data_map[val] = len(self.data)
# 리스트에 val 추가
self.data.append(val)
return True
def remove(self, val):
# val이 존재하지 않는 경우, 삭제 거부
if val not in self.data_map:
return False
# '삭제할 요소의 인덱스'와 '리스트의 마지막 요소' 찾기
val_index, last_element = self.data_map[val], self.data[-1]
# 리스트에서 val 과 마지막 요소 교환, 해시맵도 업데이트
self.data[val_index] = last_element
self.data_map[last_element] = val_index
# 리스트에서 마지막 요소(이제 val이 됨) 제거
self.data.pop()
# 딕셔너리에서 val 제거
self.data_map.pop(val)
return True
def getRandom(self):
# 리스트에서 무작위 요소 반환
return random.choice(self.data)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
먼저, __init__ 함수입니다.
self.data_map 은 딕셔너리로 초기화되며, 값과 해당 값의 인덱스를 매핑합니다.
self.data 는 리스트로 초기화되며, 실제 값들을 저장합니다.
insert 함수를 살펴보겠습니다.
삽입 메소드는 주어진 'val' 이 이미 'data_map' 에 있는지 확인합니다. 이 확인 과정은 평균적으로 O(1) 입니다.
'val'이 존재하지 않는 경우, 'val' 을 'data' 리스트에 추가하고, 'data_map'에 'val'과 그 인덱스를 매핑하는데, 이 때 인덱스는 리스트의 길이와 동일합니다. 끝에만 추가를 하기 때문이죠.
삽입이 성공하면 'True'를 반환합니다.
※ 근데 in 연산은 O(n) 아닌가요? 시간복잡도가 어떻게 되나요?
'in' 연산자의 시간 복잡도는 사용하는 데이터 구조에 따라 다릅니다. 파이썬에서 'list'와 'set' 또는 'dictionary'를 사용할 때 in 연산자의 시간 복잡도는 다음과 같습니다
리스트(List): 리스트에서 in 연산은 O(n) 시간 복잡도를 가집니다. 이는 리스트의 각 요소를 순회하며 찾고자 하는 값을 검색해야 하기 때문입니다.
세트(Set) 및 딕셔너리(Dictionary): 집합이나 딕셔너리에서 in 연산은 평균적으로 O(1) 시간 복잡도를 가집니다. 이들은 해시 테이블을 기반으로 하여 구현되어 있으며, 해시 함수를 사용해 데이터를 저장하고 검색합니다. 따라서 대부분의 경우에 데이터의 존재 여부를 상수 시간 내에 확인할 수 있습니다. 그러나 최악의 경우(해시 충돌이 많을 때) 시간 복잡도는 O(n)까지 나빠질 수 있습니다.
따라서 "380. Insert Delete GetRandom O(1)" 해당 문제에서 in 연산을 사용할 때, 해시 기반의 데이터 구조인 세트나 딕셔너리를 사용하면 대부분의 경우 O(1) 시간 복잡도로 데이터의 존재 여부를 확인할 수 있습니다. 반면, 리스트를 사용한다면 이 연산의 시간 복잡도는 O(n)이 됩니다.
가장 중점적으로 봐야 할 부분이 remove 함수입니다.
삭제 메소드는 'val'이 'data_map'에 존재하는지를 우선 확인합니다. 이 과정은 평균적으로 O(1) 입니다.
'val' 이 존재하는 경우, 리스트에서 'val'의 위치와 마지막 요소의 위치를 교환합니다.
이는 'val'을 삭제하고 나머지 요소들의 위치를 갱신하는 데 드는 시간을 절약합니다.
# lastVal takes the val to delete's spot in the list
⬐───────────────┐
[ , val , , last_element ]
⟱
[ , last_element , , last_element ]
교환 후, 'val' 이 있던 위치에 있던 마지막 요소의 새 인덱스를 'data_map'에 업데이트합니다.
# update the index in the map
{
val -> val's index ─────────┐
last_element -> last_element's index ←────┘
}
⟱
{
val -> val's index
last_element -> val's index
}
그 후, 리스트의 마지막 요소를 제거합니다. (이제 'val'이 된 요소 제거)
# Remove val from the list and map
self.data.pop()
[ , last_element , ]
'val' 을 'data_map' 에서도 제거하고, 삭제가 성공하면 'True'를 반환합니다.
self.data_map.pop(val)
{
last_element -> val's index
}
마지막으로, getRandom함수에서는
radom.choice(self.data) 를 사용하여 리스트에서 무작위로 요소를 선택합니다. 이 메소드도 역시 O(1) 시간복잡도를 가집니다.
※ radnom.choice는 왜 O(1)의 시간복잡도를 가지나요?
random.choice 함수가 O(1) 시간 복잡도를 가지는 이유는 이 함수가 리스트에서 요소를 무작위로 선택할 때 내부적으로 무작위 인덱스를 생성하고 해당 인덱스의 요소에 직접 접근하기 때문입니다.
파이썬의 리스트는 배열 기반의 데이터 구조입니다. 배열에서는 각 요소가 연속적인 메모리 위치에 저장되므로, 특정 인덱스의 요소에 직접 접근하는 것은 상수 시간(O(1))이 걸립니다.
random.choice는 다음과 같은 과정을 거칩니다:
1. 리스트의 길이에 해당하는 범위 내에서 무작위 인덱스를 선택합니다. 이 과정은 상수 시간이 걸립니다.
2. 선택된 무작위 인덱스를 사용하여 리스트에서 해당 요소를 직접 가져옵니다. 리스트의 특정 인덱스에 접근하는 것은 O(1) 연산입니다.
따라서, random.choice는 전체 리스트를 순회할 필요가 없으며, 단순히 무작위 인덱스를 생성하고 그 인덱스에 해당하는 요소에 직접 접근하기 때문에 O(1) 시간 복잡도를 가집니다.
효율적인 알고리즘을 통해, 전체적으로 O(1) 의 시간복잡도로 해당 문제를 풀 수 있습니다.
이상으로 정렬, 해시와 리스트를 이용한 O(1) 연산 자료구조와 관련한 380. Insert Delete GetRandom O(1) 문제를 정리해봤습니다.
이 문제를 통해 우리는 올바른 데이터 구조의 선택이 알고리즘의 성능에 얼마나 큰 영향을 미치는지 확인할 수 있습니다. 효율적인 솔루션은 문제의 요구 사항을 정확히 이해하고 이에 맞는 데이터 구조를 선택하는 데서 시작됩니다.
이러한 최적화 문제를 풀 때는 단순히 알고리즘을 작성하는 것뿐만 아니라, 왜 그런 알고리즘이 필요한지, 다른 접근 방식과 어떻게 다른지에 대해서도 생각해보는 것이 중요합니다. 결국, 효율적인 코딩은 문제를 깊이 있게 이해하고 최적의 해결책을 찾는 과정에서 시작됩니다.
연관된 문제로 조금 더 어려운 버전인 381. Insert Delete GetRandom O(1) - Duplicates allowed 가 있으니 풀어보시면 좋습니다.
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com