본문 바로가기
Topos Uranos
한국어

올바른 반복문 설계

요약

반복문 수업은 반복을 쓰는 법을 가르쳤다. 이 수업은 그것을 올바르게 쓰는 법과, 그것이 왜 올바른지 아는 법을 가르친다. 먼저 대부분의 반복문을 짜는 패턴(카운터, 누산기, 최댓값과 최솟값, 보초, 플래그)에서 시작하며, 각 패턴은 그 변수가 매 회차 뒤에 무엇을 의미하는가로 정의된다. 이 관찰은 중심 개념으로 이어진다. 바로 불변식으로, 변수들에 관한 명제이며 첫 회차 전과 매 회차 뒤에 성립하고, 반복문을 빠져나오는 조건과 함께 결과를 함의한다. 이것은 회차 수에 대한 귀납법이며, 이를 이용하면 반복문을 거꾸로 설계하게 된다. 먼저 끝에서 성립해야 할 것, 그 뒤에 불변식, 마지막으로 본문이다. 종료성은 변량으로 정당화하는데, 변량은 이미 문제에서 알고리즘으로 수업에서 소개했다. 그리고 이 수업은 끝나지 않는 반복문 세 가지를 보여 준다. 실수 조건을 쓰는 것, 부호 없는 카운터를 쓰는 것, 그리고 부호 있는 카운터가 오버플로가 나는 것인데, 마지막은 정의되지 않은 동작이다. 끝으로 Visual Studio Code 디버거를 처음으로 다루는데, 디버거는 프로그램을 한 줄에서 멈추고 그 변수들을 회차마다 보여 준다.

학습 목표

  1. 반복문 안에서 카운터, 누산기, 최댓값, 보초의 패턴을 알아보고, 이를 이용해 새로운 반복문을 설계한다.
  2. 간단한 반복문의 불변식을 진술하고, 그것이 임의의 회차에서 유지됨을 확인한다.
  3. 감소하면서 아래로 유계인 정수량으로 반복문의 종료성을 정당화한다.
  4. Visual Studio Code 디버거로 중단점과 변수 보기를 이용해 반복문의 실행을 따라간다.

패턴

변수가 의미하는 것

대부분의 반복문은 발명되는 것이 아니다. 모든 프로그램에 되풀이해 나타나는 몇 안 되는 부품으로 조립된다. 각 부품은 하나의 변수로, 반복문 앞의 초기화, 반복문 안의 갱신, 그리고 무엇보다 매 회차 뒤에 성립하는 의미를 가진다. 부품을 형태가 아니라 의미로 아는 것이 그것들을 오류 없이 조합할 수 있게 해 준다.

  • 카운터의 값은 처리한 데이터의 개수(또는 그중 어떤 조건을 만족하는 것의 개수)이다. 첫 회차 전에는 하나도 처리하지 않았으므로 0으로 초기화하고, 셀 것이 있을 때에만 ++count 식으로 갱신한다.
  • 누산기의 값은 처리한 데이터를 조합한 것, 곧 그 합이나 곱이다. 연산의 항등원(합이면 0, 곱이면 1)으로 초기화하는데, 데이터가 하나도 없을 때의 합은 0이고 곱은 1이기 때문이다.
  • 최댓값의 값은 처리한 데이터 중 가장 큰 것이고, 최솟값의 값은 가장 작은 것이다. 데이터가 하나도 없을 때의 최댓값은 존재하지 않는다. 그래서 최댓값은 첫 번째 데이터로 초기화하며, 아무렇게나 고른 수로 초기화하지 않는다.
  • 보초는 입력에 들어 있는 값으로, 데이터가 아니라 데이터가 끝났다는 신호이다. 이 패턴에서는 반복문 수업에서 0이 나올 때까지 더했을 때처럼 반복문 앞에서 한 번, 본문 끝에서 한 번 더 읽는다. 그러면 조건이 각 값을 처리하기 전에 검사하게 되고, 보초가 데이터로 세어지는 일은 결코 없다.
  • 플래그는 처리한 데이터 가운데 어떤 일이 한 번이라도 일어났는지를 나타내는 bool 값이다. false 값으로 초기화하고, 그 일이 처음 일어날 때 true 값이 된다. 그 뒤의 어떤 회차도 그것을 false 값으로 되돌리지 않는다.

모든 부품을 쓰는 예

