엔트리-최대공약수-컴퓨터적사고접근

엔트리 -최대공약수-컴퓨터적사고접근

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

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

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

 

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

 

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

 

엔트리-최대공약수 큰수작은수 정하기

 

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

 

엔트리-최대공약수구하기 알고리즘

 

* 디버깅

* 초기화

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

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

반복하기-remainder=0이 될 때까지

 

 

[1스텝]

remainder = max/min의 나머지 (20/8의 나머지 : 4,   remainder(4))

if remainder = 0    (4=0)  (false)

  result=min

else

  max = min           (max = 8)

  min = remainder  (min = 4)

[2스텝]

remainder = max/min의 나머지 (8/4의 나머지 : 0,   remainder(0))

if remainder = 0    (0=0)  (true)

  result=min  (result = 4)

else

  max = min           

  min = remainder  

 

최대공약수는 4이다.

 

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

 

* 실행 결과물

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

 

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

 

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

 

 

엔트리로 작성한 최대공약수구하기 프로그램을 실행한 결과 화면이다.

 

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

 

엔트리로 최대공약수를 구하는 프로그램을 작성해보았다. 이전에 작성한 수학적 접근방식으로 최대공약수를 구하는 프로그램을 작성한 글도 한번 찾아보시기 프로그램을 작성해 보기를 추천한다.

 

같은 결과이지만, 다른 방식과 다른접근 방식으로 프로그램을 작성하였다.무엇이 효율적이고 무엇이 효과적인 것은 일장 일단이 있다. 컴퓨터적 접근 방식은 수학적 개념을 좀더 분석해서 나머지가 0인 수를 찾는데 관점을 가지고 최대공약수를 찾는 방식이다. 

반면에 수학적접근은 약수를 구하고, 약수에 공약수를 구하고 이에 최대공약수를 구하는 방식으로 단계적으로 문제를 푸는 접근으로 프로그램을 작성하였다. 물론 프로그램 실행 등으로 보면 컴퓨터적 사고의 알고리즘으로 작성한 프로그램이 훨씬 효율적이지만 코드를이해하려면 많은 시간과 분석이 필요한 단점이 있다.

그러나 컴퓨터 코딩은 효율을 가장 우선시 하기 때문에 컴퓨터적 사고 방식을 추천하는 바다.

 

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

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

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

MagneticFieldSen