응용정보기술자시험 과목A 6회: 의사코드·재귀·계산량·상태전이

개정일: 2026-10-20 범위: 2026년 시험 대비, IPA 「応用情報技術者試験（レベル3）シラバス Ver.7.2」 기준 안내: 시험 범위·형식은 바뀔 수 있으므로 응시 전에 반드시 IPA의 최신 공식 정보를 확인하세요. 이 글은 학습 보조 자료이며 합격을 보장하지 않습니다. 이 글은 IPA가 작성하거나 승인한 자료가 아닙니다.

선수 지식: 탐색·정렬 알고리즘의 개요와 그 계산량 비교는 5회에서 다뤘습니다. 이번 회에서는 그 내용을 반복하지 않고, 어떤 알고리즘이든 손으로 따라가고(추적), 멈추는지 확인하고, 비용을 세고, 상태 변화로 읽는 방법에 집중합니다.

---

1. 학습 인덱스와 목표

절	내용	다 읽은 뒤 할 수 있어야 하는 것
2	용어 대응표	한국어·일본어·영어 용어를 서로 바꿔 읽을 수 있다
3	이 글의 의사코드 표기	대입(←)과 같음 비교(=)를 구별하고 반복 범위를 정확히 읽는다
4	추적 방법 · 예제 1	체크포인트를 정해 추적표를 한 줄씩 정확하게 채운다
5	반복 종료 · 예제 2	초기화·조건·갱신을 점검하고, 유클리드 호제법을 추적한다
6	재귀 · 예제 3	호출(내려가기)과 반환(되돌아오기)을 분리해 추적한다
7	계산량 · 예제 4	정확한 실행 횟수를 세고 Θ/O로 요약한다
8	상태 전이 · 예제 5	상태 전이표를 읽고 입력열에 대한 상태 변화를 추적한다
9	오리지널 연습문제 5문항	위 다섯 가지 기술을 각각 문제에 적용한다
10–13	퀵시트·함정·자가 점검·복습	핵심을 짧게 복습하고 약점을 점검한다

---

2. 용어 대응표

한국어	日本語	English
의사코드	擬似言語（擬似コード）	pseudocode
대입	代入	assignment
같음 비교	等価比較（等しいかの比較）	equality comparison
조건	条件	condition
분기	分岐（選択）	branch
반복(루프)	繰返し（ループ）	loop
반복 1회(이터레이션)	繰返し1回分（反復）	iteration
반복 조건(계속 조건)	繰返し条件（継続条件）	loop condition
종료 조건	終了条件	termination condition
초기화	初期化	initialization
갱신	更新	update
추적표	トレース表	trace table
상태	状態	state
상태 전이	状態遷移	state transition
상태 전이표 / 상태 전이도	状態遷移表 / 状態遷移図	transition table / transition diagram
재귀 호출	再帰呼出し	recursive call
기저 사례(종료 사례)	基底部（再帰の終了条件）	base case
호출 스택	呼出しスタック（コールスタック）	call stack
반환값	戻り値（返却値）	return value
시간 계산량 / 공간(영역) 계산량	時間計算量 / 領域計算量	time complexity / space complexity
정확한 연산 횟수	正確な演算回数（実行回数）	exact operation count
빅오 표기	オーダー記法（O記法）	Big-O notation

---

3. 이 글에서만 쓰는 의사코드 표기

아래 표기는 이 글의 설명과 연습문제를 위해 정한 것이며, IPA 시험의 공식 표기와 똑같다고 주장하지 않습니다. 실제 시험 문제는 기호를 다르게 정의할 수 있고, 그 경우에는 문제에 적힌 정의가 항상 우선합니다.

