한국어
메뉴

자료 구조와 알고리즘

시간 복잡도(빅오 표기법), 배열과 연결 리스트, 스택과 큐, 해시 테이블, 이진 탐색, 각종 정렬의 절차와 안정성, 이진 탐색 트리와 힙, 그래프 탐색과 최단 경로, 재귀·동적 계획법·탐욕 알고리즘을 객관식 문제로 학습합니다. 캐시나 GPU와의 관계도 다룹니다.

10문제 연습하기이 분야에서 무작위 10문제 · 약 5분 이 분야 연습하기이 분야의 모든 문제를 무작위 순서로 풀어요 취약 문제최근에 틀린 문제만 다시 풀어요

자료 구조와 알고리즘: 핵심 정리

같은 문제를 푸는 프로그램이라도, 사용하는 자료 구조와 알고리즘에 따라 데이터가 늘어났을 때의 속도는 자릿수가 다르게 달라집니다. 시간 복잡도의 차수로 수고가 늘어나는 방식을 어림하고, 데이터의 사용 방식에 맞는 구조를 고르는 것이 빠른 프로그램의 출발점입니다.

배열과 연결 리스트, 스택과 큐, 해시 테이블, 이진 탐색 트리와 힙, 그래프의 표현 방법 같은 기본 자료 구조와, 이진 탐색, 버블·선택·삽입·병합·퀵·힙 등의 정렬, 너비 우선 탐색·깊이 우선 탐색·다익스트라 알고리즘, 재귀·동적 계획법·탐욕 알고리즘을 절차를 하나씩 따라가는 계산 문제를 중심으로 학습합니다. IT 자격시험의 알고리즘 분야 학습에도 도움이 됩니다. 나아가 캐시에 맞는 데이터 배치나 GPU에서의 병렬 정렬 등 하드웨어 성능과의 관계도 다룹니다.

