엔트리-최대공약수-수학적접근

엔트리 -최대공약수-수학적접근

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

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

먼저 간단한 수학개념을 익혀보자
약수란 무엇인가? 어떤 수를 나누어서 나머니가 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가 된다.

 

요구사항

최대공약수를 어떻게 구하지?
구하는 방법부터 고민을 해야 한다.
두 수를 입력받는다.(큰수, 작은수)

각각의 수에 대해 약수를 구한다.

두 약수의 공약수를 구한다.

공약수 중에서 가장 큰 값을 구한다. 이값이 최대공약수이다.

 

이 방식은 최대공약수를 구하는 수학적접근 방식이다.

 

이번 글에서는 엔트리로 최대공약수를 구하는데 수학적 개념을 기반으로 알고리즘을 만들어보았다.

분석 및 설계

. 변수만들기
- i, j : num1, num2 리스트의 인덱스 변수로 활용한다.

- n : 입력

 

* 약수 구하기

. 약수 구하기

  - i < n 때까지 반복하기

    - if ((n / i)의 나머지 = 0

      - num리스트 <- i

    - i = i + 1

 

* 공약수 구하기

i=1

j=1

num1 항목수 번 반복하기

  j <= num2항목수 동안 반복하기

    if num(i) = num(j)    /* 공약수를 찾은 경우 */

       공약수에 num(i) 값 추가

       j = 항목수(num2)

   j = j + 1

i=i+1

j=1

 

* 최대공약수 구하기

i=1

최대공약수=공약수(i)

공약수 항목수-1 번 반복하기

  i=i+1

  if(공약수(i) > 최대공약수

     최대공약수 = 공약수(i)

 

 

 

블럭코딩

* 약수 구하기 (첫번째 수   . n : 키브도로부터 수를 입력받아 n에 저장한다.    . num1에 대한 약수구하기 함수 호출

 

엔트리-공약수구하기 변수 초기화

엔트리-약수구하기 함수 호출

 

* 두번째 수에 대해 약수 구하기   . n : 키브도로부터 수를 입력받아 n에 저장한다.    . num2에 대한 약수구하기 함수 호출

 

 

 

엔트리-약수구하기 (2번째)

 

. 약수 구하기(수, flag) i=1 i < n 때까지 반복하기   if ((n / i)의 나머지 = 0     if flag=1          num1리스트 <- i     else          num2리스트<-i     - i = i + 1

엔트리-약수구하기함수 정의

 

. 공약수 구하기 j=1 num1 항목수 번 반복하기   j <= num2항목수 동안 반복하기     if num(i) = num(j)    /* 공약수를 찾은 경우 */        공약수에 num(i) 값 추가        j = 항목수(num2)    j = j + 1 i=i+1 j=1

 

엔트리-공약수구하기 함수 정의

 

 

. 최대공약수 구하기 i=1 최대공약수=공약수(i) 공약수 항목수-1 번 반복하기   i=i+1   if(공약수(i) > 최대공약수      최대공약수 = 공약수(i)

 

 

* 디버깅

* 초기화

n=6 숫자를 입력받았다.

i=1


* 반복하기

입력한 값 n 까지 1씩 증가하면서 반복한다.

 

 

엔트리-약수구하기 반복

 

* 약수구하기

1부터 n 까지 1씩 증가하면서 n을 i값으로 하나씩 나누어서 나머지가 0인 값을 찾으면 num 리스트에 추가한다.

엔트리-약수구하기 블록코딩

 

약수구하기 디버깅은 아래 글을 참조하기 바란다.

 

엔트리-약수구하기

 

6의 약수 : [1, 2, 3, 6] <- num1

8의 약수 : [1, 2,4, 8] <- num2

 

 

* 공약수 구하기

 

엔트리-공약수구하기

 

 

공약수 리스트 = [1, 2] 

 

* 최대공약수 구하기

공약수 리스트=[1, 2]

i=1

최대공약수=공약수(i)  ; 최대공약수=1

 

공약수 항목수-1 번 반복하기 (2-1 번 반복하기)

i=i+1  (i2)

if(공약수(2) > 최대공약수

   최대공약수 = 공약수(2)  ; 최대공약수=2

 

결과값 : 최대공약수=2

 

* 실행 결과물

 

첫번째 수를 입력받는다. 6을 입력한다.

 

엔트리-최대공약수구하기 수1 입력

 

입력한 수 6에 대한 약수를 num1에 찾아서 추가하였다.

 

엔트리-최대공약수구하기 약수 결과

 

 

두번째 수를 입력한다. 8을 입력한다.

 

엔트리-최대공약수구하기 수2 입력

 

엔트리-최대공약수구하기 약수 결과

 

 

공약수와 최댁공약수 구하기 프로그램을 실행한 결과 화면이다.

공약수는 1, 2이며 이 중에 가장 큰 값인 2가 6과 8의 최대공약수가 된다.

엔트리-최대공약수구하기 실행결과화면

 

 

1차적으로 엔트리를 통해 약수를 찾는 프로그램을 작성해보였고, 이를 기반으로 두 수의 약수를 구하여 공약수를 구하는 프로그램을작성하였고 마지막 단계로는 최대공약수를 구하는 프로그램을 작성하였다.

처음부터 최대공약수를 구하는 것도 재미있지만, 수학적 개념으로 한단계씩 약수를 구하고, 공약수를 구하고 이후에 최대공약수를 구하는 단계로 프로그램을 작성하는 것도 흥미롭게 재미가 있다. 왜냐하면 수학적 개념을 이해하고 이를 프로그램으로 코딩하기 때문이다.

물론 다른 알고리즘으로 최대공약수를 작성하는 프로그램을 스크래치 최대공약수 프로그램을 통해 작성해보았다. 그렇게 작성해도 좋지만, 이런 단계적 프로그램 접근을 통해 수학적 개념의 문제를 푸는 것도 재미가 있다.

 

다음 글에서는 최대공약수를 구하는데 다른 접근으로, 다른 알고리즘으로 최대공약수를 구하는 방법을 작성해 볼 것이다.

 

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

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

MagneticFieldSen