표기	의미
x ← e	식 e의 값을 계산한 뒤 변수 x에 넣는다(대입).
a = b	a와 b가 같은지 비교한다(참/거짓). 대입이 아니다.
≠, <, ≤, >, ≥	비교 연산자.
a div b	정수 나눗셈의 몫. 이 글에서는 음이 아닌 정수에만 쓴다. 예: 7 div 2 = 3.
a mod b	정수 나눗셈의 나머지. 이 글에서는 음이 아닌 a와 양의 b에만 쓴다. 예: 48 mod 18 = 12.
for i ← a to b	i를 a부터 b까지 1씩 늘리며 반복한다. 양 끝 포함. a > b이면 한 번도 실행하지 않는다.
while 조건	전치 판정(pre-test): 매 반복을 시작하기 전에 조건을 평가하고, 참인 동안 계속한다. 처음부터 거짓이면 본문은 0회 실행된다.
if 조건 … else …	조건이 참이면 첫 블록, 거짓이면 else 블록을 실행한다.
A[i]	배열 A의 i번째 요소. 이 글에서는 첨자가 1부터 시작(A[1]이 첫 요소)한다고 정한다.
return e	현재 함수 호출을 끝내고 e의 값을 호출한 쪽으로 돌려준다.
output e	e의 값을 출력한다.
들여쓰기	같은 들여쓰기 깊이의 문장들이 하나의 블록을 이룬다.

이 글의 예제와 문제는 and/or 같은 복합 조건을 쓰지 않으므로, 단락 평가(short-circuit evaluation)를 가정하지 않습니다.

---

4. 추적(트레이스)하는 방법

손 추적은 “대충 머릿속으로 돌리기”가 아니라 규칙에 따른 기록입니다. 다음 순서를 지키면 실수가 크게 줄어듭니다.

1. 초기 상태를 고정한다. 반복에 들어가기 전 모든 변수의 값을 첫 줄(초기 행)에 적습니다.
2. 한 번에 한 문장(또는 한 반복)씩 실행한다. 여러 문장을 머릿속에서 한꺼번에 처리하지 않습니다.
3. 체크포인트를 정의하고, 그 시점에서만 기록한다. 예: “반복 본문의 모든 문장을 실행한 직후”. 표의 한 행이 언제의 상태인지를 먼저 정해야 합니다.
4. 옛 값과 새 값을 구분한다. total ← total + x에서 오른쪽의 x는 이 문장을 실행하는 순간의 값입니다. 같은 반복 안에서 뒤에 오는 x ← 2 * x는 아직 반영되지 않았습니다.
5. 조건 판정도 기록한다. while 조건이 참/거짓이 된 시점이 반복 횟수를 결정합니다.
6. 출력과 최종 상태를 확인한다. 반복을 빠져나온 뒤 무엇이 출력되는지, 각 변수의 마지막 값이 무엇인지 따로 적습니다.

예제 1: 변수 추적

x ← 1
total ← 0
while x ≤ 8
    total ← total + x
    x ← 2 * x
output total

행의 의미: 반복 k행 = “k번째 반복에서 total ← total + x와 x ← 2 * x를 둘 다 실행한 직후”의 상태.

행	판정 시 x (조건 x ≤ 8)	실행 후 x	실행 후 total
초기	—	1	0
반복 1	1 ≤ 8 참	2	1 (= 0 + 1)
반복 2	2 ≤ 8 참	4	3 (= 1 + 2)
반복 3	4 ≤ 8 참	8	7 (= 3 + 4)
반복 4	8 ≤ 8 참	16	15 (= 7 + 8)
종료 판정	16 ≤ 8 거짓	—	—

• 반복 횟수: 4회. 체크포인트 행의 (x, total)은 (2,1) → (4,3) → (8,7) → (16,15).
• 출력: 15. 최종 상태: x = 16, total = 15.
• 함정: 조건이 ≤이므로 x = 8일 때도 본문을 실행합니다. <로 잘못 읽으면 3회, 출력 7이 됩니다.

---

5. 반복의 종료

while 반복이 의도대로 끝나려면 세 가지를 함께 점검합니다.

• 초기화: 반복 전에 변수가 올바른 값을 갖는가?
• 조건: while 뒤의 조건은 계속 조건입니다. “언제 멈추는가”(종료 조건)는 그 부정입니다. 예: while b ≠ 0의 종료 조건은 b = 0입니다. 종료 조건을 그대로 while 뒤에 쓰면 반복이 아예 시작되지 않거나 엉뚱하게 동작합니다.
• 갱신(진행): 매 반복마다 조건을 거짓 쪽으로 움직이는 변화가 있는가?

대표적인 함정

• 하나 차이 오류(off-by-one): <와 ≤, 시작값 0과 1을 헷갈려 1회 많거나 적게 실행합니다. 반복 횟수는 “첫 값·마지막 값·조건”을 직접 대입해 확인합니다.
• 진행 없음(non-progress): 갱신 문장을 빠뜨리거나, 갱신이 조건과 무관한 변수를 바꾸면 무한 루프가 됩니다.

