방송대 컴퓨터과학개론 5강: 알고리즘 설계와 효율성 분석

방송대 컴퓨터과학개론 5강: 알고리즘 설계와 효율성 분석

같은 정답을 내는 두 절차가 있다면 어느 쪽을 선택해야 할까요? 작은 입력에서는 빠르던 방법이 데이터가 커지면 급격히 느려질 수 있고, 매 단계에서 가장 좋아 보이는 선택이 전체 최적해를 보장하지 않을 수도 있습니다. 이 글은 알고리즘의 성립 조건에서 출발해 설계 기법을 구분하고, 단위 연산을 세어 점근 성능을 구한 뒤 선택·버블·삽입 정렬의 실행 과정을 직접 추적하도록 안내합니다.

정답을 내는 절차와 좋은 알고리즘은 같은 말이 아니다

정렬되지 않은 카드 더미에서 특정 카드를 찾는 두 방법을 생각해 봅시다. 앞에서부터 한 장씩 확인하는 순차 탐색은 카드의 배치에 특별한 조건이 없어도 작동합니다. 반면 이진 탐색은 가운데 값을 기준으로 범위를 절반씩 줄여 빠르게 찾지만, 카드가 기준에 따라 정렬되어 있어야 합니다. 둘 다 찾기 문제를 풀 수 있어도 입력 조건과 수행량이 다릅니다.

알고리즘은 주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것입니다. 단순히 결과가 맞는 절차를 넘어 실제 컴퓨터가 수행할 수 있고, 끝나며, 필요한 자원을 합리적으로 써야 합니다. 요리의 레시피가 재료와 순서만 적는 것이 아니라 모호하지 않은 작업과 종료점을 제시해야 하는 것과 비슷합니다.

조건	판정 질문	조건이 깨진 예	고치는 기준
입출력	외부 입력 0개 이상과 출력 1개 이상이 있는가	계산만 반복하고 결과를 내지 않음	문제의 결과를 명시함
명확성	각 명령의 의미가 하나로 정해지는가	“적당히 큰 값을 고른다”	비교 기준과 동률 규칙을 정함
유한성	한정된 단계를 거친 뒤 종료하는가	종료 조건이 없는 반복	반복할 때 종료 조건에 가까워지는지 확인함
유효성	각 명령을 컴퓨터가 실행할 수 있는가	정의되지 않은 정보를 즉시 알아내라고 지시함	기본 연산으로 구체화함
효율성	실용적으로 시간과 공간을 감당할 수 있는가	작은 입력에서도 지나치게 많은 경우를 확인함	입력 증가에 따른 자원 사용을 분석함

판단 핵심: “답이 나온다”는 정확성의 일부일 뿐입니다. 알고리즘을 평가할 때는 입력 조건, 종료 여부, 실행 가능성, 결과의 정확성과 자원 사용을 분리해 확인해야 합니다.

설계에서 분석까지는 서로 다른 질문을 푸는 과정이다

강의는 알고리즘 생성 과정을 설계, 표현·기술, 정확성 검증, 효율성 분석으로 나누어 보여 줍니다. 예를 들어 n개 수의 합을 구한다면 먼저 “입력을 하나씩 누적한다”는 방법을 설계하고, 일상 언어·순서도·의사코드 가운데 적절한 수단으로 표현합니다. 다음으로 모든 유효한 입력에서 합이 맞는지 검증하고, 마지막으로 입력이 커질 때 시간과 공간이 어떻게 늘어나는지 분석합니다.

1. 설계: 문제를 어떤 단계와 자료 관계로 풀지 정합니다.
2. 표현·기술: 자연어, 순서도, 의사코드 등으로 실행 순서를 모호하지 않게 나타냅니다.
3. 정확성 검증: 유효한 입력에 대해 요구한 결과를 내는지 논리적으로 확인합니다.
4. 효율성 분석: 실행에 필요한 시간과 메모리가 입력 크기에 따라 어떻게 변하는지 측정합니다.

