스크래치COS-최대공약수

스크래치 COS -최대공약수

스크래치COS 코딩시험에서 알고리즘의 가장 핵심적인 부분이 변수, 반복문, 조건, 함수이다.

이번 글에는 두수를 입력 받아 최대공약수를 찾는 프로그램을 작성해보자

먼저 간단한 수학개념을 익혀보자
약수란 무엇인가? 어떤 수를 나누어서 나머니가 0인 나누는 수를 약수라 한다. 예를 들어 12의 약수는 1부터 12까지의 자연수 중에서 나누어서 나머지가 0이 되는 수로서 1, 2, 3, 4, 6, 12이다. 반대로 이야기하면 약수는 두 수의 곱으로 나타내어 구할 수도 있다. 12는 1x12, 2x6, 3x4 는 모두 12결과값이다.

공약수는 두 정수에 대하여 공통의 약수가 되는 정수, 즉 두 정수를 모두 나누어떨어뜨리는 정수를 두 정수의 공약수라고 한다. 두 정수 a와 b가 있을 때, a의 약수들의 집합과 b의 약숙들의 집합의 교집합에 속하는 정수가 a와 b의 공약수가 된다.

최대공약수는 a와 b의 공약수의 교집합의 정수들 중에서 가장 큰 수를 a와 b의 최대공약수라고 한다.
예로
12의 약수는 1, 2, 3, 4, 6, 12
8의 약수는 1, 2, 4, 8

8, 12의 공약수는 1, 2, 4 이고, 최대공약수는 4가 된다.

요구사항

최대공약수를 어떻게 구하지?
구하는 방법부터 고민을 해야 한다.
두 수를 입력받는다.(큰수, 작은수)
큰수/작은수의 나머지가 0이면 작은 수가 최대공약수가 된다.
0이 아니면
큰수<-작은수
작은수<-나머지

분석 및 설계

. 변수만들기
- n1, n2 변수 : 키보드로부터 입력받은 수를 저장한다.
- max : 입력받은 수 중에 큰 수를 저장한다.
- min : 입력받은 수 중에 작은 수를 저장한다.
- remainder : max/min의 나머지 값을 저장한다.

. 초기화
- n1과 n2를 비교하여
큰수는 max에 작은수는 min에 저장한다.

. 최대공약수 찾기 알고리즘
remainder가 =일때까지 반복하기
max/min의 나머지를 remainder에 저장한다.

만약 remainder=0, result변수에 min을 저장한다.
아니면
max<-min
min<-remainder

블럭코딩

. 초기화 - 두 수를 입력받아 변수 n1, n2에 저장한다.

스크래치COS-최대공약수 두수입력받기

. 큰수, 작은수 정하기 - n1과 n2를 비교하여 큰수는 max에 작은수는 min에 저장한다. . 초기값으로 remainder=1로 정한다.

* 최대공약수 찾기 알고리즘 remainder가 =일때까지 반복하기 max/min의 나머지를 remainder에 저장한다. 만약 remainder=0, result변수에 min을 저장한다. 아니면 max<-min min<-remainder

스크래치COS-최대공약수 찾기 알고리즘

* 디버깅

* 초기화

n1=8, n2=20 : 8과 20 숫자를 입력받았다.

max=20, min=8
remainder=1 ; 초기값

반복하기

최대공약수-나머지구하기

[1스텝]
max/min 의 나머지 -> remainder
20/8의 나머지(4) -> remainder (4)

remainder가 0이아니기 때문에
max <=8 (min)
min <-4 (remainder)

[2스텝]
max/min 의 나머지 -> remainder
8/4의 나머지(0) -> remainder (0)

remainder=0이기때문에
result=min값을 정한다.
최대공약수를 찾았기 때문에 프로그램은 종료된다.
-> 왜냐하면 조건반복문의 조건이 remainder=0일때까지 반복하기 때문이다.
remainder가 0이 되었으므로 반복문을 빠져나온다.

* 실행 결과물

두 수를 입력받는다. 8, 20을 입력한다.

스크래치COS-최대공약수 n1값 입력받는다.

스크래치COS-최대공약수 n2값 입력받는다.

스크래치COS-최대공약수찾기 실행결과 화면

스크래치를 통해 최대공약수를 찾는 프로그램을 작성해보았다. 수학적 논리로는 두 수의 최대공약수를 찾는 것은 그렇게 어렵지 않다. 그러나 이를 프로그램 코딩으로 구현하기 위해서는 또다른 논리와 창의가 필요하다.
여기서는 큰수/작은수의 나머지가 0일 때 min값이 최대공약수임을 이해하고 코딩을 하였다.

다른 프로그램으로 최소공배수를 찾는 프로그램도 한번 직접 작성해보기를 추천한다.

이런 것을 컴퓨터적 사고방식이라고 한다. 수학적 논리와 창의를 컴퓨터 코딩으로 구현할 때 필요한 사고방식이다. 실제적으로 어떻게 구현할지 변수를 세우고, 하나의 알고리즘을 만들어가며 코딩을 하는 경험이 쌓여야 코딩능력이 향상된다.
그럼 여러분에게도 그런 시간과 능력이 향상되기를 바란다.

다시 한번 강조해서 말하지만, 변수의 값이 각 프로그램 단계별 순차적으로 어떻게 변화하는지 추척하는 것이 매우 중요하다. 블럭을 하나씩 쌓으면서 변수 볼륨 값의 변화를 살펴보자. 코딩은 눈으로 보면서 이해하고 학습하지만 직접 블럭을 쌓으며 이해하고 학습하는 것이 더 효과적이며 창의와 이해의 개념이 ~쑥 늘어납니다.
앞으로의 여러분의 모습을 기대합니다.

Just Do it!!!
Just Drag&Drop!!!

MagneticFieldSen