변량(variant, 순위 함수)의 직관: 반복마다 엄격하게 감소하고, 반복이 계속되는 동안 어떤 하한 아래로 내려갈 수 없는 정수 값을 하나 찾으면, 반복은 반드시 유한 번 안에 끝납니다. 예제 1에서는 9 − x가 8, 7, 5, 1로 줄고, 1보다 작아지면(조건 x ≤ 8이 거짓) 반복이 멈춥니다. 시험에서는 엄밀한 증명보다 “무엇이 매번 줄어드는가?“를 묻는 감각이면 충분합니다.

예제 2: 유클리드 호제법 (48, 18)

a ← 48
b ← 18
while b ≠ 0
    r ← a mod b
    a ← b
    b ← r
output a

행의 의미: 반복 k행 = “k번째 반복의 세 문장을 모두 실행한 직후”의 (a, b).

행	판정 (b ≠ 0)	r = a mod b (옛 a, 옛 b 사용)	실행 후 (a, b)
초기	—	—	(48, 18)
반복 1	18 ≠ 0 참	48 mod 18 = 12 (48 = 18×2 + 12)	(18, 12)
반복 2	12 ≠ 0 참	18 mod 12 = 6 (18 = 12×1 + 6)	(12, 6)
반복 3	6 ≠ 0 참	12 mod 6 = 0 (12 = 6×2 + 0)	(6, 0)
종료 판정	0 ≠ 0 거짓	—	—

• 상태 변화: (48,18) → (18,12) → (12,6) → (6,0). 반복 3회, 출력 6 (48과 18의 최대공약수).
• 종료 이유(변량): 나머지 r은 항상 0 ≤ r < b이므로 새 b는 옛 b보다 엄격하게 작고 0 이상입니다. 음이 아닌 정수가 무한히 감소할 수는 없으므로 반드시 b = 0에 도달합니다.
• 함정: a ← b와 b ← r의 순서를 바꾸면(b ← r을 먼저) a에 새 b가 들어가 결과가 틀립니다. r이라는 임시 변수가 옛 값을 보존하는 역할을 합니다.

---

6. 재귀

재귀 함수는 자기 자신을 호출합니다. 추적할 때는 두 단계를 분리합니다.

1. 내려가기(호출): 기저 사례에 닿을 때까지 호출이 쌓입니다. 이때는 아직 아무 계산도 완료되지 않은 “보류 중” 상태입니다.
2. 되돌아오기(반환): 기저 사례가 값을 반환하면, 가장 최근 호출부터 거꾸로 계산을 마치며 반환합니다.

핵심 규칙:

• 모든 재귀 경로는 기저 사례 쪽으로 진행해야 합니다. 인수가 기저 사례에 가까워지지 않는 경로가 있으면 호출이 끝없이 쌓입니다.
• 활성화된 각 호출은 자신만의 인수·지역 변수를 호출 스택에 가집니다. F(5) 안의 n과 F(3) 안의 n은 서로 다른 변수입니다.
• 호출 스택은 후입선출(LIFO)입니다. 그래서 호출 순서와 반환 순서는 반대입니다.

예제 3: F(5)의 호출과 반환

F(n):
    if n ≤ 1
        return 1
    else
        return n + F(n − 2)

호출(내려가기) 순서

단계	호출	n	동작	스택 깊이(호출 후)
C1	F(5)	5	5 ≤ 1 거짓 → 5 + F(3) 보류	1
C2	F(3)	3	3 ≤ 1 거짓 → 3 + F(1) 보류	2
C3	F(1)	1	1 ≤ 1 참 → 기저 사례	3

반환(되돌아오기) 순서

단계	반환하는 호출	계산	반환값
R1	F(1)	기저 사례	1
R2	F(3)	3 + 1	4
R3	F(5)	5 + 4	9