이 단계들을 섞으면 오류 원인을 찾기 어렵습니다. 의사코드가 깔끔해도 설계가 잘못되면 정답이 나오지 않고, 정확한 알고리즘이어도 입력이 커질 때 수행량이 감당하기 어려우면 실용성이 낮습니다. 또한 효율적인 프로그램은 알고리즘만으로 완성되지 않습니다. 데이터 사이의 논리 관계를 나타내는 자료구조와 처리 절차인 알고리즘을 함께 선택해야 합니다.

설계 기법은 작은 문제의 관계와 선택의 보장 조건으로 구분한다

모든 문제에 통하는 단일 설계 기법은 없습니다. 강의는 대표적으로 분할정복, 동적 프로그래밍, 욕심쟁이 방법을 제시합니다. 이름보다 작은 문제들이 서로 독립적인지, 계산 결과를 재사용하는지, 국부 최적 선택이 전체 최적해로 이어지는지를 물어야 합니다.

기법	진행 방향과 핵심	작은 문제의 관계	대표 판단 기준
분할정복	분할 → 정복 → 결합의 하향식 접근	원래 문제와 같고 더 작으며 서로 독립적	독립적으로 푼 해를 결합할 수 있는가
동적 프로그래밍	작은 문제의 해를 저장해 큰 해를 만드는 상향식 접근	서로 독립일 필요가 없고 결과를 재사용	같은 작은 문제를 반복 계산하는가
욕심쟁이 방법	각 단계에서 가장 좋아 보이는 국부 해를 선택	이전 선택을 보통 되돌리지 않음	국부 최적 선택이 전체 최적을 보장하는가

분할정복의 정복 단계에서는 문제가 충분히 작아지면 순환 호출 없이 직접 풉니다. 결합 단계가 없는 문제도 있습니다. 동적 프로그래밍은 플로이드 알고리즘처럼 작은 문제의 해를 표에 저장해 더 큰 문제의 해를 점진적으로 구성할 수 있습니다. 욕심쟁이 방법은 단순하고 강력하지만 적용 범위가 제한적입니다.

오개념 교정: 매 순간 가장 큰 이익을 택했다고 해서 최종 결과도 자동으로 최적이 되는 것은 아닙니다. 욕심쟁이 방법은 선택 규칙이 문제의 구조와 맞아 전체 최적해를 보장할 때 사용해야 합니다.

욕심쟁이 선택은 계산 순서와 문제 조건을 함께 확인한다

강의의 거스름돈 예에서는 770원을 500원, 100원, 50원, 10원 동전으로 돌려줍니다. 가장 큰 동전부터 선택하면 500원 한 개, 100원 두 개, 50원 한 개, 10원 두 개로 총 6개입니다. 여기서 중요한 것은 “큰 동전부터”라는 문구 자체가 아니라, 주어진 동전 체계에서 그 선택이 최소 동전 수에 맞는지 확인하는 일입니다.

배낭 문제 예는 물체를 쪼개 넣을 수 있다는 조건을 명시합니다. 용량 10kg이고 (무게, 이익)이 (4,14), (3,15), (5,20), (3,9)라면 단위 무게당 이익은 각각 3.5, 5, 4, 3입니다. 따라서 비율이 높은 순서인 두 번째, 세 번째, 첫 번째, 네 번째 물체 순으로 검토합니다.

1. 무게 3, 이익 15인 두 번째 물체를 모두 넣으면 남은 용량은 7kg입니다.
2. 무게 5, 이익 20인 세 번째 물체를 모두 넣으면 남은 용량은 2kg입니다.
3. 첫 번째 물체는 4kg이므로 절반인 2kg만 넣고 이익 14의 절반인 7을 얻습니다.
4. 총무게는 3+5+2=10kg, 총이익은 15+20+7=42입니다.

