[COBOL 기초] 알고리즘 4편: 최대공약수와 최소공배수 구하기 COBOL code

최대공약수(GCD)는 두 수의 공통된 약수 중 가장 큰 수이며, 최소공배수(LCM)는 두 수의 공통된 배수 중 가장 작은 수임. 프로그래밍에서 이를 구하는 가장 효율적인 알고리즘인 '유클리드 호제법'을 코볼 코드로 구현해 본다.

🟪 1. 데이터 영역 설계 (DATA DIVISION)

연산 도중 원본 값이 유실되는 것을 막기 위한 복사본 변수와, 유클리드 나눗셈 회전에 사용할 임시 나머지 변수를 선언함.

cobol code

12345678901234567890123456789012345678901234567890123456789012345678901234567890
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  GCD-LCM-VARIABLES.
*          -------------------------------------------------------------
*          [원본 데이터 변수] 최대공약수와 최소공배수를 구할 두 개의 숫자 (B영역)
*          -------------------------------------------------------------
           05  ORIG-NUM1   PIC 9(03)     VALUE 072.
           05  ORIG-NUM2   PIC 9(03)     VALUE 030.

*          -------------------------------------------------------------
*          [연산용 복사본 변수] 유클리드 호제법 회전 시 값이 변하므로 백업용 변수 활용
*          -------------------------------------------------------------
           05  TEMP-A      PIC 9(03)     VALUE ZERO.
           05  TEMP-B      PIC 9(03)     VALUE ZERO.
           05  CALC-QUO    PIC 9(03)     VALUE ZERO.
           05  CALC-REM    PIC 9(03)     VALUE ZERO.

*          -------------------------------------------------------------
*          [최종 결과 변수] 연산이 완료된 후 답을 담아둘 기억 공간
*          -------------------------------------------------------------
           05  RESULT-GCD  PIC 9(03)     VALUE ZERO.
           05  RESULT-LCM  PIC 9(06)     VALUE ZERO.

---

🟩 2. 유클리드 호제법 루프 및 연산 실행 (PROCEDURE DIVISION)

나머지가 0이 될 때까지 큰 수를 작은 수로 나누는 회전 루프를 돌려 최대공약수를 먼저 구한 뒤, 공식에 대입하여 최소공배수를 일괄 산출함.

cobol code

12345678901234567890123456789012345678901234567890123456789012345678901234567890
       PROCEDURE DIVISION.
       MAIN-LOGIC SECTION.
       A000-START.
           DISPLAY "--- GCD & LCM ALGORITHM START ---".

*          [백업 작업] 원본 값이 파괴되지 않도록 연산용 변수로 이관함
           MOVE ORIG-NUM1 TO TEMP-A.
           MOVE ORIG-NUM2 TO TEMP-B.

*          =============================================================
*          [알고리즘 A] 유클리드 호제법을 이용한 최대공약수(GCD) 추적
*          =============================================================
*          나머지(CALC-REM)가 0이 될 때까지 무한 회전 구동함
*          처음 진입을 위해 조건을 충족하도록 임의의 값(1)을 미리 넣어두거나 수행
           DIVIDE TEMP-A BY TEMP-B GIVING CALC-QUO REMAINDER CALC-REM.

           PERFORM UNTIL CALC-REM = 0
*              나머지가 0이 아니면, 나누었던 수(B)를 새로운 A로 보냄
               MOVE TEMP-B TO TEMP-A
*              방금 나온 나머지(REM)를 새로운 B로 보낸 뒤 다시 나눔
               MOVE CALC-REM TO TEMP-B
               
               DIVIDE TEMP-A BY TEMP-B GIVING CALC-QUO REMAINDER CALC-REM
           END-PERFORM.

*          루프를 탈출하는 순간 나누었던 수(TEMP-B)가 곧 최종 최대공약수(GCD)가 됨
           MOVE TEMP-B TO RESULT-GCD.

*          =============================================================
*          [알고리즘 B] 수학 공식을 활용한 최소공배수(LCM) 산출
*          =============================================================
*          공식: 최소공배수 = (두 원본 수의 곱) / 최대공약수
           COMPUTE RESULT-LCM = (ORIG-NUM1 * ORIG-NUM2) / RESULT-GCD.

*          -------------------------------------------------------------
*          [결과 출력] 72와 30의 연산 데이터 결과 매칭 표출
*          -------------------------------------------------------------
           DISPLAY "ORIGINAL NUMBERS : " ORIG-NUM1 " AND " ORIG-NUM2.
           DISPLAY "MAX GCD RESULT   : " RESULT-GCD.
*          -> 정상 구동 시 72와 30의 최대 공약수인 '006'이 화면에 표출됨.

           DISPLAY "MIN LCM RESULT   : " RESULT-LCM.
*          -> 정상 구동 시 공식에 의해 산출된 최소 공배수 '000360'이 표출됨.

           STOP RUN.

---

💡 [실무 팁] 유클리드 호제법의 원리와 변수 백업 처리를 하는 이유

정보처리기능사 실기 시험장에서 변수 구조도를 그릴 때 빼놓으면 즉시 오답으로 이어지는 핵심 개념을 짚어봄.

• 왜 원본 변수를 그대로 쓰지 않고 복사할까?
  • 유클리드 알고리즘은 나누는 수와 나머지를 끊임없이 바꾸는 성질(A ➡️ B, REM ➡️ B)을 가짐.
  • 만약 복사본 없이 ORIG-NUM1을 그대로 제어 연산에 사용했다면 최소공배수를 구하는 식인 (ORIG-NUM1 * ORIG-NUM2) 단계를 만났을 때 이미 원본 숫자가 다른 값으로 오염되어 완전히 엉뚱한 결괏값이 도출됨.
  • 배치 시스템 설계 시 '연산 프로세스를 거치는 원본 마스터 데이터는 절대로 중간에 훼손하지 않는다'는 규칙을 증명하는 예제임.
• 코볼 연산 자릿수와 오버플로우(Overflow) 방어 규칙
  • RESULT-LCM 변수를 정의할 때 원본 자릿수(PIC 9(03))보다 훨씬 여유로운 PIC 9(06) 구역을 확보해 두었음.
  • 최소공배수 공식 분자 영역인 ORIG-NUM1 * ORIG-NUM2 계산 시 72 * 30 = 2160이라는 4자리 숫자가 일시적으로 발생하기 때문에, 결과 저장소 공간이 너무 작으면 데이터가 잘려 나가는 버그(Truncation)가 생김. 곱셈 결과가 담길 저장 공간은 항상 넉넉하게 산정하는 것이 필수 원칙이다.