• 전개: F(5) = 5 + F(3) = 5 + 3 + F(1) = 5 + 3 + 1 = 9.
• 호출 순서는 F(5), F(3), F(1). 반환 순서는 F(1), F(3), F(5)이고 반환값은 1, 4, 9.
• 비용: n ≥ 1일 때 호출 횟수는 ⌊n/2⌋ + 1(같은 값으로 ⌈(n + 1)/2⌉), 즉 대략 n/2회이고 각 호출의 작업은 상수입니다. 계산량 표기에서는 상수배(1/2)를 무시하므로 시간은 **Θ(n)**입니다. 동시에 쌓이는 최대 호출 수(호출 스택 깊이)도 같은 이유로 **Θ(n)**이며, 이는 추가 공간 Θ(n)을 의미합니다.
• 이 정의는 매 호출에서 재귀 호출이 한 번뿐이므로 호출 수가 선형입니다. 한 호출 안에서 재귀 호출이 두 번 일어나는 정의와는 계산량이 다르니 혼동하지 마세요.

---

7. 계산량

계산량은 입력 크기 n에 따라 실행 횟수(또는 메모리 사용량)가 어떻게 늘어나는가를 나타냅니다. 특정 컴퓨터에서 걸린 “몇 초”라는 경과 시간과는 다른 개념입니다. 경과 시간은 하드웨어·언어·구현에 따라 달라지지만, 실행 횟수의 증가 양상은 알고리즘 자체의 성질입니다.

세 가지 수준을 구별합니다.

수준	의미	예
정확한 횟수	정해진 문장이 실행되는 정확한 횟수	n(n + 1)/2
Θ (세타)	상수배를 무시한 꽉 맞는 증가율(위아래 모두)	Θ(n²)
O (빅오)	상수배를 무시한 상한(이보다 빠르게 늘지 않음)	O(n²). O(n³)도 참이지만 느슨한 상한

시험에서 “계산량은 O(…)“라고 할 때는 보통 가장 꽉 맞는 상한을 뜻하는 경우가 많지만, 정의상 O는 상한이라는 점을 기억해 두세요.

예제 4: 삼각형 모양 중첩 루프의 정확한 횟수

count ← 0
for i ← 1 to n
    for j ← 1 to i
        count ← count + 1
output count

셈 규칙: count ← count + 1이 실행되는 횟수를 센다(= 최종 count 값).

n = 4일 때, 행의 의미는 “바깥 반복 i 회차의 안쪽 반복이 모두 끝난 직후”.

i	안쪽 j의 값	이번 회차 실행 횟수	누적 count
1	1	1	1
2	1, 2	2	3
3	1, 2, 3	3	6
4	1, 2, 3, 4	4	10

• 일반식: 1 + 2 + … + n = n(n + 1)/2. n = 4이면 4×5/2 = 10.
• n(n + 1)/2 = n²/2 + n/2에서 최고차항만 남기고 상수배를 버리면 Θ(n²), 따라서 O(n²).

계산 규칙 요약

• 순차 블록은 더한다: 블록 A 다음 블록 B이면 횟수는 A + B, 증가율은 더 큰 쪽. 예: n + n² → Θ(n²).
• 독립 중첩 루프는 곱한다: 바깥 n회 × 안쪽 m회(안쪽 범위가 바깥 변수와 무관) → n·m회.
• 절반/두 배 루프는 로그: 매번 j ← 2 * j(또는 n ← n div 2) 하는 반복은 약 log₂ n회 → Θ(log n).
• 분기: 정확한 횟수는 실제로 실행된 경로로 셉니다. 최악 계산량(빅오)은 가장 비싼 분기를 기준으로 합니다.
• 공간 계산량: 입력 외에 추가로 쓰는 메모리(보조 공간)를 봅니다. 예제 4는 count, i, j만 쓰므로 Θ(1). 재귀는 호출 스택도 공간입니다. 예제 3의 F(n)은 Θ(n) 스택 공간을 씁니다.

---

8. 상태 전이

“상태”라는 말은 두 가지 뜻으로 쓰입니다.

• 알고리즘의 변수 상태: 어떤 시점의 모든 변수 값의 묶음. 예: 예제 2의 (a, b) = (18, 12).
• 유한 상태 기계(유한 오토마톤)의 상태: 미리 정해진 유한 개의 상태 중 하나. 예: “짝수(E)”, “홀수(O)”.

유한 상태 기계에서 전이란 “현재 상태와 입력 기호가 정해지면 다음 상태가 결정되는 것”입니다. 이 규칙을 표로 쓴 것이 상태 전이표, 원과 화살표로 그린 것이 상태 전이도입니다.

예제 5: 패리티(1의 개수가 짝수인가) 오토마톤

