한국어
메뉴

자료 구조와 알고리즘

가변 길이 배열에서, 용량이 가득 찼을 때 원소를 추가하면 2배 용량의 영역을 새로 확보하여 모든 원소를 복사한다. 용량 1인 빈 배열에 원소를 하나씩 1,000개 추가했을 때, 복사되는 원소의 총수는?

  1. A10
  2. B1,023
  3. C499,500
정답과 해설 보기

정답: B. 1,023

용량은 1, 2, 4, …, 512로 가득 찰 때마다 2배가 되고, 그때마다 그 시점의 원소를 복사하므로 복사의 총수는 1 + 2 + 4 + … + 512 = 1,023입니다. 1,000개의 추가에 대해 복사는 원소 수의 약 1배이므로 추가 1회당 수고는 평균하면 일정, 즉 분할 상환 O(1)이 됩니다. 용량을 1씩만 늘리면 복사는 1 + 2 + … + 999 = 499,500이 되어 O(n²)입니다. 10은 영역을 다시 확보한 횟수이며, 복사되는 원소의 수가 아닙니다.

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

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

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