꿈 꾸는 누렁이

지난 이야기..

문제점

뭐 위와 같은 문제들이 있다. 위의 문제의 전제는 등록되는 수는 100명도 안되고, 거의 그대로지만 번호만 오지게 큰 스케일로 변환되는 경우이다. 

해결 아이디어

그러면 어떻게 하면 될까? 

큰 인덱스 키 값의 크기를 줄이면 된다!

<인덱스를 축소 변환하는 과정>

1. 어차피 등록되는 인원은 100명이 안될 것이기 때문에 20171300 ~ 20171399 라고 범위를 어림 잡는다 
2. 그러면 말이 20171300 부터 20171399까지 이지 결국엔 0부터 99까지라고 봐도 문제가 없다.
3. 그렇다면 인덱스를 대입하기 전에 20171300이 오면 무조건 0으로 변환해주고, 20171344가 오면 무조건 44로 변환해주며, 20171399가 오면 무조건 99로 변환해주어 인덱스에 대입되도록 하면 어떨까?
4. 등록번호 % 100 을 한 결과라면 무조건적으로 위의 결과를 얻는다.
5. 그렇다면 user acc[100] 을 그대로 넣고 acc[uid%100] 으로 접근하면 배열의 크기를 비정상적으로 늘리는 고민을 해볼 필요도 없게되는 것이다.

이러한 과정에서 축소 변환해주는 역할을 하는 것을 해쉬(hash)라고 하며, 해당 역할을 하는 함수를 해쉬 함수라고 한다.

해쉬 함수는 다음과 같다. 겁나 간단하다.

이러한 해쉬 함수는 위에서 밑줄 친 것처럼 다양한 값의 형태에 따라 달라진다. 해쉬되어야 할 키 값의 상황? 문맥? 에 따라서 적용되는 해쉬 함수의 내용이 달라지고, 정답이 없다는 뜻이다.

적용된 코드 분석

등록을 할 때에 hash 함수를 이용하며,

값을 꺼낼 때에도 hash 함수를 이용하여 인덱스를 축소 변환하여 인덱싱한다.

전체 코드 및 실행 결과

그런데 또 문제점

짜증나게 또 문제가 발생하는 것이다.. 이번엔 등록해야하는 수가 갑자기 늘어나 버려서 다음과 같은 현상이 발생하는 것이다. 

1. 한 200명~300명 정도 난다.
2. 그래서 배열의 길이를 넉넉하게 user acc[400]; 정도로 주었다.
-> 이 방법 또한 썩 마음에 들지 않는다. 왜냐하면 등록 수가 늘어날때마다 계속 변경을 해줘야 하기 때문이다.
3. 그런데 문제는 여기서부터이다. 20171350과 20171450의 해쉬 결과는 50으로 같다.
-> 왜냐하면 100으로 나눈 나머지이기 때문에!(직접 나눠보라)
4. 20171350 등록 번호인 사람과 20171450 등록번호인 사람의 해쉬 결과가 50으로 같으므로 둘다 acc[50]에 정보가 등록될 것이다.. 그러니까 먼저 저장되는 값은 손실 된다는 의미이다. 원래 기대 결과는 20171350은 [50]에 20171450은 [150] 에 저장되는 것을 기대했는데 말이다.

지금 두 가지 문제가 발생하였다.

첫 번째는 문제는 등록되는 수가 넘쳐날 때마다 테이블의 크기를 갱신해야하는 상황이 발생한다.

두 번째는 문제는 분명히 다른 등록번호임에도 불구하고, 해쉬된 결과로 같은 인덱싱 번호가 나왔다. 

먼저, 두 번째 문제와 같이 같은 해쉬 결과가 나오는 것을 충돌(Collision)이라고 한다. 이러한 충돌을 막으려면 어떻게 해야할까? 해쉬 함수를 기가 막히게 잘 만들어야 한다. 해쉬 함수는 해쉬하려고 넘어오는 키 값의 범위나 종류나 형태, 양상에 따라 달라질 수 있기 때문에 매우 주관적이며, 답이 없다. 

