한국어
메뉴

자료 구조와 알고리즘

원소 수가 많고 적재율을 0.5 정도로 유지한 해시 테이블에서, 선형 탐사의 개방 주소법이 체이닝(연결 리스트로 잇는 방법)보다 빨라지기 쉬운 이유로 가장 적절한 것은?

  1. A충돌했을 때 조사하는 다음 위치가 이웃 원소이므로, 같은 캐시 라인이나 바로 다음 라인에 실려 있는 경우가 많아 메모리 접근이 적게 들기 때문
  2. B개방 주소법에서는 충돌이 전혀 일어나지 않기 때문
  3. C체이닝에서는 해시 함수를 2회 이상 계산해야 하기 때문
정답과 해설 보기

정답: A. 충돌했을 때 조사하는 다음 위치가 이웃 원소이므로, 같은 캐시 라인이나 바로 다음 라인에 실려 있는 경우가 많아 메모리 접근이 적게 들기 때문

현재의 CPU에서는 캐시 미스로 주기억을 읽는 시간이 비교 등의 계산보다 훨씬 오래 걸립니다. 선형 탐사에서는 충돌해도 이웃 위치를 조사하므로 대부분 같은 캐시 라인 안에서 끝나고, 프리페치도 잘 듣습니다. 체이닝에서는 리스트의 다음 원소가 메모리 위의 떨어진 곳에 있는 경우가 많아, 포인터를 따라갈 때마다 캐시 미스가 일어나기 쉬워집니다. 시간 복잡도의 차수가 같더라도 메모리 접근 방식에 따라 실제 속도는 크게 달라집니다. 다만 선형 탐사는 적재율이 높아지면 채워진 위치가 뭉쳐서 급격히 느려지므로, 적재율을 낮게 유지합니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. GPU 같은 병렬 처리 장치에서 정렬을 수행할 때, 바이토닉 정렬처럼 비교·교환 절차가 정해져 있는 정렬(정렬 네트워크)이 쓰이는 경우가 있다. 그 이유로 올바른 것은?
  2. 원소 수가 n인 배열에서 서로 다른 두 원소의 쌍을 모두 한 번씩 비교하는 처리(i번째 원소를 그보다 뒤에 있는 모든 원소와 비교하는 것을, i를 하나씩 늘려 가며 반복하는 이중 루프)의 시간 복잡도는?
  3. 시간 복잡도가 O(n²)인 프로그램에서 데이터 수가 1,000일 때 처리 시간이 0.5초였다. 데이터 수를 4,000으로 하면 처리 시간은 약 몇 초가 되는가?
  4. 서로 다른 100개의 값이 들어 있는 배열에서, 앞에서부터 차례로 하나씩 비교하는 선형 탐색으로 목표 값을 찾는다. 목표 값은 반드시 배열 안에 있고 어느 위치에 있을 확률도 같을 때, 비교 횟수의 평균은 얼마인가?
  5. 배열과 비교했을 때 연결 리스트(각 원소가 다음 원소의 위치를 가리키는 포인터를 가진 리스트)의 특징으로 올바른 것은?