엔트리-공약수구하기

엔트리 -공약수구하기

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

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

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

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

 

요구사항

공약수를 어떻게 구하지? 구하는 방법부터 고민을 해야 한다.
두 수를 입력받는다.

두 수에 대해 약수를 구한다.

그리고 두 수의 약수를 하나씩 비교하면서 같은 수를 공배수 리스트에 추가한다. 교집합 개념이란 두 집합에 같은 수를 의미한다. 컴퓨터 코딩에서는 두 수를 비교하여 같은 경우에 공배수 리스트에 추가하는 개념으로 블록코딩을 할 것이다.

분석 및 설계

. 변수만들기
- n : 키보드로부터 입력받은 수를 저장한다.
- 공약수리스트 : num1과 num2 리스트중에서 같은 수를 추가한다.

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

. 초기화
- i = 1
- n : 키브도로부터 수를 입력받아 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

 

블럭코딩

* 약수 구하기 (첫번째 수   . 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

 

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

 

 

* 디버깅

* 초기화

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

 

 

* 공약수 구하기

num1 = [1, 2, 3, 6]

num2 = [1, 2, 4, 8]

 

i=1

j=1

 

[1스텝]

num1항목수 반복하기 [4번중 1회]

  j<=num2항목수 동안 반복하기 (1 <=4 ) (true)

    if (num1(i) = num2(j)    if 1 = 1 (true)

      공약수<- num1(i)          공약수 = (1)

      j = num2항목수+1         j=4+1 (5)

  j=j+1                                  j=6

i=i+1   (i=2)

j=1     (j=1)

 

[2스텝]

num1항목수 반복하기 [4번중 2회]

  j<=num2항목수 동안 반복하기 (1 <=4 ) (true)

    if (num1(i) = num2(j)    if 2 = 1 (false)

  j=j+1                                  j=2

 

[3스텝]

num1항목수 반복하기 [4번중 2회]

  j<=num2항목수 동안 반복하기 (2 <=4 ) (true)

    if (num1(i) = num2(j)    if 2 = 2 (true)

      공약수<- num1(i)          공약수 = (1, 2)

      j = num2항목수+1         j=4+1 (5)

  j=j+1                                  j=6

i=i+1   (i=3)

j=1

 

[4스텝]

num1항목수 반복하기 [4번중 3회]

  j<=num2항목수 동안 반복하기 (1 <=4 ) (true)

    if (num1(i) = num2(j)    if 3 = 1 (false)

  j=j+1                                  j=2

 

[5스텝]

num1항목수 반복하기 [4번중 3회]

  j<=num2항목수 동안 반복하기 (2 <=4 ) (true)

    if (num1(i) = num2(j)    if 3 = 2 (false)

  j=j+1                                  j=3

 

[6스텝]

num1항목수 반복하기 [4번중 3회]

  j<=num2항목수 동안 반복하기 (3 <=4 ) (true)

    if (num1(i) = num2(j)    if 3 = 4 (false)

  j=j+1                                  j=4

 

[7스텝]

num1항목수 반복하기 [4번중 3회]

  j<=num2항목수 동안 반복하기 (4 <=4 ) (true)

    if (num1(i) = num2(j)    if 3 = 8 (false)

  j=j+1                                  j=5

 

[8스텝]

num1항목수 반복하기 [4번중 3회]

  j<=num2항목수 동안 반복하기 (5 <=4 ) (false)

 

i=i+1  (i=4)

j=1   (j=1)

 

[9스텝]

num1항목수 반복하기 [4번중 4회]

  j<=num2항목수 동안 반복하기 (1 <=4 ) (true)

    if (num1(i) = num2(j)    if 6 = 1 (false)

  j=j+1                                  j=2

 

[10스텝]

num1항목수 반복하기 [4번중 4회]

  j<=num2항목수 동안 반복하기 (2 <=4 ) (true)

    if (num1(i) = num2(j)    if 6 = 2 (false)

  j=j+1                                  j=3

 

[11스텝]

num1항목수 반복하기 [4번중 4회]

  j<=num2항목수 동안 반복하기 (3 <=4 ) (true)

    if (num1(i) = num2(j)    if 6 = 4 (false)

  j=j+1                                  j=4

 

[12스텝]

num1항목수 반복하기 [4번중 4회]

  j<=num2항목수 동안 반복하기 (4 <=4 ) (true)

    if (num1(i) = num2(j)    if 6 = 8 (false)

  j=j+1                                  j=5

 

반복문 종료

 

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

 

* 실행 결과물

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

 

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

 

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

 

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

 

 

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

 

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

 

 

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

 

 

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

 

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

 

 

 

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

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

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

 

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

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

MagneticFieldSen