• 상태: E(지금까지 읽은 1의 개수가 짝수), O(홀수). 시작 상태 E.
• 규칙: 입력 0 → 상태 유지, 입력 1 → E와 O를 서로 바꿈.

상태 전이표

현재 상태	입력 0	입력 1
E	E	O
O	O	E

상태 전이도(텍스트 표현)

(시작) → E
E --0--> E      E --1--> O
O --0--> O      O --1--> E

입력 101101 추적. 행의 의미: “k번째 기호를 읽기 전 상태”와 “읽은 후 상태”를 모두 적는다.

k	읽기 전 상태	입력 기호	읽은 후 상태
1	E	1	O
2	O	0	O
3	O	1	E
4	E	1	O
5	O	0	O
6	O	1	E

• 상태열: E → O → O → E → O → O → E.
• 최종 상태 E: 입력에 포함된 1의 개수(4개)가 짝수 패리티임을 뜻합니다.
• 함정: “읽기 전” 열만 이어서 답하면 마지막 기호의 효과가 빠져 E, O, O, E, O, O가 됩니다. 문제에서 행이 무엇을 뜻하는지 반드시 확인하세요.

---

9. 오리지널 연습문제 (5문항)

아래 5문항은 모두 이 글을 위해 새로 만든 오리지널 문제이며, 기출문제를 사용하거나 변형하지 않았습니다. 표기는 3절의 이 글 전용 표기를 따릅니다.

문제 1 (변수 추적)

다음 의사코드를 실행했을 때 출력되는 b의 값은? (체크포인트: 반복 본문의 세 문장을 모두 실행한 직후)

a ← 3
b ← 0
k ← 1
while k ≤ 3
    b ← b + a * k
    a ← a − 1
    k ← k + 1
output b

1. 7
2. 18
3. 10
4. 4

정답: 3 (10)

추적표 (실행 후 a, b, k):

행	판정	계산	a	b	k
초기	—	—	3	0	1
반복 1	1 ≤ 3 참	b = 0 + 3×1 = 3	2	3	2
반복 2	2 ≤ 3 참	b = 3 + 2×2 = 7	1	7	3
반복 3	3 ≤ 3 참	b = 7 + 1×3 = 10	0	10	4
종료	4 ≤ 3 거짓	—	—	—	—

• 1번 (7): 반복 2 직후의 값입니다. ≤를 <로 읽어 2회만 실행하면 이 값이 나옵니다.
• 2번 (18): a가 줄어드는 것을 무시하고 3×1 + 3×2 + 3×3을 계산한 값입니다.
• 3번 (10): 정답. 각 문장을 순서대로, 그 순간의 값으로 계산한 결과입니다.
• 4번 (4): a ← a − 1을 b 갱신보다 먼저 실행했다고 착각한 값입니다(2×1 + 1×2 + 0×3 = 4).

문제 2 (반복 종료 · 하나 차이 오류)

n은 1 이상의 정수입니다. 본문 P를 정확히 n회 실행하고, 각 실행 시작 시점의 i 값이 0, 1, …, n − 1이 되도록 하려 합니다. 올바른 것은?

1. i ← 0 / while i ≤ n / (본문) P, i ← i + 1
2. i ← 0 / while i < n / (본문) P, i ← i + 1
3. i ← 1 / while i < n / (본문) P, i ← i + 1
4. i ← 0 / while i = n / (본문) P, i ← i + 1

정답: 2

• 1번: i가 0, 1, …, n일 때 실행되어 n + 1회입니다(하나 많음).
• 2번: 정답. i가 0부터 n − 1까지일 때 조건이 참이고, i = n에서 거짓이 되어 정확히 n회입니다. 매 반복 i가 1씩 늘어 n − i가 감소하므로 반드시 끝납니다.
• 3번: i가 1, …, n − 1이므로 n − 1회이고, 시작값도 0이 아닙니다(하나 적음).
• 4번: 종료 조건(i = n)을 계속 조건 자리에 쓴 실수입니다. 처음 i = 0 ≠ n(n ≥ 1)이므로 조건이 거짓이어서 0회 실행됩니다.

문제 3 (재귀 반환 추적)

G(n):
    if n = 0
        return 0
    else
        return 2 * G(n − 1) + 1

G(3)을 호출했을 때, 각 호출이 반환되는 순서대로 반환값을 나열한 것은?

