1. 알고리즘(Algorithm)이란 무엇인가
정의
알고리즘은 주어진 작업을 수행하기 위한 명확한 절차(Definite Procedure) 다.
요리 레시피 비유
김치찌개를 만들기 위해 필요한 재료와 조리 순서가 명확하게 정해진 레시피처럼, 알고리즘은 특정 문제를 해결하기 위한 단계별 지시사항의 집합이다.
알고리즘의 위치
[문제] → [알고리즘 설계] → [프로그램 구현] → [실행]
↑
이산구조의 핵심 영역알고리즘은 컴퓨터 프로그램의 설계도이자 기반이다. 좋은 알고리즘 없이 좋은 프로그램은 만들 수 없다.
💡 역사적 어원: '알고리즘(Algorithm)'은 9세기 페르시아 수학자 알 콰리즈미(al-Khwarizmi) 의 이름에서 유래했다. 1200년 전부터 이 개념이 존재했다는 의미다.
2. 알고리즘의 6대 필수 특징 ⭐⭐⭐ 시험 단답형 빈출
알고리즘이 진정한 알고리즘이 되기 위해 만족해야 할 6가지 필수 조건이다.
6대 특징 한눈에 보기
| 1 | 입력 | Input | 외부에서 들어오는 데이터 존재 |
| 2 | 출력 | Output | 입력에 대한 정확한 결과 생성 |
| 3 | 명확성 | Definiteness | 각 단계가 모호함 없이 정의됨 |
| 4 | 정확성 | Correctness | 항상 올바른 결과 도출 |
| 5 | 유한성 | Finiteness | 반드시 끝이 있음 (무한 루프 X) |
| 6 | 효율성 | Effectiveness | 각 단계가 유한 시간 내 수행 가능 |
| 7 | 일반성 | Generality | 모든 가능한 입력에 동작 |
각 특징 상세 설명
알고리즘은 외부로부터 데이터를 받아야 한다.
예: 정렬 알고리즘 → 정렬할 숫자 리스트 (입력)
입력 값에 대해 정확한 출력 값을 생성해야 한다.
예: 정렬 알고리즘 → 정렬된 숫자 리스트 (출력)
각 단계가 모호하지 않게 명확히 정의되어야 한다.
| "x를 찾아라" | "i = 1부터 n까지 a[i]를 x와 비교" |
| "큰 수를 골라라" | "if a > b then return a" |
| "적당히 정렬" | "버블 정렬을 사용해 오름차순 정렬" |
알고리즘은 항상 올바른 결과를 도출해야 한다.
특정 입력에서만 작동하면 안 되고, 모든 정상 입력에 대해 정답이 나와야 한다.
알고리즘은 반드시 끝이 있어야 한다.
| 100번 반복 후 종료 | 무한 루프 |
| 조건 충족 시 종료 | 종료 조건 없는 반복 |
⚠️ 중요: 무한히 실행되는 코드는 알고리즘이 아니다. 이는 단순한 절차나 프로세스일 뿐이다.
각 단계는 유한한 시간 내에 수행 가능해야 한다 (Do-able).
"무한한 정밀도로 원주율 계산" 같은 단계는 효율성 위반.
특정 입력만이 아니라, 모든 가능한 입력에 대해 동작해야 한다.
예: 정렬 알고리즘은 [1, 2, 3]에서만 작동하면 안 되고, 어떤 숫자 리스트에서도 작동해야 함.
3. 알고리즘 vs 비(非)알고리즘 — 사례 비교
진짜 알고리즘 ⭕
"리스트 a₁, a₂, ..., aₙ에서 최댓값을 찾기 위해:
- v = a₁로 설정
- i = 2부터 n까지 반복
- a[i] > v이면 v = a[i]
- v 반환"
→ 모든 6대 특징 만족 ✅
알고리즘처럼 보이는 것 ❌
"큰 숫자를 잘 골라봐"
→ 명확성 X, 입력/출력 정의 X → 알고리즘 아님
💡 핵심 통찰: 알고리즘과 일상 지시의 결정적 차이는 모호함의 제거다. "잘", "적당히", "대충" 같은 표현이 들어가면 알고리즘이 아니다.
4. 컴퓨터 프로그램(Computer Program)과의 관계
정의
컴퓨터 프로그램은 정의된 알고리즘을 정확한 언어로 기술한 결과물 — 알고리즘의 구현(Implementation) 이다.
알고리즘 vs 프로그램
| 비유 | 건물의 설계도 | 실제 건물 |
| 표현 | 자연어, 의사코드 | 프로그래밍 언어 (Java, Python 등) |
| 실행 | 컴퓨터에서 직접 X | 컴퓨터에서 실행 가능 ⭕ |
| 추상화 수준 | 높음 (개념적) | 낮음 (구체적) |
| 언어 의존성 | 없음 | 있음 (특정 언어) |
같은 알고리즘, 다른 프로그램
동일한 "최댓값 찾기 알고리즘"이라도 Python, Java, C로 각각 구현하면 다른 프로그램이 된다. 하지만 알고리즘은 하나다.
💡 시험 핵심 구분: 알고리즘은 "무엇을 어떻게 할 것인가"의 논리, 프로그램은 "그 논리를 특정 언어로 정확히 표현한 결과".
5. 의사코드 (Pseudocode)란 ⭐
정의
의사코드는 알고리즘을 비공식적으로 표현하는 방법으로, 실제 프로그래밍 언어 문법에 얽매이지 않고 사람이 이해하기 쉽게 작성된다.
자연어 vs 의사코드 vs 실제 코드
| 자연어 | "최댓값을 찾아라" |
| 의사코드 | v := a₁; for i := 2 to n if a_i > v then v := a_i |
| 실제 코드 (Python) | max_val = max(a) |
의사코드는 자연어와 실제 코드의 중간 단계다.
의사코드의 가치
| 연습장 역할 | 실제 코드 전 알고리즘 흐름 정리 |
| 언어 독립적 | 어떤 프로그래밍 언어로도 변환 가능 |
| 가독성 | 사람이 읽기 쉬움 |
| 소통 도구 | 개발자 간 알고리즘 공유 표준 |
의사코드의 특징
| 비공식적 표현 | 엄격한 문법 X |
| 의미 명확성 우선 | "swap(x, y)" 같은 표현 허용 |
| 실행 불가능 | 컴퓨터에서 직접 실행 X |
💡 학습 팁: 의사코드를 효과적으로 활용하려면 최소 한 개 이상의 실제 프로그래밍 언어를 알고 있어야 한다. 의사코드만으로는 추상적이지만, 실제 언어 경험이 있으면 의사코드의 의도가 자연스럽게 보인다.
6. 의사코드 기본 문법 ⭐⭐⭐ 시험 빈출
이 강의에서 다루는 Pascal 스타일 의사코드의 9가지 기본 구문이다.
의사코드 문법 9선
| 1 | procedure name(arg: type) | 프로시저(함수) 선언 |
| 2 | variable := expression | 변수 할당 (계산해서 넣기) |
| 3 | begin ... end | 문장 블록 그룹화 |
| 4 | {comment} | 주석 |
| 5 | if condition then statement | 조건문 |
| 6 | if condition then ... else ... | 양방향 조건문 |
| 7 | for variable := initial to final | for 반복문 |
| 8 | while condition | while 반복문 |
| 9 | return expression | 값 반환 |
핵심 문법 상세 설명
procedure max(a₁, a₂, ..., aₙ: integers)함수의 이름과 입력 파라미터를 정의.
v := a₁| := | "계산해서 넣어라" (할당) | 수학의 = 와 다름! |
| = | "같다" (비교 연산) | 진위 판별 |
⚠️ 시험 함정 1순위: :=(할당)과 =(비교)를 헷갈리지 말 것. x := 5는 "x에 5를 넣어라", x = 5는 "x가 5와 같은가?"
begin
statement1
statement2
statement3
end여러 문장을 하나의 단위로 묶음.
v := a₁ {임시 최댓값을 첫 번째 값으로 설정}{} 안의 내용은 컴퓨터가 무시. 사람의 이해를 돕기 위한 설명.
if x > y then
v := x
else
v := y조건이 참이면 then 부분 실행, 거짓이면 else 부분 실행.
for i := 1 to n
statementi를 1부터 n까지 1씩 증가시키며 statement 반복.
while (i ≤ n and x ≠ aᵢ)
i := i + 1조건이 참인 동안 반복.
return location함수의 결과값을 호출자에게 돌려줌.
💡 for vs while 구분: for는 "몇 번 반복할지 정해진 경우" (예: 1부터 100까지), while은 "조건 충족 시까지 반복" (예: 답을 찾을 때까지). 시험에서는 두 반복문 중 어느 것이 적합한지 묻는 문제도 나온다.
7. 알고리즘 의사코드 종합 예제 ⭐
예제: 최댓값 찾기 알고리즘
목표: 정수 리스트 a₁, a₂, ..., aₙ에서 최댓값 찾기.
procedure max(a₁, a₂, ..., aₙ: integers)
v := a₁ {임시 최댓값 변수}
for i := 2 to n
if aᵢ > v then v := aᵢ
return v {v는 최댓값}| 1 | procedure max(...) | "max"라는 함수 정의 |
| 2 | v := a₁ | 첫 번째 값을 임시 최댓값으로 저장 |
| 3 | for i := 2 to n | i를 2부터 n까지 반복 |
| 4 | if aᵢ > v then v := aᵢ | 현재 값이 더 크면 v 갱신 |
| 5 | return v | 최종 최댓값 반환 |
💡 알고리즘 6대 특징 검증:
- 입력 ⭕ (a₁~aₙ)
- 출력 ⭕ (v)
- 명확성 ⭕ (각 단계 명확)
- 정확성 ⭕ (모든 값 비교 후 최대 도출)
- 유한성 ⭕ (n번 반복 후 종료)
- 효율성 ⭕ (각 단계 빠르게 수행)
- 일반성 ⭕ (어떤 정수 리스트도 처리) 모든 조건 만족 → 진짜 알고리즘 ✅
8. 알고리즘 실행 (Execute / Run)
정의
알고리즘 실행이란 정의된 단계에 따라 실제 작업을 수행하는 것이다.
"사람이 곧 컴퓨터" 시대
2차 대전 이전에는 '컴퓨터(Computer)'가 알고리즘을 수행하는 사람을 의미했다. 인간 수학자들이 종이에 알고리즘을 따라 계산하던 시절.
알고리즘 학습의 핵심 — 손으로 추적하기
알고리즘을 가장 확실하게 이해하는 방법은 사람이 직접 종이에 쓰면서 따라 해보는 것이다.
실행 추적 예제
수열: a = {7, 12, 3, 15, 8} 목표: 최댓값 찾기
| 초기 | v = a₁ | 7 | 시작 |
| i=2 | 12 > 7? 참 | 12 | 갱신 ✅ |
| i=3 | 3 > 12? 거짓 | 12 | 유지 |
| i=4 | 15 > 12? 참 | 15 | 갱신 ✅ |
| i=5 | 8 > 15? 거짓 | 15 | 유지 |
최종 결과: v = 15 ✅
💡 시험 핵심 스킬: 시험에서 의사코드와 입력 데이터가 주어지고 "실행 결과를 추적하시오"라는 문제가 자주 나온다. 표로 단계별 변수 변화를 정리하는 습관을 들이자. 디버깅 능력의 핵심이기도 하다.
9. 알고리즘과 디버깅의 연결고리
디버깅(Debugging)의 본질
프로그램에 오류가 생겼을 때, 알고리즘의 실행 과정을 한 단계씩 추적하여 어디서 문제가 발생했는지 찾는 작업.
추적 능력 = 디버깅 능력
| 1 | 입력값 설정 |
| 2 | 변수 변화 단계별 기록 |
| 3 | 예상 결과와 실제 결과 비교 |
| 4 | 차이 발생 지점 찾기 |
| 5 | 알고리즘 또는 코드 수정 |
💡 개발자 실무 직결: 시니어 개발자와 주니어 개발자의 가장 큰 차이는 **"코드를 머릿속에서 실행할 수 있는가"**다. 이는 학생 때부터 의사코드 추적을 손으로 연습하며 길러지는 능력이다.
10. 알고리즘 학습의 비밀 ⭐
진리
"왕도(지름길)는 없다. 오직 연습만이 살 길이다."
알고리즘 학습 4단계
| 1 | 많은 예제 보기 |
| 2 | 직접 연습하기 |
| 3 | 더 많은 예제 보기 |
| 4 | 무한 반복 (1~3 사이클) |
왜 알고리즘은 어려운가?
알고리즘 발명은 수학 증명을 작성하는 것과 유사하게 많은 창의성과 직관을 요구한다. 단 하나의 마법 같은 '알고리즘'은 존재하지 않는다.
학습 마인드셋
| "공식 외우기" | "원리 이해 + 직접 구현" |
| "한 번 봤으니 됐다" | "여러 번 손으로 따라 쓰기" |
| "이론만 보기" | "실제 코드로 구현하기" |
| "남의 풀이 보고 끝" | "스스로 풀어보고 비교" |
⚠️ 솔직한 조언: 이산구조 알고리즘 단원은 시험 직전 벼락치기로는 절대 안 된다. 매주 1~2개 알고리즘을 직접 손으로 풀어보는 꾸준한 연습이 유일한 길이다. 다음 19강에서 다룰 5가지 알고리즘(선형 검색·이진 검색·버블 정렬·삽입 정렬·탐욕 알고리즘)을 각각 5번씩 손으로 추적해보자.
📌 한눈에 보는 핵심정리
| 알고리즘 | 작업 수행을 위한 명확한 절차 |
| 알고리즘 6대 특징 | 입력·출력·명확성·정확성·유한성·효율성·일반성 |
| 명확성 | 모호함 없이 정의 (잘/적당히/대충 X) |
| 유한성 | 반드시 끝이 있음 (무한 루프 X) |
| 컴퓨터 프로그램 | 알고리즘의 구체적 구현 (특정 언어로) |
| 알고리즘 vs 프로그램 | 설계도 vs 건물 |
| 의사코드 | 비공식적 알고리즘 표현, 언어 독립적 |
| :=와 = | 할당 (계산해서 넣기) vs 비교 (같은가?) |
| for vs while | 횟수 정해짐 vs 조건 충족 시까지 |
| 알고리즘 추적 | 변수 변화를 표로 단계별 기록 (디버깅 핵심) |
| 학습 비결 | 왕도 없음, 연습이 살 길 |
🧠 예상문제 2제
문제 1. 알고리즘 6대 특징 위반
다음 절차 중 알고리즘이 아닌 것은?
① "리스트의 첫 번째 요소부터 끝까지 순회하며 찾는 값과 비교한다" ② "1부터 100까지 모든 수를 더한다" ③ "리스트에서 가장 큰 수를 적당히 골라낸다" ④ "n=1부터 시작해서 n²+1이 소수일 때까지 n을 1씩 증가시킨다"
👉 정답: ③
각 선택지 분석:
| ① | 명확한 단계, 유한 종료 | 알고리즘 ✅ |
| ② | 명확하고 유한함 | 알고리즘 ✅ |
| ③ | "적당히"는 모호함 | 명확성 위반 ❌ |
| ④ | 끝이 있을지 불확실하지만 절차 자체는 명확 | 알고리즘 ✅ (논쟁 가능하지만 단계 명확) |
💡 시험 핵심: 알고리즘의 6대 특징 중 가장 자주 위반되는 것이 명확성이다. "적당히, 알맞게, 대충, 잘"같은 모호한 표현이 들어가면 무조건 알고리즘이 아니다. 시험 단답형 단골 함정.
⚠️ 참고: ④번은 사실 콜라츠 추측처럼 종료 여부가 미증명일 수 있어 "유한성" 논란이 있을 수 있지만, 단계 자체는 명확하므로 알고리즘으로 본다. 이런 미세한 판단은 출제 의도에 따라 달라진다.
문제 2. 의사코드 추적
다음 의사코드를 입력 a = {3, 8, 1, 6, 4}로 실행했을 때, 반환되는 v 값은?
procedure mystery(a₁, a₂, ..., aₙ: integers)
v := a₁
for i := 2 to n
if aᵢ < v then v := aᵢ
return v① 3 ② 8 ③ 1 ④ 6
👉 정답: ③
| 초기 | v = a₁ = 3 | 3 | 시작 |
| i=2 | 8 < 3? 거짓 | 3 | 유지 |
| i=3 | 1 < 3? 참 | 1 | 갱신 ✅ |
| i=4 | 6 < 1? 거짓 | 1 | 유지 |
| i=5 | 4 < 1? 거짓 | 1 | 유지 |
반환값: v = 1 ✅
이 의사코드는 사실 최솟값을 찾는 알고리즘이다. 차이점은:
- 본문 예제 max → if aᵢ > v then v := aᵢ (더 큰 값으로 갱신)
- 이 문제 mystery → if aᵢ < v then v := aᵢ (더 작은 값으로 갱신)
💡 시험 핵심 스킬: 부등호 방향 한 글자 바꾸면 알고리즘의 의미가 정반대가 된다. 의사코드를 읽을 때 부등호 방향을 가장 먼저 확인하는 습관을 들이자. 이것이 시험에서 가장 흔한 실수 패턴이다.
💡 추가 학습: 알고리즘 추적 문제는 표를 그려 단계별로 정리하는 것이 가장 안전하다. 머릿속으로 시뮬레이션하면 80% 확률로 한 단계를 빼먹는다. 시험 시간이 부족해도 표는 꼭 그리자.
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 개념-20] 알고리즘 복잡도 — 시간·공간·빅 오 표기법 (0) | 2026.06.13 |
|---|---|
| [이산구조 개념-19] 검색·정렬·탐욕 알고리즘 — 5가지 핵심 알고리즘 (0) | 2026.06.12 |
| [이산구조 개념-17] 영-일 행렬과 부울린 연산 — 0과 1로 그리는 관계의 지도 (0) | 2026.06.10 |
| [이산구조 개념-16] 행렬의 기초와 연산 — 숫자들의 사각형 세계 (1) | 2026.06.09 |
| [이산구조 개념-15] 함수의 성질과 연산 — 단사·전사·전단사부터 합성까지 (1) | 2026.06.08 |