강우 기록은 날마다 내린 비의 양을 밀리미터로 적는다. 프로그램은 먼저 기준값을 읽고, 이어서 며칠간의 측정값을 읽는데, 측정값들은 음수 하나로 끝난다. 음수는 측정값이 될 수 없으므로 보초 구실을 한다. 프로그램은 측정값의 개수, 그 평균, 최댓값, 기준값을 넘은 날의 수, 그리고 비가 오지 않은 날이 있었는지를 출력한다.

C++ 프로그램
#include <iostream>#include <print>​int main(){    double threshold{};    std::cin >> threshold;    int count{0};          // 카운터: 처리한 측정값    int aboveCount{0};     // 카운터: 기준값을 넘은 측정값    double total{0.0};     // 누산기: 측정값의 합    double largest{0.0};   // 최댓값: count > 0일 때만 의미가 있다    bool dryDay{false};    // 플래그: 비가 오지 않은 날이 있었다    double value{};    std::cin >> value;    while (std::cin && value >= 0.0) {        if (count == 0 || value > largest) {            largest = value;        }        ++count;        total += value;        if (value > threshold) {            ++aboveCount;        }        if (value == 0.0) {            dryDay = true;        }        std::cin >> value;    }    if (count == 0) {        std::println("측정값이 없다.");    } else {        std::println("측정값: {}개; 평균: {:.2f} mm", count, total / count);        std::println("최댓값: {:.1f} mm; {:.1f} mm 초과 일수: {}", largest, threshold, aboveCount);        std::println("비가 오지 않은 날: {}", dryDay ? "있음" : "없음");    }}
프로그램 입력
104.5 0 12.5 21.5 7.5 -1
출력
측정값: 5개; 평균: 9.20 mm최댓값: 21.5 mm; 10.0 mm 초과 일수: 2비가 오지 않은 날: 있음

네 가지 결정에 대해 설명해 둘 만하다. 조건 count == 0 || value > largest 식은 따로 읽지 않고도 첫 번째 데이터로 최댓값을 초기화한다. 첫 회차에는 카운터가 0이어서 대입이 반드시 일어나고, 그 뒤의 회차들에서는 데이터가 최댓값을 넘을 때에만 일어난다. 비교 value == 0.0 식은 정확한데, 그 값은 계산한 것이 아니라 읽어 들인 것이기 때문이다. 숫자 0 리터럴은 정확한 0으로 변환되며, 부동소수점 수 수업의 == 연산자에 대한 경고는 연산 결과에 관한 것이다. 반복문의 조건에는 std::cin 객체가 들어 있으므로, 보초 없이 끝나는 입력도 반복문을 끝낸다. 그리고 평균은 측정값이 있을 때에만 계산한다. count 변수가 0이면 total / count 식은 0/00/0이 되는데, 이것은 부동소수점에서 오류가 아니라 ‘수가 아님’이라는 값이며, 프로그램은 아무 경고 없이 그것을 출력할 것이다.

예시회차마다 본 변수들

증명

  1. 반복문 전: 기준값은 10, 두 카운터와 누산기는 0, 플래그는 거짓이며, 첫 측정값 4.5는 이미 읽었다. 최댓값은 0이지만, count 변수가 0인 동안 이 값은 아무 의미도 없다.

  2. 첫 번째 회차: count 변수가 0이므로 4.5가 최댓값이 된다. 카운터는 1로, 합계는 4.5로 올라간다. 0을 읽는다.

  3. 두 번째 회차: 0은 최댓값을 넘지 않지만 플래그를 세운다. 12.5를 읽는다.

  4. 세 번째 회차: 12.5는 새로운 최댓값이며 기준값을 넘는다. aboveCount 변수는 1로 올라간다. 21.5를 읽는다.

  5. 네 번째 회차: 21.5는 새로운 최댓값이며 역시 기준값을 넘는다. 7.5를 읽는다.

  6. 다섯 번째 회차: 7.5는 최댓값도 aboveCount 변수도 바꾸지 않는다. 합계는 46에 이른다. −1-1을 읽는다.

  7. 조건은 −1-1을 검사하는데, 이것은 음수이다. 반복문은 그것을 처리하지 않고 끝난다. 평균은 46/5=9.246 / 5 = 9.2이다.

그림의 각 행에서 각 변수가 그때까지 처리한 측정값에 대해 자기 의미를 충족한다는 점에 주목하자. total 변수는 그 합이고, largest 변수는 그 최댓값이며, dryDay 변수는 그 가운데 0이 있었는지를 말해 준다. 매 회차 뒤에 성립하는 이 성질에는 이름이 있다.