1. 7, 3, 1, 0
2. 0, 1, 2, 3
3. 1, 3, 7, 15
4. 0, 1, 3, 7

정답: 4

호출 순서: G(3) → G(2) → G(1) → G(0). 반환 순서: G(0), G(1), G(2), G(3).

반환 단계	호출	계산	반환값
1	G(0)	기저 사례	0
2	G(1)	2×0 + 1	1
3	G(2)	2×1 + 1	3
4	G(3)	2×3 + 1	7

• 1번: 값은 맞지만 호출 순서(G(3)부터)로 나열했습니다. 반환은 가장 깊은 호출부터 일어납니다.
• 2번: 반환값이 아니라 각 호출의 인수 n을 반환 순서로 적은 것입니다.
• 3번: 기저 사례 값을 1로 착각하여 한 단계씩 밀린 값입니다(G(0)=1이라면 1, 3, 7, 15).
• 4번: 정답.

문제 4 (연산 횟수 · 빅오)

count ← 0
for i ← 1 to n
    count ← count + 1
for i ← 1 to n
    j ← 1
    while j < n
        count ← count + 1
        j ← 2 * j
output count

셈 규칙: count ← count + 1의 실행 횟수(= 출력값). n = 8일 때의 출력값과, n이 2의 거듭제곱일 때의 시간 계산량으로 옳은 조합은?

1. 32, Θ(n log n)
2. 40, Θ(n log n)
3. 24, Θ(n log n)
4. 72, Θ(n²)

정답: 1

• 첫 번째 루프: 8회.
• 두 번째 루프: 각 i마다 안쪽 while에서 j = 1, 2, 4일 때 실행(j = 8에서 8 < 8 거짓) → 3회 = log₂ 8. 8 × 3 = 24회.
• 합계 8 + 24 = 32. 일반적으로 n + n·log₂ n이며, 순차 블록은 큰 쪽이 지배하므로 Θ(n log n).
• 1번: 정답.
• 2번 (40): 안쪽 조건을 j ≤ n으로 읽어 각 i마다 4회로 센 하나 차이 오류입니다(8 + 8×4).
• 3번 (24): 첫 번째 순차 블록(8회)을 더하지 않았습니다.
• 4번 (72, Θ(n²)): 안쪽 루프를 n회 반복으로 착각했습니다(8 + 8×8). 두 배씩 늘어나는 루프는 로그 횟수입니다.

문제 5 (상태 전이)

다음 상태 전이표를 가진 오토마톤이 있습니다. 시작 상태는 R0입니다.

현재 상태	입력 0	입력 1
R0	R0	R1
R1	R2	R0
R2	R1	R2

입력 1101을 왼쪽부터 한 기호씩 읽을 때, 각 기호를 읽은 직후의 상태를 순서대로 나열한 것은?

1. R1, R2, R2, R2
2. R0, R1, R0, R0
3. R1, R0, R0, R1
4. R1, R2, R2, R0

정답: 3

k	읽기 전	입력	읽은 후
1	R0	1	R1
2	R1	1	R0
3	R0	0	R0
4	R0	1	R1

• 1번: 입력을 오른쪽부터(1, 0, 1, 1) 읽은 결과입니다(R0→R1→R2→R2→R2).
• 2번: 각 기호를 읽기 전 상태를 나열했습니다. 마지막 기호의 효과가 빠집니다.
• 3번: 정답. 최종 상태 R1. (참고: 이 표는 2진수를 왼쪽부터 읽으며 3으로 나눈 나머지를 추적하는 기계로, 1101₂ = 13, 13 mod 3 = 1과 일치합니다.)
• 4번: 표를 보지 않고 “1의 개수를 3으로 나눈 나머지”를 세는 기계라고 짐작한 결과입니다(R1에서 1을 읽으면 표에서는 R0인데 R2로 처리).

---

10. 퀵시트

