DataStructure

자료구조1 과제 제출용 레포

과제(3)

1) ADT

분수 추상 자료형

분수는 정수형 분자(numerator)와 분모(denominator)로 구성된다.

• numerator: int (분자)
• denominator: int (분모)

단, 분모는 0이 될 수 없다.

---

연산

분수는 다음과 같은 기본 연산을 지원한다.

• add(a, b): 두 분수의 덧셈 (+)
• sub(a, b): 두 분수의 뺄셈 (-)
• multiply(a, b): 두 분수의 곱셈 (*)
• divide(a, b): 두 분수의 나눗셈 (/)

두 분수의 연산 결과는 하나의 분수로 반환되며, 모든 결과는 기약분수 형태로 출력된다.

---

추가 기능

분수 ADT는 다음과 같은 추가 연산을 제공한다.

• reduce(f): 하나의 분수를 입력받아 기약분수로 변환하여 반환한다.
• parseFraction(str): "A/B" 또는 정수/소수 형태의 문자열을 입력받아 Fraction 자료형으로 변환한다.
• printFraction(f): Fraction 자료형을 "A/B" 또는 기약분수 형태로 출력한다. (분모가 1이면 정수로 출력)

---

파일 구성

아래와 같이 3가지 파일을 구성한다.

• my_fraction.h: 분수 자료형 및 함수 선언
• my_fraction.c: 분수 연산 및 기능 구현
• main.c: 프로그램 실행 및 입력 처리

main.c에서는 my_fraction.h를 include하여 사용한다.

---

입력 형식 (Input)

입력은 다음과 같은 형식으로 주어진다.

[분수] [연산자] [분수]

--------------- 아래부터 과제 3의 2번

2) GCD, LCM

이 프로그램은 두 개의 정수를 입력받아 최대 공약수(GCD)와 최소 공배수(LCM)를 계산하는 프로그램이다.

• GCD는 유클리드 호제법을 이용하여 계산한다.

최대 공약수

function gcd(a, b):
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

두 정수 a와 b에 대해 나머지를 반복적으로 계산하며, b가 0이 되는 순간의 a 값이 최대 공약수가 된다.

예시:

gcd(18, 24)
24 % 18 = 6
18 % 6 = 0 → GCD = 6

최소 공배수

function lcm(a, b):
    return (a * b) / gcd(a, b)

최소 공배수는 두 수의 곱을 최대 공약수로 나누어 구할 수 있다.

예시:

lcm(18, 24) = (18 × 24) / 6 = 72