이 풀이가 가능한 이유는 물체를 분할할 수 있기 때문입니다. 물체를 통째로만 넣어야 한다면 단위 이익 순으로 일부를 잘라 넣는 세 번째 단계가 허용되지 않습니다. 같은 ‘배낭 문제’라는 이름보다 분할 가능 여부가 적용 가능한 알고리즘을 가르는 조건입니다.

시간 복잡도는 초가 아니라 입력 크기의 함수로 센다

실제 실행 시간을 초 단위로 재면 컴퓨터 속도, 프로그래밍 언어, 작성 방식과 컴파일러에 따라 결과가 달라져 일반적으로 비교하기 어렵습니다. 시간 복잡도는 알고리즘에서 수행되는 단위 연산의 횟수를 모두 더하고, 이를 입력 크기 n의 함수로 나타냅니다. 같은 알고리즘도 입력 상태에 따라 최선·평균·최악 수행 시간이 달라질 수 있습니다.

n개 수의 합과 평균을 구하는 강의의 의사코드를 단위 연산으로 세어 봅시다. 초기화 두 번은 1+1, 반복 조건 검사는 n+1번, 합 갱신과 인덱스 증가는 각각 n번, 평균 계산과 출력은 각각 1번입니다.

i = 0
sum = 0
while i < n:
    sum = sum + a[i]
    i = i + 1
average = sum / n
print sum, average

따라서 총횟수는 1+1+(n+1)+n+n+1+1 = 3n+5입니다. 반복문 본문이 n번 실행된다는 것만 세어 2n이라고 하면 조건 검사의 마지막 실패 1회와 반복문 밖 연산을 빠뜨립니다. 정확한 횟수를 얻은 뒤, 큰 입력에서 증가 추세를 지배하는 항을 남겨 점근 성능을 판단합니다.

계산 순서: 입력 크기를 정하고 → 각 문장의 실행 횟수를 표시하고 → 합하여 f(n)을 만들고 → 최고차항을 찾아 점근 표기로 단순화하십시오.

작은 입력의 역전보다 큰 입력의 증가 추세가 중요하다

f₁(n)=10n+9와 f₂(n)=n²/2+3n을 비교하면 n=5에서는 f₂가 27.5로 f₁의 59보다 작습니다. 그러나 n=16에서는 f₁=169, f₂=176으로 순서가 바뀌고, 이후 n이 커질수록 제곱항의 영향이 더 커집니다. 작은 입력에서 한 번 빠르다는 사실만으로 큰 입력에서도 우수하다고 결론 내릴 수 없습니다.

점근 성능은 입력 크기 n이 충분히 커질 때 결정되는 성능입니다. 계수와 낮은 차수 항보다 최고차항을 이용해 증가 추세를 간단히 표현하므로 알고리즘 사이의 확장성을 비교하기 쉽습니다.

정확한 수행 함수	큰 n에서 지배하는 항	점근적 차수	판정 이유
7	상수	Θ(1)	입력 증가와 무관함
3n+5	n	Θ(n)	상수 계수와 상수항을 제거함
n²/2+3n	n²	Θ(n²)	n²이 n보다 빠르게 증가함
2n³+3n²+n+10	n³	Θ(n³)	가장 높은 차수인 3차항이 지배함

O·Ω·Θ는 위쪽·아래쪽·양쪽 경계를 구분한다

Big-O는 점근적 상한, Big-Ω는 점근적 하한, Big-Θ는 점근적 상하한을 나타냅니다. 충분히 큰 n, 즉 어떤 n₀ 이후에 양의 상수배 g(n)과 비교한다는 점이 공통입니다. 초반의 몇 값이 경계를 벗어나더라도 n₀ 이후 조건이 유지되면 점근 관계가 성립할 수 있습니다.

