방송대 방통대 컴퓨터과학개론 5강 - 알고리즘 (1) - 요약 노트 시험족보 예상문제 - 올에이클래스

컴퓨터과학개론 5강 - 알고리즘 (1)

컴퓨터로 문제를 해결하기 위한 절차인 알고리즘의 개념과 조건, 설계 및 분석 방법을 학습한다. 분할정복·동적 프로그래밍·욕심쟁이 방법의 차이를 살펴보고, 점근성능과 선택·버블·삽입 정렬의 동작 및 성능을 비교한다.

1. 알고리즘의 개념과 조건

문제 해결 절차로서의 알고리즘

컴퓨터과학은 컴퓨터를 활용하여 주어진 문제를 해결하는 학문이다. 문제를 해결하려면 입력으로 주어진 상태를 원하는 결과로 바꾸는 구체적인 풀이 방법이 필요하다. 방정식 2x+4=16에서 양변에 4를 빼고 2로 나누어 x=6을 구하는 것처럼, 문제 해결에는 일정한 순서와 규칙을 가진 절차가 존재한다.

알고리즘(algorithm)은 주어진 문제를 풀기 위한 명령어를 단계적으로 나열한 것이다. 음식의 재료와 조리 순서를 알려 주는 레시피가 맛있는 음식을 만드는 절차라면, 알고리즘은 입력에서 원하는 출력을 얻기 위한 문제 해결의 레시피라고 할 수 있다. 좋은 결과를 안정적으로 얻으려면 레시피가 분명해야 하듯이 알고리즘도 정확하고 효율적으로 구성되어야 한다.

알고리즘은 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 단순하며 컴퓨터가 수행할 수 있는 유한개의 명령을 순서에 따라 구성한 것이다.

알고리즘이 갖추어야 할 조건

조건	의미	확인할 질문
입출력	0개 이상의 외부 입력을 받아 1개 이상의 결과를 생성해야 한다.	무엇을 받아 무엇을 내놓는가?
명확성	각 명령은 모호하지 않고 단순하며 뜻이 분명해야 한다.	명령을 한 가지 의미로 해석할 수 있는가?
유한성	한정된 수의 단계를 거친 뒤 반드시 종료해야 한다.	언젠가 멈추는가?
유효성	모든 명령은 컴퓨터에서 실제로 수행할 수 있어야 한다.	실행 가능한 기본 연산으로 이루어졌는가?
효율성	실용적인 측면에서 시간과 기억공간을 지나치게 사용하지 않아야 한다.	같은 문제를 더 적은 자원으로 풀 수 있는가?

유한성은 알고리즘과 끝없이 반복되는 절차를 구분하는 중요한 조건이다. 또한 결과만 정확하다고 충분한 것은 아니다. 같은 결과를 내더라도 입력이 커질수록 지나치게 오랜 시간이 걸리거나 너무 많은 기억공간이 필요하다면 실제 프로그램에서는 사용하기 어렵다.

입력은 반드시 한 개 이상이어야 하는 것은 아니다. 외부 입력이 없는 알고리즘도 가능하지만, 알고리즘은 문제에 대한 결과인 출력을 하나 이상 생성해야 한다.

2. 알고리즘의 생성과 표현

알고리즘 생성의 네 단계

알고리즘은 단순히 아이디어를 떠올리는 것으로 완성되지 않는다. 문제 해결 방법을 만들고, 다른 사람이 이해할 수 있는 형태로 나타내고, 올바른지 증명하며, 필요한 자원의 양을 평가하는 과정을 거쳐야 한다.

단계	주요 내용
설계	문제의 조건과 입력·출력을 분석하여 해결 방법과 처리 순서를 만든다.
표현·기술	일상 언어, 의사코드, 순서도 등으로 해결 절차를 명확하게 나타낸다.
정확성 검증	모든 유효한 입력에 대해 알고리즘이 올바른 결과를 내는지 확인한다.
효율성 분석	수행 시간과 기억공간이 입력 크기에 따라 어떻게 증가하는지 분석한다.

알고리즘의 표현 방법

예를 들어 n개의 숫자의 합을 구하는 알고리즘은 “데이터를 입력받고, 합을 저장할 변수를 0으로 초기화한 다음, 처리하지 않은 데이터가 있는 동안 값을 더하고, 마지막에 합을 출력한다”라고 일상 언어로 설명할 수 있다. 같은 절차를 의사코드로 표현하면 다음과 같다.