A회사에서 만든 해쉬 함수가 기가 막히게 성능이 잘 나오다가도 B회사에서 A회사의 해쉬 함수를 쓰면 동작이 잘 안될 수도 있다. 그렇지만 최대한 공통으로 적용할 수 있는 여러 알고리즘? 들이 존재한다.

자릿수 선택, 폴딩 방법, 선형 조사법, 이차 조사법, 이중 해쉬, 체이닝 ... 등

이렇게 여러 방법들이 존재하지만 이 방법들의 공통점은 해쉬 해야할 키 값을 어떻게 변환해야 충돌이 덜 일어나는가에서부터 시작하는 방법들이다.

가장 좋은 해쉬 방법을 만드는 것은 키 값의 부분을 활용하여 해쉬된 키 값을 만들 것이 아니라, 키 값의 전체를 활용하여 해쉬된 키 값을 만들어야 한다는 것이다.

위의 예제에서도 키 값의 마지막 두 자리 수만 가지고 장난질 했기 때문에 문제가 되었다. 키 전체를 활용할수록 콜리전이 발생할 확률이 매우 낮아진다.

첫 번째 문제는 해쉬 함수의 구현에 따라 달라진다. 해쉬 함수를 통해 변환되는 해쉬된 키 값의 범위를 어떻게 정하느냐에 따라 적절한 할당 크기를 정할 수 있기 때문이다.

테이블과 해쉬 등은 성능은 좋지만 이러한 충돌(collision) 문제로 인해, 그리고 키를 이용하여 제어해야하는 곳에서만 주로 사용해야하기 때문에 사용되는 곳이 제한된다. 

테이블과 해쉬를 살펴봤는데 해쉬 테이블은 기본 동작 원리나 문제점 그리고 적용 가능한 작업의 특징 정도로만 공부하고 넘어가는게 좋을 것 같다.

지난 포스팅에서 순회까지 끝냈다. 이제 탐색과 삭제가 남았다.

바로 이어서 탐색을 보자.

이진 탐색 트리의 탐색

이진 탐색 트리에서 탐색과 순회는 다르다. 순회는 모든 노드를 방문하는 것을 이야기하지만, 탐색은 가장 효율적이고 적은 깊이로 노드를 방문하여 원하는 값을 찾는 것인가이다.

1번 : 찾으려고 하는 5 값이 루트 노드의 10 값보다 작으니, 왼쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
2번 : 찾으려고 하는 5 값이 노드의 4 값보다 크니, 오른쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
그 이후 발견.

위와 같이 서브 트리를 대상으로 옮기고, 또 서브 트리의 서브 트리로 대상을 옮기고 하는 과정에서 봤을 때, 재귀로 해결할 수 있다! 탐색 또한 마찬가지로 순회처럼 재귀를 이용하여 문제를 해결해갈 것이다.

코드를 보면 다음과 같다.

매개 변수인 sub_root에는 서브 트리의 루트 노드가 항상 들어온다. 이 서브 트리의 루트 노드와 값을 비교하여 같으면 탐색 완료, 작으면 다시 왼쪽 서브 트리 재탐색을 위한 재귀 호출, 크면 다시 오른쪽 서브 트리 재탐색을 위한 재귀 호출 순서로 조건 및 연산 수행을 진행하면 된다.

이진 탐색 트리의 삭제

아.. 삭제는 ㅋㅋ 여러 유형으로 나뉜다 쉽지가 않다. 왜냐하면? 자식이 없는 단말 노드를 삭제할 경우, 그냥 해당 단말 노드만 제거하면 끝나는 문제이지만 자식 노드가 존재하는 노드를 삭제할 경우 문제가 커진다. 

일단은 그림 형태로 유형 별로 확인한 뒤 코드를 보자.