표기	n≥n₀에서의 조건	말로 읽기	자주 하는 착각
f(n)=O(g(n))	f(n)≤c·g(n)	g의 상수배가 위에서 덮음	정확히 같은 증가율이라는 뜻으로 오해
f(n)=Ω(g(n))	f(n)≥c·g(n)	g의 상수배가 아래에서 받침	최악 수행 시간과 같은 용어로만 오해
f(n)=Θ(g(n))	c₁g(n)≤f(n)≤c₂g(n)	위아래에서 같은 차수로 조임	O와 Ω 중 하나만 보여도 성립한다고 오해

예를 들어 f(n)=3n+3은 충분히 큰 n에서 n의 상수배로 위에서도 덮이고 아래에서도 받쳐지므로 Θ(n)입니다. 2n³+3n²+n+10은 최고차항이 n³이므로 강의에서는 O(n³)으로 나타냅니다. 정확한 차수를 말하려면 상한뿐 아니라 하한도 같은 차수임을 확인해 Θ를 사용할 수 있습니다.

대표적인 증가 순서는 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)입니다. 이는 같은 입력 크기에서 언제나 실제 초 단위 실행 시간이 이 순서라는 뜻이 아니라, 충분히 큰 입력에서 증가 추세를 비교한 것입니다.

정렬은 저장 위치와 비교 방식부터 분류한다

정렬은 키값을 정해 원하는 순서로 데이터를 나열하는 일입니다. 강의의 기본 가정은 n개의 양의 정수 키를 배열 A[0..n-1]에 저장하고 오름차순으로 정렬하는 것입니다. 먼저 정렬 수행 시점에 데이터가 어디에 있는지에 따라 내부 정렬과 외부 정렬을 구분합니다.

• 내부 정렬: 모든 데이터를 주기억장치에 적재한 뒤 정렬합니다.
• 외부 정렬: 전체를 주기억장치에 둘 수 없어 보조기억장치에 저장하고 일부를 번갈아 적재하며 정렬합니다.

내부 정렬은 키를 서로 비교하는 비교 기반과 값의 분포를 이용하는 분포 기반으로 다시 나눌 수 있습니다. 강의는 비교 기반에 선택·버블·삽입·퀵·합병 정렬, 분포 기반에 계수·기수 정렬을 배치합니다. 이번 차시의 실행 추적은 선택, 버블, 삽입 정렬에 집중합니다.

세 기본 정렬은 한 단계가 확정하는 범위가 다르다

직접 구성한 배열 [7, 3, 5, 2]를 오름차순으로 정렬하며 첫 단계를 비교해 봅시다.

정렬	첫 단계의 핵심 동작	첫 단계 뒤 상태	확정되거나 유지되는 부분
선택 정렬	전체 미정렬 구간의 최솟값 2를 찾아 첫 원소 7과 교환	[2, 3, 5, 7]	맨 앞의 최솟값이 확정됨
버블 정렬	왼쪽부터 인접 쌍을 비교해 큰 값을 오른쪽으로 보냄	[3, 5, 2, 7]	한 회전 뒤 최댓값 7이 맨 뒤에 확정됨
삽입 정렬	두 번째 값 3을 앞의 정렬 구간 [7]에서 제자리로 삽입	[3, 7, 5, 2]	앞의 두 원소가 정렬 상태를 유지함

선택 정렬은 미정렬 부분에서 최솟값을 골라 맨 앞과 바꾸는 작업을 n-1번 반복합니다. 입력이 이미 정렬되어 있어도 최솟값을 찾는 비교 과정은 계속되므로 강의에서는 입력 상태에 민감하지 않은 O(n²)로 설명합니다.

버블 정렬은 모든 인접한 두 값을 차례로 비교하고 왼쪽이 크면 교환합니다. 이미 오름차순이면 교환 없이 확인하여 최선 O(n), 역순이면 많은 비교와 교환이 일어나 최악 O(n²)입니다. 선택 정렬보다 데이터 교환이 더 많이 발생할 수 있습니다.