sum = 0
while (데이터가 더 존재)
  sum = sum + 데이터(i)
print(sum)

일상 언어는 이해하기 쉽지만 표현이 길어지거나 모호해질 수 있다. 의사코드(pseudocode)는 프로그래밍 언어와 비슷한 형식으로 핵심 연산과 제어 흐름을 나타내며, 특정 언어의 문법에 얽매이지 않는다. 순서도(flowchart)는 시작과 종료, 처리, 판단, 흐름을 도형과 화살표로 나타내므로 전체 제어 구조를 시각적으로 파악하기 좋다.

표현 방법이 달라도 입력을 처리하는 단계와 결과는 같아야 한다. 알고리즘은 프로그램 코드 자체가 아니라, 코드로 구현할 수 있는 논리적인 문제 해결 절차이다.

3. 자료구조와 탐색 알고리즘

자료구조와 알고리즘의 관계

자료구조(data structure)는 데이터 사이의 논리적 관계를 표현하고 조직하는 방법이다. 대표적인 자료구조에는 배열, 연결 리스트, 스택, 큐, 트리, 그래프가 있다. 같은 알고리즘도 어떤 자료구조를 사용하는지에 따라 데이터 접근과 갱신에 필요한 시간이 달라질 수 있다.

효율적인 프로그램 = 적절한 자료구조 + 효율적인 알고리즘

자료구조에 대한 고려 없이 알고리즘만 선택하거나, 알고리즘의 처리 방식과 맞지 않는 자료구조를 고르면 전체 프로그램의 효율이 떨어진다. 따라서 문제의 데이터가 어떤 관계를 갖고 어떤 연산이 자주 수행되는지를 함께 살펴야 한다.

같은 문제를 푸는 서로 다른 알고리즘

주어진 수열에서 최댓값을 찾는 방법도 하나만 있는 것은 아니다. 첫 번째 방법은 현재까지의 최댓값과 다음 값을 차례로 비교하는 선형적인 방식이고, 다른 방법은 값들을 쌍으로 비교한 뒤 승자끼리 다시 비교하는 토너먼트 형태의 방식이다. 둘 다 최댓값을 찾을 수 있지만 비교의 구성과 중간 결과의 활용 방식이 다르다.

알고리즘의 효율은 그림의 모양이나 직관만으로 판단해서는 안 된다. 입력 크기가 커질 때 필요한 비교·연산 횟수를 계산하고, 공간 사용량과 구현 목적까지 분석해야 한다.

순차 탐색과 이진 탐색

구분	순차 탐색	이진 탐색
기본 방법	처음부터 원소를 하나씩 확인한다.	중간 원소와 비교하여 탐색 범위를 절반씩 줄인다.
데이터 조건	정렬 여부와 관계없이 적용할 수 있다.	데이터가 정렬되어 있어야 한다.
특징	단순하지만 데이터가 많으면 비교가 늘어난다.	정렬된 데이터에서 빠르게 범위를 축소한다.

뒤집힌 카드처럼 순서를 알 수 없는 자료에서 원하는 카드를 찾을 때는 순차 탐색이 자연스럽다. 반면 오름차순으로 나열된 카드에서는 중간값을 기준으로 찾는 값이 왼쪽에 있는지 오른쪽에 있는지를 판단하여 절반을 제외하는 이진 탐색을 사용할 수 있다.

4. 대표적인 알고리즘 설계 기법

문제의 종류와 제약 조건은 매우 다양하므로 모든 문제에 통용되는 단 하나의 설계 기법은 존재하지 않는다. 강의에서는 대표적인 설계 기법으로 분할정복, 동적 프로그래밍, 욕심쟁이 방법을 다룬다.

분할정복 방법

분할정복(divide-and-conquer)은 문제를 더 이상 나눌 수 없을 때까지 둘 이상의 작은 문제로 순환적으로 분할하고, 작은 문제의 해를 구한 뒤 이를 결합하여 원래 문제의 해를 만드는 하향식 접근 방법이다. 분할된 작은 문제는 원래 문제와 성격이 같고 입력 크기만 작으며, 서로 독립적이라는 특징이 있다.

단계	설명
분할	주어진 문제를 여러 개의 작은 문제로 나눈다.
정복	작은 문제를 순환적으로 풀고, 충분히 작아지면 순환 호출 없이 직접 해를 구한다.
결합	작은 문제의 해를 합쳐 원래 문제의 해를 만든다. 문제에 따라 결합 단계가 없을 수도 있다.

