연습 문제

알고리즘 복잡도와 Big-O 표기법 (컴퓨터/정보 고등 정보)

문제에 답하고 제출하면 정답과 풀이를 확인할 수 있습니다. 한 세트는 5문항으로 구성됩니다.

아래의 기본 문제를 먼저 풀어 보세요. 자동 채점 화면은 자바스크립트가 켜진 브라우저에서 이용할 수 있습니다.

문제와 해설로 복습하기

이 단원의 기본 문제 5개입니다. 먼저 스스로 풀고, 힌트와 해설을 열어 풀이 과정을 비교해 보세요. 위의 채점 연습에서는 기본 문제를 다시 풀거나, 지원되는 수학 단원의 변형 문제를 풀 수 있습니다.

기본 문제 1

반복문 하나가 n번 돌고 매번 상수 시간 작업만 한다면 시간 복잡도는 무엇인가요?
  1. O(n)
  2. O(1)
  3. O(log n)
  4. O(n²)
힌트 보기반복 횟수에 비례합니다.
정답과 풀이 보기
정답: O(n)

  1. 1. 풀이

    상수 작업을 n번 수행하므로 증가율은 선형 O(n)입니다.

기본 문제 2

입력을 매 단계 절반으로 줄여 찾는 알고리즘의 시간 복잡도는 무엇인가요?
  1. O(log n)
  2. O(1)
  3. O(n)
  4. O(n²)
힌트 보기몇 번 절반으로 줄이면 1이 되는지 세세요.
정답과 풀이 보기
정답: O(log n)

  1. 1. 풀이

    단계마다 크기가 절반이 되므로 단계 수는 log₂n에 비례합니다.

기본 문제 3

서로 독립적인 O(n) 반복문 두 개가 순서대로 실행될 때 전체 복잡도는 무엇인가요?
  1. O(n)
  2. O(n²)
  3. O(log n)
  4. O(1)
힌트 보기덧셈에서 지배적인 차수를 남기세요.
정답과 풀이 보기
정답: O(n)

  1. 1. 풀이

    n+n=2n이며 Big-O에서는 상수 계수 2를 생략해 O(n)입니다.

기본 문제 4

크기 n 배열의 모든 서로 다른 두 원소 쌍을 검사하는 이중 반복문의 복잡도는 보통 무엇인가요?
  1. O(n²)
  2. O(n)
  3. O(log n)
  4. O(2n)
힌트 보기각 원소마다 약 n개의 상대를 확인합니다.
정답과 풀이 보기
정답: O(n²)

  1. 1. 풀이

    원소 수 n개 각각에 대해 최대 n개를 검사하므로 비교 횟수가 n²에 비례합니다.

기본 문제 5

입력 n=100,000에서 O(n²) 알고리즘과 O(n log n) 알고리즘 중 대체로 더 확장성이 좋은 것은 무엇인가요?
  1. O(n log n)
  2. O(n²)
  3. 둘은 항상 같다
  4. 복잡도만으로는 차이를 전혀 비교할 수 없다
힌트 보기입력이 커질 때 두 증가율을 비교하세요.
정답과 풀이 보기
정답: O(n log n)

  1. 1. 풀이

    n이 커지면 n log n은 n²보다 훨씬 느리게 증가하므로 일반적으로 O(n log n)이 확장성이 좋습니다.

참고 근거와 확인 범위

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.