자료 구조와 알고리즘 전체 문제 (40)
  1. 원소 수가 n인 배열에서 서로 다른 두 원소의 쌍을 모두 한 번씩 비교하는 처리(i번째 원소를 그보다 뒤에 있는 모든 원소와 비교하는 것을, i를 하나씩 늘려 가며 반복하는 이중 루프)의 시간 복잡도는?
  2. 시간 복잡도가 O(n²)인 프로그램에서 데이터 수가 1,000일 때 처리 시간이 0.5초였다. 데이터 수를 4,000으로 하면 처리 시간은 약 몇 초가 되는가?
  3. 서로 다른 100개의 값이 들어 있는 배열에서, 앞에서부터 차례로 하나씩 비교하는 선형 탐색으로 목표 값을 찾는다. 목표 값은 반드시 배열 안에 있고 어느 위치에 있을 확률도 같을 때, 비교 횟수의 평균은 얼마인가?
  4. 배열과 비교했을 때 연결 리스트(각 원소가 다음 원소의 위치를 가리키는 포인터를 가진 리스트)의 특징으로 올바른 것은?
  5. 빈 스택에 대해 push 1, push 2, pop, push 3, push 4, pop, pop의 순서로 조작했다. pop으로 꺼낸 값을 차례로 나열한 것은?
  6. 빈 큐에 A, B, C의 순서로 원소를 넣고 하나를 꺼낸 뒤, D를 넣고 하나를 꺼내고, E를 넣고 하나를 꺼냈다. 꺼낸 원소를 차례로 나열한 것은?
  7. 역폴란드 표기법(후위 표기법)으로 쓴 식 '3 4 + 2 * 5 −'를, 수가 오면 스택에 쌓고 연산자가 오면 두 값을 꺼내 계산하여 결과를 쌓는 방법으로 평가했다. 결과는 얼마인가? 여기서 연산자의 왼쪽 값은 먼저 쌓인 쪽의 값으로 한다.
  8. 해시 테이블에서 충돌(collision)에 대한 설명으로 올바른 것은?
  9. 크기 7인 해시 테이블(위치 0~6)에 해시 함수 h(k) = k mod 7로 키 10, 17, 24, 3을 이 순서로 저장한다. 충돌했을 때는 위치를 하나씩 뒤로 옮기며(6 다음은 0) 빈 위치를 찾는 선형 탐사법을 사용한다. 키 3이 저장되는 위치는?
  10. 해시 테이블의 충돌을 처리하는 방법으로 체이닝(같은 위치의 원소를 연결 리스트로 잇는다)과 개방 주소법(표 안의 비어 있는 다른 위치를 찾는다)을 비교한 설명으로 올바른 것은? 적재율은 저장한 원소 수를 표의 크기로 나눈 값으로 한다.
  11. 배열 가운데의 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 이진 탐색을 사용하기 위한 전제 조건으로 올바른 것은?
  12. 오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 작다·더 크다'를 알 수 있다고 하면, 찾는 경우와 찾지 못하는 경우를 모두 포함하여 비교 횟수는 최대 몇 회인가?
  13. 오름차순으로 늘어선 배열 a[0]~a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60에서 이진 탐색으로 38을 찾는다. 찾는 범위를 하한 lo = 0, 상한 hi = 9에서 시작하고, 가운데 위치를 (lo + hi) ÷ 2의 버림으로 한다. 38과 비교되는 원소의 값을 차례로 나열한 것은?
  14. 배열 5, 3, 8, 1, 4를 버블 정렬로 오름차순 정렬한다. 앞에서부터 이웃한 원소끼리 비교하여 왼쪽이 더 크면 교환하는 조작을 끝까지 1회 수행한(1패스) 후의 배열은?
  15. 배열 29, 10, 14, 37, 13을 선택 정렬(정렬되지 않은 부분에서 최솟값을 찾아, 정렬되지 않은 부분의 맨 앞과 교환한다)로 오름차순 정렬한다. 이 조작을 2회 수행한 후의 배열은?
  16. 원소 수 10인 배열을 삽입 정렬로 오름차순 정렬한다. 두 번째 이후의 원소를 차례로 꺼내어, 왼쪽 이웃부터 차례로 비교하며 꺼낸 값 이하인 원소가 발견되거나 맨 앞에 도달할 때까지 비교한다. 처음부터 오름차순으로 늘어서 있는 경우와 내림차순으로 늘어서 있는 경우의 비교 횟수의 조합은?
  17. 최악의 경우에도 시간 복잡도가 O(n log n)이고, 작업용 배열 등의 추가 기억 영역을 거의 사용하지 않고 정렬할 수 있는 정렬 방식은?
  18. (이름, 점수) 데이터 (A, 80), (B, 70), (C, 80), (D, 70)이 이 순서로 늘어서 있다. 점수의 오름차순으로 안정 정렬했을 때 이름의 순서는?
  19. 퀵 정렬의 시간 복잡도가 O(n²)이 되는 전형적인 경우는?
  20. 병합 정렬에서 오름차순으로 정렬된 두 열 1, 4, 7, 9와 2, 3, 8, 10을, 맨 앞끼리 비교하여 작은 쪽을 출력하는 것을 반복하여 하나의 열로 합친다(병합한다). 한쪽 열이 비면 나머지는 비교하지 않고 그대로 출력한다. 비교 횟수는 몇 회인가?
  21. 이진 힙을, 루트를 a[0]으로 하는 배열 a[0], a[1], a[2], …에 위쪽 단부터 차례로 왼쪽부터 채워 저장한다. a[4]의 자식과 부모로 올바른 것은?
  22. 부모의 값이 자식의 값 이상이 되는 최대 힙을, 루트를 a[0]으로 하는 배열로 나타내고 있다. 힙 50, 30, 40, 10, 20, 35에 45를 추가한다. 맨 끝에 놓은 뒤 부모보다 큰 동안은 부모와 교환하는 조작을 수행한 후의 배열은?
  23. 이진 탐색 트리를 중위 순회(왼쪽 서브트리, 그 노드, 오른쪽 서브트리 순으로 방문한다)로 따라갔을 때, 방문한 노드의 값은 어떻게 늘어서는가? 값은 모두 서로 다르다고 한다.
  24. 빈 이진 탐색 트리에 50, 30, 70, 20, 40, 60, 80의 순서로 값을 삽입했다. 이 트리를 후위 순회(왼쪽 서브트리, 오른쪽 서브트리, 그 노드 순으로 방문한다)로 따라갔을 때의 순서는?
  25. 빈 이진 탐색 트리에 1, 2, 3, …, 1000의 순서로 값을 삽입했다(균형을 잡는 조작은 하지 않는다). 이 트리에서 1000을 찾을 때, 루트부터 비교하기 시작하여 찾을 때까지 비교하는 노드의 수는?
  26. 데이터베이스나 파일 시스템의 인덱스에 이진 탐색 트리가 아니라 B 트리(B+ 트리 포함)가 자주 쓰이는 주된 이유는?
  27. 정점이 100만 개, 간선이 300만 개 정도인 도로망처럼 정점 수에 비해 간선이 적은(희소한) 그래프를 메모리에 저장하는 방법으로 적절한 것은?
  28. 간선에 가중치가 없는 그래프에서, 출발점에서 각 정점까지의 최소 간선 수를 구하고 싶다. 적합한 탐색 방법과 그때 사용하는 자료 구조의 조합은?
  29. 간선에 방향이 없는 그래프에서 각 정점의 이웃 정점이 다음과 같다. A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. 정점 A부터 재귀적인 깊이 우선 탐색을 수행한다. 이웃 정점은 여기에 쓴 순서로 조사하고, 아직 방문하지 않은 정점이 발견되면 바로 그 정점으로 나아간다. 정점을 방문하는 순서는?
  30. 간선에 방향이 없는 그래프에서 간선의 가중치(거리)가 S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3, A−T: 6이다. 다익스트라 알고리즘으로 S에서 T까지의 최단 경로를 구했을 때, 그 경로와 길이는?
  31. 다익스트라 알고리즘으로 올바른 최단 경로를 구하기 위한, 그래프에 관한 조건으로 올바른 것은?
  32. 작업 A~E에 'A는 C보다 앞', 'B는 C보다 앞', 'C는 D보다 앞', 'B는 E보다 앞', 'E는 D보다 앞'이라는 순서 제약이 있다. 모든 제약을 만족하는 작업의 순서(위상 정렬의 결과)는?
  33. 함수 f(x, y)를 'y가 0이면 x를 반환하고, 그렇지 않으면 f(y, x mod y)를 반환한다'로 정의한다. f(84, 36)을 호출했을 때의 반환값과, f가 호출되는 횟수(첫 호출 포함)의 조합은?
  34. 피보나치 수를 구하는 함수 fib(n)을 'n이 1 이하이면 n을 반환하고, 그렇지 않으면 fib(n−1) + fib(n−2)를 반환한다'로 재귀적으로 정의했다. fib(5)를 호출했을 때 fib가 호출되는 횟수는 첫 호출을 포함하여 몇 회인가?
  35. 1엔, 4엔, 6엔의 3종류 동전으로 8엔을 지불한다. 큰 동전부터 쓸 수 있는 만큼 쓰는 탐욕 알고리즘으로 정했을 때의 개수와 최소 개수의 관계로 올바른 것은?
  36. 용량 8인 배낭에 (무게, 가치)가 (2, 3), (3, 4), (4, 5), (5, 6)인 4개의 물건 중에서 골라 넣는다. 각 물건은 하나씩밖에 없고 나눌 수 없다. 무게의 합계가 8 이하일 때 가치 합계의 최댓값은 얼마인가?
  37. 문자열 안에서 패턴을 찾는 BM법(보이어-무어 알고리즘)의 특징으로 올바른 것은?
  38. 가변 길이 배열에서, 용량이 가득 찼을 때 원소를 추가하면 2배 용량의 영역을 새로 확보하여 모든 원소를 복사한다. 용량 1인 빈 배열에 원소를 하나씩 1,000개 추가했을 때, 복사되는 원소의 총수는?
  39. 원소 수가 많고 적재율을 0.5 정도로 유지한 해시 테이블에서, 선형 탐사의 개방 주소법이 체이닝(연결 리스트로 잇는 방법)보다 빨라지기 쉬운 이유로 가장 적절한 것은?
  40. GPU 같은 병렬 처리 장치에서 정렬을 수행할 때, 바이토닉 정렬처럼 비교·교환 절차가 정해져 있는 정렬(정렬 네트워크)이 쓰이는 경우가 있다. 그 이유로 올바른 것은?

컴퓨터 시스템의 다른 분야