퀵 정렬, 합병 정렬, 이진 탐색은 분할정복의 대표적인 예이다. 이진 탐색은 중간값과의 비교 결과에 따라 탐색해야 할 절반만 남기므로 별도의 해 결합 단계가 필요하지 않다.

동적 프로그래밍 방법

동적 프로그래밍(dynamic programming)은 최댓값이나 최솟값을 구하는 최적화 문제에서 작은 소문제의 해를 먼저 구해 표에 저장하고, 저장한 결과를 이용하여 더 큰 문제의 해를 점진적으로 만드는 상향식 접근 방법이다. 분할정복과 달리 소문제가 서로 독립적일 필요가 없으며, 동일한 소문제가 반복될 때 계산 결과를 재사용할 수 있다.

플로이드 알고리즘처럼 모든 정점 쌍의 최단 경로를 구하는 문제에서, 중간 정점의 범위를 조금씩 넓히며 앞에서 계산한 최단거리 정보를 활용하는 것이 동적 프로그래밍의 예이다.

욕심쟁이 방법

욕심쟁이 방법(greedy method)은 해를 구하는 일련의 선택 과정에서 앞뒤 단계의 선택과 관계없이, 각 단계에서 가장 좋다고 판단되는 국부적인 최적해를 선택한다. 이러한 선택을 이어 가면 전체적인 최적해를 얻을 수 있으리라고 기대하는 방법이다.

욕심쟁이 방법은 적용 범위가 제한적이지만 구조가 간단하고 강력한 경우가 있다. 거스름돈 문제와 배낭 문제는 각 단계에서 어떤 기준으로 가장 유리한 선택을 하는지 보여 주는 대표적인 예이다.

매 단계의 최선이 항상 전체 최선을 보장하는 것은 아니다. 욕심쟁이 방법은 국부적 선택이 전체 최적해로 이어지는 성질을 가진 문제에 적용해야 한다.

기법	접근 방향과 핵심	소문제 관계	대표 예
분할정복	하향식으로 나누고 작은 문제의 해를 결합	서로 독립적	퀵 정렬, 합병 정렬, 이진 탐색
동적 프로그래밍	상향식으로 작은 해를 저장·재사용	중복될 수 있음	플로이드 알고리즘
욕심쟁이	각 단계의 국부적 최적 선택을 즉시 확정	선택을 되돌리지 않음	거스름돈, 배낭 문제

5. 욕심쟁이 방법의 적용 사례

거스름돈 문제

거스름돈 문제는 고객에게 돌려줄 금액이 T만큼 있을 때 동전의 개수를 최소로 하여 거스름돈을 주는 방법을 찾는 문제이다. 동전의 종류가 500원, 100원, 50원, 10원이고 770원을 돌려준다면, 각 단계에서 남은 금액보다 크지 않은 가장 큰 동전을 선택한다.

770원 → 500원 선택, 270원 남음 → 100원 2개 선택, 70원 남음 → 50원 선택, 20원 남음 → 10원 2개 선택

이 예에서는 500원 1개, 100원 2개, 50원 1개, 10원 2개로 총 6개의 동전을 사용한다. 큰 동전부터 고르는 국부적인 선택이 최소 동전 수라는 전체 결과로 이어진다.

배낭 문제

배낭 문제는 최대 용량이 M인 배낭과 n개의 물체가 있을 때, 배낭의 용량을 넘지 않으면서 담은 물체의 이익 합이 최대가 되도록 선택하는 문제이다. 각 물체 i에는 무게 wi와 이익 pi가 있다. 강의의 가정처럼 물체를 쪼개어 일부만 넣을 수 있다면 단위 무게당 이익 pi/wi이 큰 물체부터 담는 욕심쟁이 전략을 사용할 수 있다.

물체	무게	이익	단위 무게당 이익	선택 순서
1	4kg	14	3.5	3번째
2	3kg	15	5	1번째
3	5kg	20	4	2번째
4	3kg	9	3	4번째

용량이 10kg이면 먼저 물체 2의 3kg을 담고, 다음으로 물체 3의 5kg을 담는다. 남은 용량은 2kg이므로 물체 1의 절반을 담아 이익 7을 얻는다. 총이익은 15+20+7=42이다.

물체를 쪼갤 수 있는 배낭 문제에서는 단위 무게당 이익이 큰 순서로 선택한다. 단순히 전체 이익이나 가벼운 무게만을 기준으로 삼는 것이 아니다.

