직관 — 가장 큰 기록을 한 칸에 보관한다
기록 카드를 한 장씩 읽으면서 지금까지 본 가장 큰 수를 메모한다. 새 카드가 더 크면 메모를 바꾸고, 그렇지 않으면 그대로 둔다. 마지막 카드까지 확인하면 메모에 전체의 최댓값이 남는다.
카드들은 입력, 마지막 메모는 출력이다. 중간에 무엇을 비교하고 언제 멈추는지까지 정해야 누구나 같은 절차를 따라 할 수 있다. 수열의 값을 만드는 규칙을 배웠다면, 이제 문제 해결 절차 자체를 읽고 표현해 보자. 컴퓨터 프로그램도 이렇게 정한 절차를 프로그래밍 언어로 옮긴 것이다.
알고리즘의 표현은 절차의 순서와 조건을 명확히 적는 일이다
알고리즘은 허용된 입력에 대해 원하는 출력을 얻도록 정한 명확한 유한 절차다. 순서도는 도형과 화살표로, 의사코드는 사람이 읽을 수 있는 명령문으로 같은 절차를 표현한다. 의사코드는 특정 프로그래밍 언어의 실행 코드와 같지 않다.
절차가 알고리즘이 되려면 입력과 원하는 출력이 정해져 있고, 각 단계의 뜻이 하나로 정해져야 한다. 또 허용된 모든 입력에서 유한 번 만에 끝나야 한다. ‘적당히 큰 수를 고른다’처럼 사람마다 다르게 할 수 있는 단계나, 끝나지 않는 반복이 있으면 알고리즘이 아니다.
여기서는 실수 이 주어지고 인 유한 목록을 다룬다. 원하는 출력은 목록에 실제로 있는 값 중 가장 큰 값이다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 입력 값 | input value | 목록의 i번째 실수 | |
| 목록 길이 | length | 1 이상의 정수 | |
| 확인할 위치 | index | 다음에 비교할 카드 번호 | |
| 현재 최댓값 | running maximum | 지금까지 확인한 값 중 최댓값 | |
| 대입 | assignment | 오른쪽 값을 계산해 왼쪽에 저장 | |
| 최댓값 | maximum | 주어진 값 중 가장 큰 값 |
대입은 등식과 역할이 다르다. 은 기존 번호에 1을 더해 저장하라는 명령이다. 이를 등식 이라고 읽지 않는다. 목록의 위치는 1부터 세고, 마지막을 넘어서면 입력 값을 더 읽지 않는다.
같은 절차를 의사코드와 순서도로 읽어 보자
첫 값을 메모에 넣고, 두 번째 위치부터 비교한다. 아래의 들여쓰기는 반복 안에서 실행할 명령을 나타낸다. [반환]은 값을 결과로 돌려주고 이 실행을 끝낸다는 뜻이다.
[정의] 최댓값(a₁, …, aₙ): # n ≥ 1
M ← a₁
i ← 2
[반복] i ≤ n인 동안:
[조건] aᵢ > M이면:
M ← aᵢ
i ← i + 1
[반환] M
조건에 맞지 않으면 을 바꾸지 않는다. 하지만 는 어느 경우든 1 증가한다. i ← i + 1을 조건문 안으로 잘못 들여쓰면 더 크지 않은 값을 만날 때 같은 카드를 끝없이 읽을 수 있다.
그림 1은 이 의사코드의 순서도다. 둥근 칸은 시작·끝, 사각형은 처리(값 저장), 마름모는 판단, 평행사변형은 입력이다. 출력은 교과서처럼 아래쪽이 물결 모양인 기호로 그렸다. T는 조건이 참, F는 거짓인 길이고, IN은 입력, OUT은 출력을 뜻한다. 왼쪽으로 돌아가는 흐름선이 반복을 나타낸다.
figures/maximum_flow.py교과서는 결과를 나타낼 때 [출력]을 쓴다. 이 글의 [반환]과 같은 자리다. 정해진 범위를 차례로 도는 반복은 [반복] i=2부터 n까지:처럼 적기도 한다. 이 꼴은 반복이 끝날 때마다 가 1씩 커진다는 약속을 담고 있어서, 을 따로 적지 않는다.
음수와 같은 값이 있어도 절차가 맞을까?
값의 크기만 비교하므로 음수와 같은 값도 처리한다. 입력을 , , , , 의 순서로 주면 로 시작한다.
| 확인할 위치 | 읽은 값 | 비교 | 비교 뒤 M |
|---|---|---|---|
| 2 | 7 | 참 | 7 |
| 3 | 2 | 거짓 | 7 |
| 4 | 7 | 거짓 | 7 |
| 5 | −1 | 거짓 | 7 |
그다음 이면 가 거짓이므로 끝난다. 같은 최댓값 7이 두 번 있어도 출력은 값 7 하나다. 어느 위치인지까지 요구하는 문제는 위치를 저장하는 변수를 별도로 정해야 한다.
그림 2는 이 표를 그래프로 옮겼다. 막대는 각 위치의 입력 값이고, 점은 그 위치까지 비교한 뒤의 이다. 비교는 네 번이지만 이 바뀐 것은 위치 2에서 한 번뿐이다. 위치 4의 7은 이 거짓이라 메모를 바꾸지 않는다.
figures/maximum_trace.py왜 최댓값을 놓치지 않고 반드시 끝날까?
처음 은 첫 카드까지의 최댓값이다. 이미 확인한 카드들의 최댓값이 이라고 하자. 새 값이 더 크면 새 값으로 바꾸고, 그렇지 않으면 기존 값을 유지하므로 새 카드까지의 최댓값이 다시 에 남는다.
이 관계는 매번 유지된다. 마지막 카드까지 읽었을 때 식 (2)가 식 (1)이 되므로 결과가 맞다. 예제 네 번의 비교가 모든 입력을 증명하는 것은 아니며, 이 ‘이미 본 범위의 최댓값 유지’가 일반적인 이유다. 처음에 맞고 한 단계 뒤에도 맞음을 보이는 이 논증은 수학적 귀납법과 같은 구조다.
또한 반복 본문을 한 번 실행하면 정수 가 정확히 1 커진다. 비교할 위치는 2부터 까지여서 반복은 번이며, 이면 0번이다. 올바른 값을 얻는 이유와 유한 번에 끝나는 이유를 둘 다 확인해야 한다. 이것은 재귀적 알고리즘에서도 중요하다.
순서도의 출력값은 변수의 변화를 표로 추적해 구한다
순서도가 출력하는 값을 묻는 문제는 반복할 때마다 바뀌는 변수를 표에 적어 가며 푼다. 1부터 까지 더하는 그림 3의 순서도에 를 넣으면 출력은 15다. 아래에서 는 지금까지의 합, 는 다음에 더할 수다.
[정의] 합(n): # 정수 n ≥ 1
S ← 0
k ← 1
[반복] k ≤ n인 동안:
S ← S + k
k ← k + 1
[반환] S
figures/sum_flow.py| 반복 | 더한 k | 더한 뒤 S | 다음 k |
|---|---|---|---|
| 1 | 1 | 1 | 2 |
| 2 | 2 | 3 | 3 |
| 3 | 3 | 6 | 4 |
| 4 | 4 | 10 | 5 |
| 5 | 5 | 15 | 6 |
이 되면 가 거짓이므로 15를 출력하고 끝난다. 반복은 다섯 번이고, 끝난 뒤 는 이다. 번 반복한 뒤의 를 라 하면, 가 바뀌는 규칙은 귀납적으로 정의한 수열과 같다.
식 (3)의 는 1부터 까지의 합이므로 시그마의 공식 와 같고, 에서 15다. 순서도는 이 점화식을 한 줄씩 계산하는 절차다.
반복 조건의 등호 하나가 결과를 바꾼다. 조건을 으로 바꾸면 에서 가 거짓이라 마지막 5를 더하지 못하고 10을 출력한다. 그림 4에서 두 조건은 네 번째 반복까지 같은 값을 지나다가 마지막 한 번에서 갈린다. 마지막 반복에서 조건이 참인지 직접 확인하는 습관이 이런 오류를 막는다.
figures/sum_trace.py알고리즘의 표현은 입력·출력·분기·반복·종료를 명확히 담는다. 비어 있지 않은 길이 n의 실수 목록은 첫 값을 M에 저장하고 나머지 n−1개를 비교하여 최댓값을 얻는다.
알고리즘의 최댓값 메모를 0으로 시작해도 되나요?
항상 그런 것은 아니다. 입력이 모두 음수인 이면 0을 바꾸지 못해 목록에도 없는 값을 출력한다. 입력의 첫 값으로 시작하면 이런 가정을 추가할 필요가 없다.
알고리즘의 입력이 비어 있으면 무엇을 출력하나요?
이 최댓값 알고리즘에서는 빈 입력을 허용하지 않는다. 첫 값 이 없고 실수의 빈 목록에는 최댓값도 없기 때문이다. 빈 목록을 처리할 서비스라면 ‘값 없음’ 같은 별도 결과와 분기를 먼저 설계한다.
알고리즘의 순서도와 의사코드는 무엇이 다른가요?
같은 알고리즘을 도형과 흐름선으로 그리면 순서도, 들여쓴 명령문으로 적으면 의사코드다. 순서도는 갈림길과 되돌아가는 흐름이 한눈에 보이고, 의사코드는 줄 단위로 읽고 고치기 쉽다. 그림 1의 마름모 두 개가 의사코드의 [반복]과 [조건] 두 줄에 대응하며, 모양은 달라도 비교·저장·반환의 순서가 같으면 같은 절차다.
알고리즘을 읽을 때 생기는 오해
- 한 예제에서 맞았으니 어떤 입력에서도 맞는다 — 초기값 0도 양수 목록에서는 우연히 맞을 수 있다. 입력 조건 전체에 대한 이유와 반례를 확인한다.
- 같은 값이면 비교 횟수를 세지 않는다 — 이 거짓인지 판단하는 것도 비교 한 번이다. 값을 바꾼 횟수와 비교 횟수는 다르다.
- 의사코드는 그대로 컴퓨터에서 실행된다 —
[반복] k ≤ n인 동안:같은 줄은 사람이 읽는 약속이다. 엄밀한 문법이 없으므로 프로그래밍 언어의 문법에 맞게 옮겨야 실행된다.
직접 해보기
- 입력 에서 초기 M과 각 비교 뒤 M, 최종 출력을 적자.
답
초기 M은 다. 이후 , , 가 되며 출력은 다. 비교는 3번, M을 바꾸는 일은 1번이다.
- 한 값 만 입력하면 첫 조건 판단 때 i는 얼마이며 몇 번 비교하는가?
답
, 이므로 반복 조건이 처음부터 거짓이다. 입력 값끼리의 비교는 0번이며, 처음 저장한 을 반환한다.
- 입력 에서 i를 늘리는 명령을 ‘새 값이 더 클 때’에만 실행하면 어떤 일이 생기는가?
답
처음 에서 가 거짓이므로 M도 i도 바뀌지 않는다. 계속 같은 1만 확인하여 9에 도달하지 못한다. 번호 증가는 조건문의 바깥, 반복문의 안에 둬야 한다.
- 입력 에서 최댓값이 처음 나온 위치도 함께 얻으려면 어떻게 고칠까?
답
초기에 위치 을 저장하고, 이 참일 때 M과 함께 를 저장한다. 엄격한 부등호를 유지하므로 같은 8을 다시 만나도 위치를 바꾸지 않아 결과는 값 8과 위치 2다. 조건을 으로 바꾸면 마지막 위치 3이 남는다.
- 그림 3의 처리 칸 를 로 바꾸고 을 넣으면 출력은 얼마인가? 반복은 몇 번이고, 끝난 뒤 는 얼마인가?
답
더하는 수는 1, 3, 5, 7, 9, 11이므로 출력은 36이다. 반복은 부터 6까지 여섯 번이고, 끝난 뒤 이다. 홀수 여섯 개의 합이 인 것과 같다.
더 읽기
- 교육부 고시 제2022-33호 — 별책20 [12이수02-03]과 해설의 순서도·의사코드 범위.
- 우리교과서 『이산 수학』 공개 원문 — 이준열 외, 인쇄66–67쪽의 알고리즘 정의, 순서도 기호(시작과 끝·처리·판단·출력·흐름선)와 의사코드 표기. 교과서는 버블 정렬로 두 표현을 연결하며, 이 글은 최댓값 찾기와 합을 새 예로 구성했다.
영상 노트
- 00:00 기록을 한 장씩 보아도 최댓값을 찾을 수 있을까?
- 00:35 식 (1)의 입력 범위와 첫 메모 정하기
- 01:15 그림 1과 의사코드의 두 분기, 교과서의 [출력] 표기 대응하기
- 02:10 다섯 입력의 비교 표를 그림 2로 따라가기
- 03:00 식 (2)의 유지와 n−1번 종료를 따로 설명하기
- 03:50 그림 3의 순서도를 표로 추적해 출력 15 구하기
- 04:40 식 (3)과 그림 4로 k ≤ n과 k < n의 차이 보기
지도에서의 위치
- 2026-11-16 · 독립 검수 AR1 — 비교 횟수와 입력 위치를 구별하도록 불변식 문구를 바로잡음
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 순서도에 끝 단말과 교과서의 출력 기호를 넣고, 알고리즘의 조건, 교과서 의사코드 표기와의 대응, 최댓값 추적 그림, 1부터 n까지의 합과 순서도 출력값 문제, 반복 조건의 경계, 연습 5문항으로 보강 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림