• ←는 대입, =는 비교. 문제의 기호 정의가 항상 우선.
• 추적표: 초기 행 → 체크포인트 정의 → 한 문장씩 → 옛 값/새 값 구분 → 출력과 최종 상태.
• while 조건은 계속 조건. 종료 조건은 그 부정.
• 반복 점검 3종: 초기화·조건·갱신. 변량이 엄격히 줄면서 하한이 있으면 종료.
• 재귀: 호출은 내려가며 쌓이고, 반환은 거꾸로 풀린다. 기저 사례로의 진행 필수. 호출마다 독립된 변수.
• F(n) = n + F(n − 2): 호출 수·스택 깊이 Θ(n).
• 1 + 2 + … + n = n(n + 1)/2 → Θ(n²).
• 순차는 덧셈, 독립 중첩은 곱셈, 절반/두 배는 log.
• 정확한 횟수 ≠ Θ(꽉 맞는 증가율) ≠ O(상한) ≠ 초 단위 경과 시간.
• 유한 상태 기계: 다음 상태 = f(현재 상태, 입력). 행이 “읽기 전”인지 “읽은 후”인지 확인.

11. 자주 하는 실수

1. 같은 반복 안에서 이미 갱신된 값을 옛 값으로 착각(또는 반대).
2. <와 ≤ 혼동으로 1회 차이.
3. 종료 조건을 while 뒤에 그대로 씀.
4. 갱신 문장 누락으로 무한 루프.
5. 재귀의 반환 순서를 호출 순서로 답함.
6. 기저 사례의 반환값을 잘못 읽어 모든 값이 밀림.
7. 상수배나 낮은 차수 항을 남겨 둔 채 Θ/O를 씀(예: Θ(n²/2)).
8. 두 배로 늘어나는 루프를 n회로 셈.
9. 재귀의 스택 공간을 공간 계산량에서 빠뜨림.
10. 상태 전이 추적에서 입력을 읽는 방향이나 행의 시점을 혼동.

12. 최종 자가 점검

• 예제 1을 보지 않고 (x, total) 행 4개와 출력 15를 다시 만들 수 있다.
• 48 mod 18, 18 mod 12, 12 mod 6을 계산하고 반복 3회·결과 6을 설명할 수 있다.
• F(5)의 호출 순서와 반환 순서(반환값 1, 4, 9)를 따로 적을 수 있다.
• 삼각형 중첩 루프의 n(n + 1)/2와 n = 4일 때 10을 표로 보일 수 있다.
• 정확한 횟수, Θ, O, 보조 공간의 차이를 한 문장씩 말할 수 있다.
• 패리티 오토마톤에서 101101의 상태열 E→O→O→E→O→O→E를 재현할 수 있다.
• 연습문제 5문항의 오답 선택지가 왜 틀렸는지 설명할 수 있다.

13. 복습 제안 (1일 / 3일 / 7일)

학습 데이터에 근거한 처방이 아니라 일반적인 간격 복습 제안입니다.

• 1일 후: 퀵시트를 읽고, 예제 1·2의 추적표를 빈 종이에 다시 작성.
• 3일 후: 예제 3·4를 다시 풀고, n = 5로 바꿔 삼각형 루프 횟수(15)와 F(7)(= 7 + 5 + 3 + 1 = 16)를 직접 확인.
• 7일 후: 연습문제 5문항을 해설 없이 다시 풀고, 틀린 문항의 함정을 11절에서 찾아 표시.

---

14. 시러버스 대응

• 大分類1：基礎理論／中分類1：基礎理論／3. 情報に関する理論／（6）オートマトン
• 大分類1：基礎理論／中分類1：基礎理論／3. 情報に関する理論／（8）計算量
• 大分類1：基礎理論／中分類2：アルゴリズムとプログラミング／2. アルゴリズム／（1）流れ図
• 大分類1：基礎理論／中分類2：アルゴリズムとプログラミング／2. アルゴリズム／（2）代表的なアルゴリズム／②再帰のアルゴリズム
• 大分類1：基礎理論／中分類2：アルゴリズムとプログラミング／2. アルゴリズム／（3）アルゴリズム設計

15. 출처

• IPA 「応用情報技術者試験（レベル3）シラバス Ver.7.2」 https://www.ipa.go.jp/shiken/syllabus/omgdg50000005kq5-att/syllabus_ap_ver7_2.pdf (확인일: 2026-10-20 / 이 글의 개정일: 2026-10-20)
• 시러버스는 출제 범위 확인에만 사용했습니다. 이 글의 설명·예제·연습문제는 모두 독자적으로 작성했으며, 기출문제나 제3자의 해설을 사용하지 않았습니다. 이 글은 IPA의 승인이나 보증을 받은 자료가 아닙니다.