6. 알고리즘의 정확성과 효율성 분석

정확성 분석과 효율성 분석

정확성 분석은 유효한 입력과 유한한 수행 시간이 주어졌을 때 알고리즘이 정확한 결과를 생성하는지를 확인하는 것이다. 몇 개의 예를 실행해 보는 것만으로 모든 입력에 대한 정확성이 보장되지는 않으므로 다양한 수학적 기법을 이용한 이론적 증명이 필요하다.

효율성 분석은 알고리즘을 수행하는 데 필요한 컴퓨터 자원의 양을 측정한다. 메모리의 정적 공간과 동적 공간을 다루는 공간 복잡도(space complexity), 수행 시간을 다루는 시간 복잡도(time complexity)로 나뉜다.

분석 대상	핵심 질문
정확성	모든 유효한 입력에서 올바른 결과를 만들고 종료하는가?
공간 복잡도	알고리즘 수행에 필요한 기억공간은 입력 크기에 따라 얼마나 증가하는가?
시간 복잡도	알고리즘의 기본 연산 횟수는 입력 크기에 따라 얼마나 증가하는가?

실제 시간 대신 연산 횟수를 사용하는 이유

알고리즘을 컴퓨터에서 실행하여 완료될 때까지 걸린 실제 시간을 측정할 수도 있다. 그러나 실제 시간은 컴퓨터의 종류와 속도, 프로그래밍 언어, 구현 방법, 컴파일러와 운영체제 등에 영향을 받는다. 따라서 알고리즘 자체의 성능을 비교하기에는 객관성이 부족하다.

시간 복잡도에서는 알고리즘이 수행하는 단위 연산의 횟수를 입력 크기의 함수로 표현한다. 입력 데이터의 상태에 따라 수행 횟수가 달라질 수 있으므로 평균 수행 시간, 최선 수행 시간, 최악 수행 시간을 구분하기도 한다.

입력 크기와 수행 시간 함수

배열 a[0..n-1]의 합과 평균을 구하는 알고리즘을 생각해 보자. 초기화, 반복 조건 검사, 덧셈, 인덱스 증가, 나눗셈, 출력의 수행 횟수를 합하면 강의 예제에서는 f(n)=3n+5가 된다. 여기서 입력 크기는 배열에 들어 있는 데이터의 개수 n이다.

시간 복잡도는 초 단위의 실제 실행 시간이 아니라, 입력 크기 n에 따라 증가하는 기본 연산 횟수의 함수로 분석한다.

7. 점근성능과 점근 표기법

점근성능의 의미

점근성능(asymptotic performance)은 입력 크기 n이 충분히 커질 때 결정되는 알고리즘의 성능이다. 예를 들어 f1(n)=10n+9와 f2(n)=n²/2+3n을 비교하면 작은 n에서는 두 번째 함수의 값이 더 작을 수 있지만, n이 커지면 제곱항이 빠르게 증가하여 첫 번째 함수보다 커진다.

다항식의 수행 시간에서 입력 크기가 충분히 클 때 가장 큰 영향을 미치는 것은 최고차항이다. 계수와 낮은 차수의 항을 제외하고 증가율을 간결하게 표현하면 알고리즘 사이의 비교가 쉬워지고 구현 환경에 덜 의존하는 성능 평가가 가능하다.

Big-oh, Big-omega, Big-theta

표기	의미	정의의 핵심
O(g(n))	점근적 상한	충분히 큰 n에서 f(n) ≤ c·g(n)이 되는 양의 상수 c가 존재한다.
Ω(g(n))	점근적 하한	충분히 큰 n에서 f(n) ≥ c·g(n)이 되는 양의 상수 c가 존재한다.
Θ(g(n))	점근적 상하한	충분히 큰 n에서 c₁g(n) ≤ f(n) ≤ c₂g(n)이 성립한다.

Θ(g(n))은 함수의 증가율을 위와 아래에서 동시에 제한하므로 f(n)=O(g(n))이면서 f(n)=Ω(g(n))임을 뜻한다. 예를 들어 f(n)=3n+3은 충분히 큰 n에서 n의 상수배 사이에 놓이므로 Θ(n)이다. f(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ⁿ)

왼쪽으로 갈수록 입력 크기가 증가할 때 수행 시간의 증가가 완만하여 일반적으로 효율적이고, 오른쪽으로 갈수록 증가가 가파르다. 상수 시간은 입력 크기와 관계없이 일정하며, 로그 시간은 입력이 크게 늘어도 완만하게 증가한다. 선형 시간은 입력 크기에 비례하고, 제곱·세제곱·지수 시간은 큰 입력에서 급격히 증가한다.