삭제할 타겟이 단말(리프) 노드인 경우

간단하다. 그냥 끝에 있는 노드이므로 바로 삭제를 하면 되는데, 다만! 삭제할 타겟의 부모의 링크(left or right)가 NULL을 가리키도록 설정해주면 된다. 다음의 그림과 같이 말이다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 하나만 존재하는 경우

이 경우 또한 간단하다. 아래의 그림과 같은 경우인데 삭제할 타겟의 부모의 링크와 삭제할 타겟이 가지고 있는 하나의 자식 노드를 연결해주면 된다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 두 개 모두 존재하는 경우

이 경우는 좀 답이 없다. 물론 설명하기 답이 없다는 것이다. ㅋㅋ 좀만 생각해보면 쉽다! 

먼저, 이전의 노드 삭제 유형들처럼 타겟을 삭제하고 부모와 자식을 연결해주는 등의 간단한 방법으로 끝날 문제가 아니다.

삭제할 타겟 노드가 자식 노드를 두 마리나(?) 가지고 있는 바람에 왼쪽 자식 노드의 서브 트리와 오른쪽 자식 노드의 서브 트리를 만족할 수 있는 값으로 대체 노드 선별해야한다. 

아 그러면? 삭제할 타겟 노드의 자식들 중 하나로 선택하면 되는 것 아니냐?

응 안된다. 왜냐하면 그림에 자세히 설명을 해 놓았다. 아래의 그림에서 두 번째 케이스에 해당하는 경우다. 혼돈하지 말아야 한다.

그러면 자식 중에 아무나 하나를 그냥 올리면 안되면 어떻게 올려야 하나?

왼쪽 서브 트리에서 가장 큰 값을 갖는 노드를 대체 노드로 선별하거나,
오른쪽 서브 트리에서 가장 작은 값을 갖는 노드를 대체 노드로 선별해야한다.

두 경우 중 하나를 선택해야 한다. 그 선택은 뭐 개발자 마음이고, 코드 작성자 마음이다. 선택했다면 다음과 같은 순서를 떠올릴 수 있다.

1. 대체 노드의 링크들을 타겟 노드의 링크로 전부 동기화 한다.
2. 대체 노드의 부모의 링크를 적절한 포인터(노드 혹은 NULL)로 변경한다.
3. 타겟 노드를 제거한다.

이러한 순서를 떠올렸는데 여기서 약간의 꼼수(?)를 쓴다고 하며, 지혜를 발휘한다고 읽는다. 뭐냐하면, 대체 노드를 굳이 드러내어 타겟이 있던 자리로 옮겨서 링크를 수정할게 아니라, 타겟 노드의 값만 대체 노드의 값으로 바꿔준다면 링크들을 굳이 변경할 필요가 없기 때문이다. 

1번 연산이 굉장히 부담 그 자체이다. 헤깔려죽겠는데.. 2번과 3번은 어차피 대체 노드에 대해서 해야할 작업이기 때문에 그렇다 치더라도, 1번 연산은 안 해도 될 일을 하는 것과 다름이 없다! ㅋㅋ

그래서 뭐 어찌 되었든 간에 왼쪽/오른쪽 중에 선택을 했다면, 다음 그림으로 그 선택 이후의 과정을 설명한다. 번호 순서대로 색깔과 연관 지어서 차근 차근 읽으면 된다.

이에 따른 코드는 아래와 같으며, 타겟 노드를 루트 노드로 한 서브 트리의 오른쪽 자식의 서브 트리 군에서 가장 작은 값을 선택하여 타겟 노드의 자리에 대체하기로 하였다.

하.. 이로써 삭제까지 끝이다.

일요일에 정말 집중도 안되고, 포스팅을 하면 할수록 코드 작성 때는 떠 올리지도 않았던 세세한 부분까지 의구심이 들어서 시간이 두배, 세배 드는 것 같다.

뭐 다음 시간에는 코드와 실행 결과만 올린다.