삽입 정렬은 배열을 정렬 부분과 미정렬 부분으로 나누고, 미정렬 부분의 첫 원소를 하나씩 뽑아 정렬 부분의 제자리에 끼워 넣습니다. 이미 정렬된 입력에서는 새 원소가 현재 정렬 구간의 끝에 그대로 놓여 최선 O(n)이고, 역순 입력에서는 앞 원소들을 계속 이동해야 해 최악 O(n²)입니다.

실행 추적 요령: 선택 정렬은 ‘왼쪽 확정 구간’, 버블 정렬은 ‘오른쪽 확정 구간’, 삽입 정렬은 ‘항상 정렬된 왼쪽 구간’을 표시하십시오. 숫자 이동만 보면 세 알고리즘을 혼동하기 쉽습니다.

풀이를 마칠 때는 결과·과정·성능을 따로 검산한다

알고리즘 문제에서 정렬 결과만 맞는다고 과정 추적까지 맞은 것은 아닙니다. 다음 세 층을 분리해 검산하면 오류를 찾기 쉽습니다.

1. 결과 검산: 출력이 문제의 요구를 만족하는가. 정렬이라면 모든 i<j에 대해 A[i]≤A[j]인지 확인합니다.
2. 과정 검산: 선택한 설계 기법과 알고리즘의 불변 조건이 단계마다 유지되는가. 삽입 정렬이라면 왼쪽 정렬 구간이 계속 정렬되어 있어야 합니다.
3. 성능 검산: 입력 크기를 기준으로 단위 연산 횟수를 세었는가. 최고차항과 최선·최악 조건을 혼동하지 않았는가.

예를 들어 버블 정렬의 최선이 O(n)이라는 문장을 모든 구현에 무조건 적용해서는 안 됩니다. 한 회전에서 교환이 없음을 감지해 종료하는 조건이 있다는 강의의 분석 맥락을 확인해야 합니다. 복잡도는 알고리즘 이름만이 아니라 실제 반복과 종료 조건을 보고 판정합니다.

최종 판단 절차: 문제 조건 확인 → 알고리즘 성립 조건 점검 → 단계별 상태 추적 → 단위 연산 계산 → 점근 차수와 입력 상태별 경우 판정의 순서로 풀이하십시오.

핵심 개념 정리

• 알고리즘은 입출력·명확성·유한성·유효성을 갖추고, 실용적으로는 효율성까지 검토해야 합니다.
• 분할정복은 독립적인 작은 문제를 풀어 결합하고, 동적 프로그래밍은 작은 해를 저장·재사용하며, 욕심쟁이 방법은 보장 조건 아래 국부 최적을 선택합니다.
• 정확성 분석은 결과가 맞는지를, 효율성 분석은 시간·공간 자원의 증가를 확인합니다.
• 시간 복잡도는 단위 연산 횟수를 입력 크기 n의 함수로 세며, 점근 성능은 최고차항이 만드는 증가 추세를 중심으로 봅니다.
• O는 점근적 상한, Ω는 하한, Θ는 같은 차수의 상하한입니다.
• 선택 정렬은 최솟값을 앞에 확정하고, 버블 정렬은 큰 값을 뒤로 보내며, 삽입 정렬은 왼쪽 정렬 구간에 새 원소를 끼워 넣습니다.

알고리즘을 평가할 때는 ‘답이 맞다’에서 멈추지 마십시오. 먼저 어떤 조건에서 절차가 성립하는지 확인하고, 중간 상태가 규칙을 지키는지 추적한 뒤, 각 문장의 실행 횟수를 n의 함수로 합산하십시오. 마지막으로 충분히 큰 입력에서의 증가율과 최선·최악 입력 조건을 구분하면 설계, 정확성, 효율성을 한 흐름으로 설명할 수 있습니다.

예상문제 10선

1. 알고리즘의 유한성을 가장 정확히 설명한 것은?