점근 표기법은 실제 실행 시간을 정확히 예측하는 식이 아니라 입력이 매우 커질 때의 증가율을 비교하는 도구이다. 같은 차수의 알고리즘도 구현과 입력 특성에 따라 실제 시간은 달라질 수 있다.

8. 정렬의 기본 개념과 분류

정렬과 저장 위치

정렬(sort)은 데이터를 일정한 기준에 따라 오름차순이나 내림차순으로 나열하는 작업이다. 정렬 수행 시점에 데이터가 어디에 저장되어 있는지에 따라 내부 정렬과 외부 정렬로 나뉜다.

구분	설명
내부 정렬	모든 데이터를 주기억장치에 적재한 뒤 정렬하는 방식이다.
외부 정렬	전체 데이터를 주기억장치에 담을 수 없어 보조기억장치에 저장하고, 일부를 번갈아 주기억장치로 가져와 정렬하는 방식이다.

내부 정렬의 분류

내부 정렬은 키값을 서로 비교하는 비교 기반 정렬과 키의 분포나 자릿값을 이용하는 분포 기반 정렬로 구분할 수 있다. 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬은 비교 기반에 속하고, 계수 정렬과 기수 정렬은 분포 기반에 속한다.

분류	알고리즘	강의에서 제시한 대표 성능
비교 기반	선택 정렬	O(n²)
	버블 정렬	O(n²)
	삽입 정렬	O(n²)
	퀵 정렬	O(n log n) 계열
	합병 정렬
분포 기반	계수 정렬	O(n) 계열
	기수 정렬

강의의 기본 가정에서는 n개의 양의 정수 키가 배열 A[0..n-1]에 저장되어 있으며, i<j이면 A[i]≤A[j]가 되도록 오름차순 정렬한다.

9. 선택 정렬, 버블 정렬, 삽입 정렬

선택 정렬

선택 정렬(selection sort)은 정렬되지 않은 데이터 중 가장 작은 값을 선택하여 미정렬 부분의 첫 번째 원소와 교환하는 과정을 반복한다. 첫 단계가 끝나면 전체 최솟값이 맨 앞에 놓이고, 다음 단계에서는 그다음 위치부터 최솟값을 찾는다. n개의 데이터에서는 이 과정을 n-1번 수행하면 정렬이 완료된다.

예를 들어 60, 20, 70, 10, 80, 30, 50, 40에서 10을 찾아 60과 교환하고, 남은 부분에서 20, 30, 40의 순서로 가장 작은 값을 확정한다. 입력이 이미 정렬되어 있어도 미정렬 부분의 최솟값을 계속 찾아야 하므로 수행 시간은 입력 상태에 민감하지 않고 언제나 O(n²)이다.

버블 정렬

버블 정렬(bubble sort)은 왼쪽부터 인접한 두 데이터를 차례대로 비교하여 왼쪽 값이 더 크면 자리를 바꾸는 과정을 반복한다. 한 번의 전체 비교가 끝나면 가장 큰 값이 오른쪽 끝으로 이동한다. 다음 단계에서는 이미 확정된 마지막 원소를 제외하고 같은 작업을 반복한다.

버블 정렬의 성능은 입력 데이터의 상태에 영향을 받는다. 교환이 한 번도 발생하지 않으면 이미 정렬되었음을 확인하고 종료하도록 구현한 경우, 이미 오름차순으로 정렬된 입력의 최선 성능은 O(n)이다. 역순 입력에서는 인접 원소의 비교와 교환이 반복되어 최악 성능이 O(n²)이 된다. 선택 정렬보다 데이터 교환이 많이 발생할 수 있다는 점도 중요하다.

삽입 정렬

삽입 정렬(insertion sort)은 데이터를 하나씩 뽑아 왼쪽의 정렬 부분에서 알맞은 위치를 찾고, 그 위치에 삽입하여 정렬 부분을 확장하는 방식이다. 입력 배열을 정렬 부분과 미정렬 부분으로 나눈 뒤, 미정렬 부분의 가장 왼쪽 데이터를 선택한다. 선택한 값보다 큰 정렬 부분의 원소를 오른쪽으로 이동시켜 자리를 만들고 값을 삽입한다.

