알고리즘과 복잡도쉬움
증가율의 상한(upper bound)을 나타내는 표기법은 무엇입니까?
- ABig Omega
- BLittle omega
- CBig O
- DBig Theta
힌트 보기
- "최대"를 의미합니다.
- 오답 두 개를 지웠습니다. 남은 두 개 중 하나가 정답입니다.
정답과 설명 보기
이것이 답인 이유
O는 상한, Ω는 하한, Θ는 정확한 한계(tight bound)를 나타냅니다.
답
C · Big O
자료구조와 알고리즘: 연습 문제와 시험 문제
빅오 표기법, 주요 알고리즘의 실행 시간, 배열·연결 리스트·트리·해시 테이블·그래프 사이의 장단점.
벼락치기 팩 (PDF)인쇄하기 좋은 공식 모음, 풀이 단계 요약, 전체 풀이가 있는 연습 문제.
이 강의의 주제
자료구조와 알고리즘 시험 팁
- 중첩 반복문은 반복 횟수를 곱하고, 연달아 나오는 반복문은 더 큰 항만 남기세요.
- 각 자료구조의 탐색, 삽입, 삭제 비용을 알아 두세요.
- 매 단계 입력을 절반으로 줄이면 로그 시간이 됩니다.
예제 풀이
자료구조보통
이진 최소 힙에서 extract-min은 어떻게 동작합니까?
- A배열의 마지막 원소를 제거한다
- B마지막 원소를 루트로 옮기고 아래로 내린다
- C루트를 제거하고 모든 원소를 왼쪽으로 한 칸씩 이동시킨다
- D모든 리프에서 새로운 최솟값을 찾는다
힌트 보기
- 트리를 완전 트리로 유지한 다음 순서를 고칩니다.
- 오답 두 개를 지웠습니다. 남은 두 개 중 하나가 정답입니다.
정답과 설명 보기
이것이 답인 이유
마지막 원소가 루트의 빈자리를 채우고, 힙 성질이 성립할 때까지 더 작은 자식과 교환되며, O(log n)이 걸립니다.
답
B · 마지막 원소를 루트로 옮기고 아래로 내린다
연습 방법
- “이 강의 연습하기”는 실제 시험처럼 모든 주제의 문제를 섞어서 냅니다.
- 문제마다 값이 새로 바뀌므로 답이 아니라 푸는 방법을 익히게 됩니다.
- 막혔나요? 먼저 작은 힌트를 열고, 필요할 때만 전체 해설을 보세요.
- 모의고사는 제한 시간이 있고 힌트가 없으며, 끝나면 점수와 함께 전체 풀이를 검토할 수 있습니다.