배열, 링크드리스트, 해쉬테이블 비교해 주세요
배열은 모든 데이터를 연속된 메모리에 저장된다. 데이터가 저장될 메모리가 물리적으로 연속되어있기 때문에, 인덱스를 통한 데이터접근이 O(1)이다. 데이터수가 아무리 많더라도, 인덱스만 알면 산술적으로 메모리주소를 계산할 수 있기 때문이다.
이에 반해, 링크드리스트는 데이터의 인덱스접근이 O(N)이다. 데이터를 추가할 때마다 메모리가 동적할당되어, 해당 메모리주소를 알기 위해선 선형적으로 처음 데이터부터 해당 데이터까지 조회해야 하기 때문이다. 그러나 배열과는 다르게 처음 할당시에 미리 사용할 메모리영역을 예약할 필요가 없다. 동적으로 필요한 만큼만 메모리를 할당해 사용할 수 있다.
해쉬테이블은 해쉬함수를 이용해 매우 넓은 범위의 데이터를 그보다는 작은 배열공간에 저장하게 된다. 해쉬펑션이란 키값을 배열의 인덱스로 사상하는 역할을 한다. 따라서 데이터수가 아무리 많더라도 이 연산자체는 O(1)에 끝나고, 따라서 일반적인 조회연산은 O(1)에 가능하다. 그러나 해쉬테이블은 매우 넓은 범위의 데이터를 그보다 작은 메모리영역에 저장하는 구조이기 때문에 필연적으로 데이터들이 같은 메모리에 사상되는 현상인 해시충돌이 발생할 수 밖에 없고, 이 경우 조회성능이 악화된다.
해시 충돌이 뭔가요?
해쉬테이블은 데이터를 내부 배열에 저장하는데, 이때 배열의 인덱스를 해시 값이라고 한다. 서로 다른 두개의 키 값이 해시함수에의해 같은 해시값으로 변환될 때 해시충돌이 일어났다고 한다.
해쉬컬리전이 일어나면 처리하는 방식 각각설명해주고 비교해주세요
두가지 방식이 있다. separate chaining 방식과 open addressing 방식이다.
separate chaining 방식은 내부배열의 각 칸이 링크드리스트를 가리키도록 하여, 해시충돌이 발생하면 선형적으로 해당 버킷에 데이터를 저장하는 방식을 말한다. 하지만, 소수의 버킷에 데이터가 집중될 경우 해당 버킷의 데이터를 조회할 때는 O(N)과 가까운 시간소요를 피할 수 없게된다. 이러한 문제를 해결하기 위해, jdk1.8 부터는 하나의 버킷에 데이터가 8개 이상이 링크드리스트로 연결될 경우, 트리구조로 데이터를 저장한다. 데이터가 집중된 버킷에서 특정데이터를 찾는다 하더라도 log(N)에 데이터를 조회할 수 있도록 하기 위해서이다
다른 방식은 open addressing 방식이다. 해시충돌이 발생했을 경우, 빈 버킷을 찾을때까지 걔속해서 다음 인덱스를 찾는 방식이다. 이 방식에서 데이터를 삭제하게되면 다음에 있는 데이터를 찾는데 문제가 생길 수 있기 때문에, 항목이 여기서 제거되었음을 나타내는 표시를 하게 된다. 데이터 갯수가 적을 경우, open addressing 방식이 더 빠르다. 연속된 메모리 안에서 인덱스를 조금씩 늘려가며 조회하기 때문에, 동적할당이 많은 separate chaining 보다 캐쉬데이터를 더 많이 이용할 수 있다.
자바에서는 자바8을 기준으로 separate chaining을 사용하고 있다.
네이버 D2 참고자료
자바8에서는 데이터의 개수가 많아지면 Separate Chaining에서 링크드 리스트 대신 트리를 사용한다. 같은 버켓에 6개까지는 링크드 리스트를 사용하지만 8개가 되면 트리로 변경한다. 8과 6으로 차이를 둔 것은 만약 차이가 1이라면 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일을 하기 때문이다. 이때 사용하는 트리는 Red-Black Tree이다.
해시 버킷의 기본값은 16이고 임계점에 이르면 두배씩 늘린다. 최대 개수는 2^30개이다. 해시 버킷 크기를 두 배로 확장하는 임계점을 load factor라고 하는데 0.75이다.
삽입연산이 O(N)이 되는 구체적인 상황을 말씀해주세요
separate chaining 의 경우, 하나의 모든 키값이 하나의 버킷에 해시충돌이 발생했을 경우이다. 이런 경우엔 해당 버킷에서 링크드리스트 조회가 발생하게되고 따라서 O(N)이다.
openaddressing 의 경우 또한 마찬가지다. 하나의 버킷에 해시충돌이 발생하면 해당 버킷에 인접한 이후의 버킷들에 차례차례로 저장된다. 이 경우 조회를 하게되면 순차적으로 버킷들을 조회해가며 찾기 때문에 O(N)이 발생한다.
머지소트와 퀵소트를 비교해주세요
[퀵소트 설명]
퀵소트는 2 단계로 이루어져 있다.
첫번째로, 정렬범위에서 피벗을 정해서 피벗 왼쪽엔 피벗보다 작은 숫자들을, 오른쪽엔 큰 숫자들을 배치시킨다. 이때의 총 연산횟수는 N번이다.
두번째로, 각각의 범위에 재귀적으로 다시 첫번째 단계를 적용한다.
이때, 동일한 순환호출단계의 모든 데이터범위에 첫번째 단계를 적용할때, 모든 비교연산횟수를 더하더라도 N번이다.
따라서 피벗을 통해 최대한 정렬범위를 반씩 나눠 순환호출의 깊이를 작게 하는것이 중요하다.
피벗을 계속해서 정렬범위의 중앙데이터로 정한다면, logN번만에 모든 정렬범위를 1로 만들 수 있고, 각각의 순환호출 단계의 총연산이 N이기 때문에, 정렬성능은 NlogN이다.
[머지소트 설명]
머지소트는 데이터의 중앙을 기준으로 데이터를 반으로 나눈다.
범위가 1이 될 때까지 재귀적으로 반복된다.
그리고 나눠진 각각의 범위를 합치면서 정렬하게 되는데, 이때 동일한 순환호출단계의 모든연산횟수는 O(N)이다.
머지소트는 데이터를 정확히 반으로 나누기 때문에, 순환호출의 깊이는 logN이 보장되며, 따라서 전체 성능은 NlogN이다.
[퀵소트 머지소트 비교]
퀵소트는 정렬하는데 있어 추가적인 공간을 거의 필요로 하지 않는다. 그러나 머지소트는 데이터범위를 합칠때 임시배열에 해당 데이터를 담아야 하기 때문에 O(N)의 추가데이터가 필요하다.
퀵소트는 또한 캐시지역성을 최대한 활용한다고 알려져 있다.
캐쉬로컬러티 측면에서 두알고리즘을 비교해줄 수 있을까요?
결론: 퀵소트는 메모리 조회가 넓은 범위로 이루어지지 않는다. 재귀적으로 정렬을 실행하지만, 순차적인 범위를 정렬한다. 하지만 머지소트는 메모리조회가 처음과 끝을 계속해서 반복하며 오간다. 따라서 캐시지역성을 활용하는 것이 퀵소트보다 힘들다. 이는 빅오노테이션에서 상수 (A*NlogN + B) 에서 A와 B 부분등의 상수값을 증가시키는 요인으로 작용하고, 따라서 평균적으로 퀵소트보다 성능이 좋지 않다고 알려져 있다.
밸런스트트리가 뭐고 왜 중요할까요?
binary search tree에서의 조회/삽입/삭제 연산에서의 세부연산횟수는 트리의 높이에 비례한다. 따라서, 트리의 높이가 최대한 짧아야 자료구조의 성능이 좋아진다. 트리의 높이를 최대한 낮게하기 위해선 트리가 치우쳐져 있으면 안되고 좌우 균형이 맞도록 balanced 되어 있어야 한다. 이러한 균형을 유지하는 알고리즘이 적용된 트리가 AVL트리와 Red Black 트리이다.
레드블랙트리에 대해서 설명해주세요
느슨한 밸런스 트리라고 볼 수 있다. 모든 루트에서 리프까지노드가 블랙노드 수가 같아야 하는 특성이 있고, 레드노드가 연속해서 위치하지 못한다는 특성이 있다. 이 두 특성의 조합으로 인해 가장 짧은 리프노드까지의 길이가, 가장 긴 리프노드까지의 길이와 2배이상차이날 수 없다는 특성을 만족하게 된다.
레드블랙트리와 avl 트리의 차이점에 대해서 말씀해주세요
AVL 트리와 레드블랙트리 모두 밸런스드 트리이므로, 삽입조회삭제등의 연산이 logN에 완료될 수 있다.
AVL트리는 레드블랙트리보다 훨씬더 타이트하게 균형잡혀 있으므로 트리의 높이가 더 낮다. 따라서 조회연산이 더 빠르다. 조회연산이 많은경우 avl 트리를 사용하는것이 좋다.
레드블랙트리는 삽입연산이 많은경우 사용하면 좋다. 레드블랙트리는 한번의 삽입연산에 O(1)의 회전연산을 보장한다. AVL 트리는 매우 타이트하게 밸런스를 유지하므로 한번의 삽입연산에 연쇄적으로 많은 회전이 일어날 수 있다.
BST와 b 트리를 비교해주세요
BST는 주로 균형을 이루는 이진트리이다. BST는 랜덤엑세스가 메인메모리까지만 일어난다는 가정 하에서 설계된 데이터구조이다.
B트리는 디스크기반 스토리지에 적합하다. 한노드에 연속된 메모리(배열)를 할당해 많은 데이터를 저장한다. 이렇게 하면 한번의 디스크읽기를 통해 (단일 디스크 블록 읽는데 10ms 걸릴 수 있음) 최대로 주변노드들의 데이터를 함께 가져오게 된다. 이를 통해 데이터 검색시간을 줄일 수 있게 되고 디스크에 재차 접촉해야하는 횟수를 줄이게 되므로, 디스크 기반 스토리지에 적합한 데이터 구조이다.
