[코드잇][위클리페이퍼][3주차] 알고리즘과 자료구조

아래는 3주차 위클리페이퍼 주제이다.

• HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유를 설명해주세요.
• O(n)과 O(log n)의 성능 차이를 실생활 예시를 들어 설명하고, 데이터의 크기가 1백만 개일 때 각각 대략 몇 번의 연산이 필요한지 비교해주세요.

 

먼저 HashSet 자료형을 설명하기에 앞서 Set의 특징에 대해서 설명한다.

Set은 영어 그대로 집합을 말하며 집합의 수학적 특징을 그대로 가져간다. 그래서 순서가 없으며, 원소의 중복이 허용되지 않는다.

그렇다면 자바는 내부적으로 어떻게 Set을 구현할까? 자바에는 HashSet과 TreeSet이라는 두 Set가 있다.

이 두 자료구조의 차이점은 HashSet은 내부적으로 해쉬 테이블을 사용하는 HashMap 객체이고, TreeSet은 레드-블랙 트리를 사용한다.

위 이미지는 오라클 공식 문서의 HashSet 설명을 일부 발췌한 것이다.

 

HashSet의 내부 동작 방식은 HashMap 객체와 동일한 것이다. 내부적으로 hashcode, equals를 사용하여 해쉬 테이블을 작성한다. 먼저 저장하려는 요소의 hashcode를 호출하여 해시 값을 비교하고, 만약 hashcode가 같다면 equals를 호출하여 논리적으로 동일한 객체인지 비교한다. 이 두 단계가 모두 같다고 판단되면 HashSet은 해당 요소를 저장하지 않는다.

 

HashSet은 위 메커니즘으로 중복 제거를 하며, 요소를 조회할 때는 해쉬 테이블을 사용하므로 O(1)의 시간복잡도를 가진다.

 

그런데 여기서 개발자라면 한가지 의문점이 들 것이다. 기본 타입은 쉽게 비교가 되는데 참조 타입 객체는 같은 객체라도 주소값이 다르다면 equals가 다른 객체라고 판단을 하는데 그렇다면 중복 제거가 안 되는거 아닌가? 라는 의문점이다.

 

이 의문점은 실제로도 매우 정확하다. 참조 타입 중 String타입은 hashcode와 equals가 이미 오버라이딩 되어 있어서 String타입은 문자열 값에 따라 hashcode의 값이 결정된다. 그러나 개발자가 직접 작성한 참조 객체라면 직접 hashcode나 equals를 재정의해야 한다.

 

만약 Person 클래스를 만들었다면 Person 객체의 유일성을 보장할 수 있는 필드를 equals로 비교하도록 한다. 주민등록번호나 객체에서 생성한 시퀀스 번호를 사용할 수 있을 것이다. 또는 2개 이상의 필드를 사용해서 유일성이 보장된다면 그렇게 해도 된다.

---

다음으로는 O(n)과 O(log n)의 성능 차이를 정말 이해하기 쉬운 예시로 설명하려고 한다.

친구랑 내가 1부터 100까지 생각한 숫자 맞추기 게임을 하고 있다고 가정하자.

 

이 때, 친구는 첫 번째 게임에서는 오직 맞췄는지 틀렸는지에 대한 정보만 준다. 그렇다면 나는 1부터 100까지 모든 숫자를 맞춰야 할 수 밖에 없다. 운이 없다면 숫자 100개를 전부 말해야 맞출 수 있을 것이다. 그러므로 시간 복잡도는 O(n)이 된다.

 

다음 게임에서 친구는 너무 답답했는지 내가 말한 숫자가 자신이 생각한 숫자보다 큰지 작은지를 알려준다. 내가 50을 말하고 친구가 "50보다 작아"라고 말한다면 51부터 100은 더 이상 생각 할 필요가 없게 된다. 그 다음에 25를 말하고 친구가 "25보다 커" 라고 말한다면 1부터 24까지는 당연히 아니게 된다. 이 흐름을 자세히 생각해보면 100개의 숫자가 50개로, 50개의 숫자가 25개로 계속 절반씩 줄어든다. 우리는 아무리 운이 없다고 해도 25개 다음엔 12개, 12개 다음엔 6개, 6개 다음 3개, 3개 다음 1개가 남게 된다. 즉 7번 만에 무조건 100개의 숫자 중 하나의 숫자를 찾을 수 있는 것이다. 이를 이진 탐색이라고 하며 이진 탐색을 할 경우 O(log n)의 시간 복잡도를 가지게 된다.

 

지금은 N이 100이라서 100과 7로 큰 차이가 안나보이지만, 데이터의 개수가 100만개라면?
O(N)은 말 그대로 100만 번의 연산이 필요하다면, O(log N)은 단 20번의 연산이 필요하다.

 

아래는 대체적으로 자주 사용되는 시간복잡도를 그래프로 나타낸 것이다.

 

 

이상으로 이번 주 위클리페이퍼에 대한 포스팅을 마친다.