① 외부 입력을 정확히 한 개만 받아야 한다 ② 한정된 수의 단계를 거친 뒤 반드시 종료해야 한다 ③ 각 명령의 실행 시간이 모두 같아야 한다 ④ 같은 문제에는 한 가지 절차만 존재해야 한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 외부 입력은 0개 이상일 수 있으며 유한성과 다른 조건입니다.
• ② 정답: 종료 조건에 도달하여 유한 단계 안에 끝나는 성질입니다.
• ③ 오답: 연산 시간이 같을 필요는 없고 각 명령이 수행 가능해야 합니다.
• ④ 오답: 같은 문제에도 여러 알고리즘을 설계할 수 있습니다.

2. 분할정복과 동적 프로그래밍의 구분으로 적절한 것은?

① 두 방법 모두 국부 최적해만 선택하고 되돌리지 않는다 ② 분할정복은 작은 문제의 결과를 사용할 수 없다 ③ 동적 프로그래밍의 작은 문제는 반드시 서로 독립적이다 ④ 분할정복은 독립적인 작은 문제를 결합하고 동적 프로그래밍은 결과를 저장·재사용한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 이는 욕심쟁이 방법의 선택 방식에 가깝습니다.
• ② 오답: 분할정복은 작은 문제의 해를 결합해 원래 해를 만듭니다.
• ③ 오답: 동적 프로그래밍은 겹치는 작은 문제의 해를 재사용할 수 있습니다.
• ④ 정답: 작은 문제의 독립성과 결과 재사용 여부를 바르게 구분합니다.

3. 강의의 분할 가능한 배낭 문제에서 단위 무게당 이익을 기준으로 물체를 고를 수 있는 핵심 조건은?

① 물체를 필요한 무게만큼 쪼개 넣을 수 있다 ② 모든 물체의 무게와 이익이 서로 같다 ③ 배낭의 용량을 초과해도 마지막 물체를 넣는다 ④ 물체를 입력된 순서대로만 선택해야 한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 남은 용량에 맞추어 물체 일부와 비례 이익을 취할 수 있습니다.
• ② 오답: 비율을 비교하려면 오히려 무게와 이익이 달라도 됩니다.
• ③ 오답: 최대 용량은 반드시 지켜야 하는 제약입니다.
• ④ 오답: 입력 순서가 아니라 단위 무게당 이익 순서를 사용합니다.

4. 수행 횟수 함수가 f(n)=6n²+4n+9일 때 점근적으로 가장 알맞은 차수는?

① Θ(1) ② Θ(n) ③ Θ(n²) ④ Θ(n³)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 입력이 커지면 n²항 때문에 수행량도 증가합니다.
• ② 오답: 선형항보다 제곱항이 더 빠르게 증가합니다.
• ③ 정답: 최고차항 n²이 증가 추세를 지배하며 상하한이 같은 차수입니다.
• ④ 오답: 식에 3차항이 없습니다.

5. 점근 표기의 의미를 올바르게 연결한 것은?

① O — 점근적 하한 ② Θ — 점근적 상한과 하한 ③ Ω — 정확한 단위 연산 횟수 ④ Θ — 실제 실행 시간의 초 단위 측정값

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: O는 점근적 상한을 나타냅니다.
• ② 정답: 같은 g(n)의 상수배가 f(n)을 위아래에서 조이는 표기입니다.
• ③ 오답: Ω는 충분히 큰 입력에서의 점근적 하한입니다.
• ④ 오답: Θ는 기계별 초가 아니라 증가 차수를 표현합니다.

6. [6, 4, 7, 2]에 선택 정렬의 첫 단계를 수행한 결과는?