예를 들어 정렬 부분이 10, 30, 40이고 뽑은 값이 20이면 40과 30을 오른쪽으로 한 칸씩 이동한 뒤 10 다음에 20을 넣는다. 입력이 이미 정렬되어 있으면 각 원소가 현재 자리에 그대로 들어가므로 최선 성능은 O(n)이다. 역순 입력에서는 매번 정렬 부분의 모든 값을 이동해야 하므로 최악 성능은 O(n²)이다.

정렬	핵심 동작	입력 상태의 영향	최선	최악
선택 정렬	미정렬 부분의 최솟값을 선택하여 앞자리와 교환	민감하지 않음	O(n²)	O(n²)
버블 정렬	인접한 값을 비교·교환하여 큰 값을 뒤로 이동	영향을 받음	O(n)	O(n²)
삽입 정렬	뽑은 값을 정렬 부분의 제자리에 삽입	영향을 받음	O(n)	O(n²)

선택 정렬은 ‘최솟값 선택’, 버블 정렬은 ‘인접 원소 비교·교환’, 삽입 정렬은 ‘정렬 부분의 제자리에 삽입’으로 구분한다.

핵심 개념 정리

• 알고리즘은 문제 해결을 위해 모호하지 않고 수행 가능한 유한개의 명령을 순서대로 구성한 것이다.
• 알고리즘의 조건은 입출력, 명확성, 유한성, 유효성, 효율성이다.
• 알고리즘 생성 과정은 설계, 표현·기술, 정확성 검증, 효율성 분석으로 이루어진다.
• 효율적인 프로그램을 만들려면 문제에 맞는 자료구조와 알고리즘을 함께 선택해야 한다.
• 순차 탐색은 원소를 하나씩 확인하고, 이진 탐색은 정렬된 데이터의 범위를 절반씩 줄인다.
• 분할정복은 독립적인 작은 문제로 나누어 풀고 결합하는 하향식 방법이다.
• 동적 프로그래밍은 작은 문제의 해를 저장하고 재사용하여 큰 문제를 푸는 상향식 방법이다.
• 욕심쟁이 방법은 각 단계에서 국부적으로 가장 좋은 선택을 확정한다.
• 알고리즘 분석은 정확성 분석과 효율성 분석으로 나뉘며, 효율성에는 공간 복잡도와 시간 복잡도가 있다.
• 점근성능은 입력 크기가 충분히 커질 때의 증가율이며, 최고차항이 가장 큰 영향을 미친다.
• O는 점근적 상한, Ω는 점근적 하한, Θ는 점근적 상하한을 나타낸다.
• 내부 정렬은 데이터를 주기억장치에 적재하여 처리하고, 외부 정렬은 보조기억장치와 주기억장치를 번갈아 사용한다.
• 선택 정렬은 항상 O(n²)이며, 버블·삽입 정렬은 이미 정렬된 입력에서 최선 O(n), 역순 입력에서 최악 O(n²)이다.

최종 정리: 알고리즘 학습의 핵심은 문제를 푸는 절차를 만드는 것에서 끝나지 않는다. 절차가 정확하고 종료하며 실행 가능한지 확인하고, 입력 크기가 증가할 때 시간과 공간이 어떻게 변하는지 분석해야 한다. 설계 기법과 정렬 알고리즘은 이름보다 문제를 나누는 방식, 선택 기준, 데이터 이동 과정과 복잡도의 차이를 중심으로 이해해야 한다.

예상문제 20선

1. 알고리즘의 정의로 가장 적절한 것은?

① 문제의 결과를 만들기 위해 수행 가능한 유한개의 명령을 순서대로 구성한 것 ② 컴퓨터에 저장된 모든 데이터의 집합 ③ 특정 프로그래밍 언어의 문법만을 모은 것 ④ 종료 조건 없이 명령을 반복하는 것

정답입니다.

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

정답 및 해설 보기

정답: ①
알고리즘은 문제 해결을 위해 명확하고 수행 가능한 유한개의 명령을 순서대로 구성한 절차이다.

2. 알고리즘의 유한성에 대한 설명은?

① 외부 입력이 반드시 한 개여야 한다. ② 한정된 수의 단계를 거친 뒤 반드시 종료해야 한다. ③ 모든 명령을 자연어로만 표현해야 한다. ④ 출력의 개수가 입력보다 많아야 한다.

정답입니다.

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

정답 및 해설 보기

정답: ②
유한성은 알고리즘이 무한히 계속되지 않고 유한한 단계 후에 끝나야 한다는 조건이다.

