위클리페이퍼03: 알고리즘과 자료 구조
Q1. HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유를 설명해주세요.
Q1-1. 답변
1. HashSet
해시 테이블을 이용하여 데이터를 저장하는 구조로, Set 특징을 가지고 있어 중복된 값이 저장되지 않는다.
인덱스가 아닌 중복되지 않은 유일한 값인 key를 이용해 데이터를 저장하며 접근한다.
2. 내부 동작 방식
HashSet 클래스의 내부 코드를 보면 HashMap을 사용하여 구현이 되어 있어, 데이터 저장에 key-value 쌍을 이용한다. 하지만 HashMap과는 달리 key에 데이터를 저장하고, 더미 객체를 value에 저장한다.
3. 중복 제거 메커니즘
(1) 객체 저장 시 hashcode()메서드를 호출해 해시값을 생성
(2) 이렇게 생성된 해시값을 기반으로 저장할 위치를 결정
(3) 저장할 위치에 이미 데이터가 있다면 equals()메소드로 같은 데이터인지 확인
(4) hashcode()와 equals() 메소드의 결과가 모두 같은 경우에만 중복으로 판단하여 추가하지 않음
4. 효율적으로 중복 체크가 가능한 이유
순회하며 비교하는 대신 해시함수인 hashcode()로 생성된 해시값을 기반으로 결정된 저장 위치에 바로 찾아가 데이터를 저장하거나 비교할 수 있어 O(1)의 시간 복잡도만을 가지기 때문에 효율적으로 중복 체크가 가능한다.
Q1-2. 정리
HashSet은 내부적으로 HashMap을 사용하여 구현되어 있으며, 입력된 요소를 키로 사용하고 더미 객체를 값으로 저장합니다. HashSet의 중복 제거 메커니즘은 다음과 같이 작동합니다:
- 객체가 추가될 때 먼저 객체의 hashCode() 메서드를 호출하여 해시값을 계산합니다.
- 이 해시값을 기반으로 저장할 버킷 위치를 결정합니다.
- 같은 버킷에 이미 요소가 있다면 equals() 메서드를 사용하여 객체 간의 동등성을 비교합니다.
- hashCode()와 equals() 모두 같은 경우에만 중복으로 판단하여 추가를 하지 않습니다.
이러한 방식이 효율적인 이유는 해시 기반의 검색이 O(1)의 시간 복잡도를 가지기 때문입니다. 모든 요소를 순회하면서 비교하는 대신, 해시값을 통해 즉시 비교할 위치를 찾아갈 수 있어 매우 빠른 중복 체크가 가능합니다.
Q2. O(n)과 O(log n)의 성능 차이를 실생활 예시를 들어 설명하고, 데이터의 크기가 1백만 개일 때 각각 대략 몇 번의 연산이 필요한지 비교해주세요.
Q2-1. 답변
1. O(n)
첫 번째부터 하나씩 차례대로 찾을 때의 시간 복잡도
데이터의 크기가 100만 개일 때, 평균적으로 50만 번의 연산이 필요할 것
2. O(log n)
중간을 기준으로 내가 찾는 값이 앞에 있는지 뒤에 있는지 확인하여 범위를 절반씩 좁혀나갈 때의 시간 복잡도
데이터의 크기가 100만 개일 때, 대략적으로 19~20번의 연산이 필요할 것
Q2-2. 정리
O(n)과 O(log n)의 차이는 전화번호부에서 이름을 찾는 두 가지 방법으로 설명할 수 있습니다.
O(n): 첫 페이지부터 한 페이지씩 순차적으로 찾는 방법
- 1백만 개의 데이터에서는 평균적으로 500,000번의 비교가 필요
O(log n): 중간을 펴서 찾는 이름이 앞에 있는지 뒤에 있는지 판단하여 범위를 절반씩 좁혀가는 방법
- 1백만 개의 데이터에서는 log(1,000,000) ⇒ 20번의 비교만 필요 (2^20 = 1,048,576으로 약 1백만)
이처럼 데이터의 크기가 커질수록 O(n)과 O(log n)의 성능 차이는 매우 커지게 됩니다.
Leave a comment