① [2, 4, 7, 6] ② [4, 6, 2, 7] ③ [4, 6, 7, 2] ④ [6, 4, 2, 7]

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 전체 미정렬 구간의 최솟값 2를 첫 원소 6과 교환합니다.
• ② 오답: 인접 비교 한 회전처럼 큰 값 7을 뒤로 보낸 결과입니다.
• ③ 오답: 첫 인접 쌍만 교환했을 뿐 최솟값을 선택하지 않았습니다.
• ④ 오답: 뒤쪽 한 쌍만 교환해 첫 위치가 확정되지 않았습니다.

7. [5, 1, 4, 2]를 버블 정렬로 왼쪽부터 한 회전한 뒤의 상태는?

① [1, 5, 4, 2] ② [1, 2, 4, 5] ③ [1, 4, 5, 2] ④ [1, 4, 2, 5]

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 첫 인접 쌍만 처리하고 회전을 끝냈습니다.
• ② 오답: 한 회전만으로 전체가 정렬되지는 않습니다.
• ③ 오답: 5와 2의 마지막 인접 비교를 빠뜨렸습니다.
• ④ 정답: 5가 1, 4, 2와 차례로 교환되어 맨 뒤에 확정됩니다.

8. “f(n)=10n+9가 n=5에서 n²/2+3n보다 느리므로 큰 입력에서도 계속 느리다”는 판단의 오류는?

① 두 식의 상수항을 먼저 비교하지 않았다 ② 작은 입력 한 지점만 보고 입력 증가에 따른 최고차항의 영향을 무시했다 ③ 두 함수가 같은 입력 크기를 사용했다 ④ 실제 시간이 아니라 단위 연산 횟수를 비교했다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 점근 비교에서는 상수항보다 최고차항이 중요합니다.
• ② 정답: 제곱 함수는 교차점 이후 선형 함수보다 더 빠르게 증가합니다.
• ③ 오답: 동일한 n에서 비교해야 두 수행량의 차이를 판단할 수 있습니다.
• ④ 오답: 기계 환경을 배제한 단위 연산 비교는 일반성을 높이는 방법입니다.

9. 이미 오름차순으로 정렬된 데이터에서 강의가 제시한 최선 수행 시간이 O(n)인 정렬의 묶음은?

① 선택 정렬만 ② 선택 정렬과 버블 정렬 ③ 버블 정렬과 삽입 정렬 ④ 선택 정렬과 삽입 정렬

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 선택 정렬은 입력 상태와 무관하게 최솟값 탐색을 반복합니다.
• ② 오답: 선택 정렬을 O(n) 묶음에 포함했습니다.
• ③ 정답: 이미 정렬된 경우 버블은 교환 없이 확인하고 삽입은 제자리임을 확인합니다.
• ④ 오답: 삽입 정렬은 맞지만 선택 정렬은 강의에서 O(n²)입니다.

10. 새 알고리즘의 정확성과 효율성을 검토하는 순서로 가장 타당한 것은?

① 작은 입력의 실행 시간만 재고 정답 여부를 추정한다 ② 점근 차수를 먼저 정한 뒤 문제 조건을 그 차수에 맞춘다 ③ 출력이 한 번 맞으면 종료성과 모든 유효 입력을 확인하지 않는다 ④ 성립 조건과 결과를 검증한 뒤 단위 연산을 세고 입력 증가에 따른 차수를 판정한다

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 한 환경과 작은 입력의 시간은 일반적인 정확성·확장성을 보장하지 않습니다.
• ② 오답: 복잡도는 실제 알고리즘의 반복 구조에서 도출해야 합니다.
• ③ 오답: 정확성은 모든 유효한 입력과 종료 조건을 고려해야 합니다.
• ④ 정답: 정확성 검증과 효율성 계산을 구분하면서 올바른 순서로 연결합니다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 개념 관계, 계산 과정, 직접 구성한 정렬 예제와 문제 해설은 학습자의 이해를 돕도록 구성하고 검토했습니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 컴퓨터과학개론 5강 「알고리즘(1)」 강의자료, 2024
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-09-06