3. 알고리즘 생성 단계의 올바른 순서는?

① 효율성 분석 → 설계 → 정확성 검증 → 표현 ② 표현 → 정확성 검증 → 설계 → 효율성 분석 ③ 설계 → 표현·기술 → 정확성 검증 → 효율성 분석 ④ 정확성 검증 → 효율성 분석 → 표현 → 설계

정답입니다.

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

정답 및 해설 보기

정답: ③
해결 방법을 설계하고 표현한 뒤 정확성을 검증하고 마지막으로 필요한 자원을 분석한다.

4. 효율적인 프로그램을 구성하는 핵심 요소의 결합은?

① 입력 장치 + 출력 장치 ② 운영체제 + 컴파일러 ③ 의사코드 + 순서도 ④ 적절한 자료구조 + 효율적인 알고리즘

정답입니다.

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

정답 및 해설 보기

정답: ④
데이터 조직 방법과 처리 절차는 서로 영향을 주므로 자료구조와 알고리즘을 함께 고려해야 한다.

5. 이진 탐색을 적용하기 위한 기본 조건은?

① 데이터가 일정한 순서로 정렬되어 있어야 한다. ② 데이터가 반드시 연결 리스트에 있어야 한다. ③ 찾는 값이 첫 번째 원소여야 한다. ④ 모든 원소가 같은 값이어야 한다.

정답입니다.

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

정답 및 해설 보기

정답: ①
이진 탐색은 중간값과 비교하여 한쪽 절반을 제외하므로 데이터가 정렬되어 있어야 한다.

6. 분할정복 방법의 세 단계는?

① 입력, 출력, 종료 ② 분할, 정복, 결합 ③ 선택, 교환, 삽입 ④ 저장, 삭제, 출력

정답입니다.

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

정답 및 해설 보기

정답: ②
문제를 작은 문제로 나누고 각각을 해결한 후 필요한 경우 작은 해들을 결합한다.

7. 동적 프로그래밍의 특징으로 옳은 것은?

① 모든 소문제는 반드시 서로 독립적이어야 한다. ② 매 단계에서 가장 큰 값만 즉시 선택한다. ③ 작은 문제의 해를 저장하고 이용해 더 큰 문제의 해를 만든다. ④ 입력 크기와 관계없이 항상 한 번만 계산한다.

정답입니다.

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

정답 및 해설 보기

정답: ③
동적 프로그래밍은 소문제의 해를 표 등에 저장해 중복 계산을 피하고 큰 문제를 점진적으로 해결한다.

8. 욕심쟁이 방법에 대한 설명으로 가장 적절한 것은?

① 가능한 모든 해를 반드시 생성한다. ② 작은 문제의 해를 모두 표에 저장한다. ③ 문제를 항상 정확히 두 부분으로 나눈다. ④ 각 단계에서 국부적으로 가장 좋다고 판단되는 해를 선택한다.

정답입니다.

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

정답 및 해설 보기

정답: ④
욕심쟁이 방법은 현재 단계의 최선 선택을 확정하며 전체 최적해를 얻기를 기대하는 기법이다.

9. 강의의 배낭 문제에서 물체를 쪼갤 수 있을 때 우선 선택 기준은?

① 단위 무게당 이익이 큰 순서 ② 무게가 무거운 순서 ③ 물체 번호가 작은 순서 ④ 전체 이익이 작은 순서

정답입니다.

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

정답 및 해설 보기

정답: ①
제한된 용량에서 이익을 최대화하기 위해 pᵢ/wᵢ가 큰 물체부터 담는다.

10. 공간 복잡도가 측정하는 것은?

① 출력 결과의 정확도 ② 알고리즘 수행에 필요한 기억공간의 양 ③ 프로그래밍 언어의 문법 수 ④ 입력 장치의 처리 속도

정답입니다.

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

정답 및 해설 보기

정답: ②
공간 복잡도는 정적 공간과 동적 공간을 포함하여 알고리즘이 요구하는 메모리 자원을 분석한다.

11. 시간 복잡도를 실제 초 단위 시간 대신 입력 크기의 함수로 분석하는 주된 이유는?

① 모든 알고리즘의 실제 시간은 항상 같기 때문이다. ② 입력 데이터의 개수는 성능과 관계없기 때문이다. ③ 실제 시간은 컴퓨터·언어·구현 환경의 영향을 받기 때문이다. ④ 기본 연산은 컴퓨터에서 수행할 수 없기 때문이다.

정답입니다.

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

정답 및 해설 보기

정답: ③
실행 환경의 영향을 줄이고 알고리즘 자체의 증가율을 비교하기 위해 기본 연산 횟수를 입력 크기의 함수로 나타낸다.

12. f(n)=2n³+3n²+n+10의 Big-oh 표기로 가장 적절한 것은?

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

정답입니다.

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

정답 및 해설 보기

정답: ④
입력 크기가 충분히 커지면 최고차항인 2n³이 증가율을 지배한다.

13. 점근적 상한을 나타내는 표기법은?

① Big-oh, O ② Big-omega, Ω ③ Big-theta, Θ만 ④ 분할정복

정답입니다.

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

정답 및 해설 보기

정답: ①
O(g(n))은 충분히 큰 입력에서 함수의 증가율을 위쪽에서 제한하는 점근적 상한이다.

14. 다음 중 수행 시간의 증가가 가장 빠른 것은?

① O(log n) ② O(2ⁿ) ③ O(n) ④ O(n log n)

정답입니다.

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

정답 및 해설 보기

정답: ②
지수 시간 O(2ⁿ)은 로그·선형·로그 선형 시간보다 입력 증가에 따른 수행 시간 증가가 훨씬 가파르다.

15. 모든 데이터를 주기억장치에 적재하여 정렬하는 방식은?

① 외부 탐색 ② 동적 정렬 ③ 내부 정렬 ④ 순차 탐색

정답입니다.

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

정답 및 해설 보기

정답: ③
내부 정렬은 전체 데이터를 주기억장치에 올려 놓고 정렬할 수 있을 때 사용하는 방식이다.

16. 선택 정렬의 핵심 동작은?

① 인접 원소만 비교하여 큰 값을 뒤로 보낸다. ② 중간값을 기준으로 탐색 범위를 반으로 줄인다. ③ 뽑은 값을 정렬 부분의 제자리에 삽입한다. ④ 미정렬 부분의 최솟값을 선택하여 첫 원소와 교환한다.

정답입니다.

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

정답 및 해설 보기

정답: ④
선택 정렬은 각 단계에서 남은 데이터 중 가장 작은 값을 찾아 앞쪽의 확정 위치로 옮긴다.

17. 선택 정렬의 수행 시간에 관한 설명으로 옳은 것은?

① 입력 상태와 관계없이 대체로 O(n²)이다. ② 이미 정렬된 입력에서는 항상 O(1)이다. ③ 역순 입력에서 O(log n)이다. ④ 데이터 개수와 무관하게 비교를 한 번만 한다.

정답입니다.

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

정답 및 해설 보기

정답: ①
입력이 정렬되어 있어도 매 단계 미정렬 부분에서 최솟값을 찾아야 하므로 입력 상태에 민감하지 않다.

18. 버블 정렬의 설명으로 옳은 것은?

① 항상 미정렬 부분의 최솟값을 한 번에 찾는다. ② 인접한 두 값을 비교하여 왼쪽 값이 크면 교환한다. ③ 정렬된 입력에서도 반드시 모든 교환이 발생한다. ④ 비교하지 않고 자릿수만으로 정렬한다.

정답입니다.

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

정답 및 해설 보기

정답: ②
버블 정렬은 인접 원소를 차례로 비교·교환하여 큰 값이 오른쪽으로 이동하게 한다.

19. 이미 오름차순으로 정렬된 입력을 개선된 버블 정렬로 처리할 때 기대할 수 있는 최선 시간은?

① O(1) ② O(log n) ③ O(n) ④ O(n³)

정답입니다.

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

정답 및 해설 보기

정답: ③
한 번의 순회에서 교환이 없음을 확인하면 정렬 상태를 알아내고 종료할 수 있어 최선 시간은 선형이다.

20. 삽입 정렬에서 정렬 부분이 10, 30, 40이고 다음 데이터가 20일 때의 처리로 옳은 것은?

① 20을 맨 뒤에 그대로 둔다. ② 10을 삭제하고 20으로 바꾼다. ③ 최솟값 10과 20만 교환한다. ④ 30과 40을 오른쪽으로 이동하고 10과 30 사이에 20을 삽입한다.

정답입니다.

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

정답 및 해설 보기

정답: ④
삽입 정렬은 뽑은 값보다 큰 원소를 오른쪽으로 이동해 제자리를 만든 뒤 값을 삽입한다.