엔트리-최소공배수

엔트리-최소공배수

 

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

 

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

 

어떤 수 a의 배수는 a*1, a*2, a*3, a*4, a*5,,,수로 예로 4의 배수는 4, 8, 12, 16, 20이고 6의 배수는 6, 12,18, 24, 30,,, 등이다. 공배수란 두 수의 배수 들 중에 공통의 배수가 되는 정수이다. 예로 4와 6의 공배수는 12, 24, 36,,, 등이 있다.

최소공배수란 공배수 중에서 가장 작은 값을 의미한다. 위의 예로 4와 6의 최소공배수는 12이가 된다.

 

[[질문]]

. 어떻게 공배수와 최소공배수를 찾을 것인가?

  . 각 수의 공배수를 구한다. 

     [문제] 어디까지 배수를 구할 것인가?

 

-> 그렇다면 다른 측면으로 고민을 해봐야 할 것이다.

공배수는 두 수로 각각 나누었을 때, 모두 나머지가 0인 수이다.

최소공배수는 두 수중 큰 값을 공배수로 설정하고 두 수로 나누어 나머지가 0인 경우 최소공배수로 지정하면 된다.

 

요구사항

최소공배수는 어떻게 구하지?

두  수를 각각 나누어서 나머지가 0인 수를 공배수로 한다.

그럼 최소공배수는 어떻게 구할 것인가?

두 수 중에 큰 값부터 시작해서 1씩 증가시켜가며 두 수를 나누어 나머지가 0인 최초의 값이 최소공배수가 된다.

 

 

분석 및 설계

. 변수만들기

  - n1, n2 변수 : 키보드로부터 입력받은 수를 저장한다.

  - n은 최소공배수를 저장한다.

    - 초기값은 n1과 n2 두 수중에 큰 값을 초기값으로 가진다.

    - 이후에는 1씩 증가시켜 가면 나머지가 0인 수를 찾는다.

 

. 초기화

  - n1과 n2를 두 수를 키보드로 입력받아 저장한다.

  - n값은 n1과 n2 값 중에 큰 값을 초기값으로 저장한다.

 

. 최소공배수 찾기 알고리즘

  - n1/n의 나머지=0 이고(and) n2/n의 나머지=0 이면

     최소공배수는 n이 된다.

  - 아니라면 n을 1 증가시킨다.

 

블럭코딩

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

 

엔트리-최소공배수 두수 입력

 

. n은 최소공배수를 저장한다.     - 초기값은 n1과 n2 두 수중에 큰 값을 초기값으로 가진다.     - 이후에는 1씩 증가시켜 가면 나머지가 0인 수를 찾는다.

엔트리-최소공배수 초기값 큰수 설정

 

. 최소공배수 찾기 알고리즘   - n1/n의 나머지=0 이고(and) n2/n의 나머지=0 이면      최소공배수는 n이 된다.   - 아니라면 n을 1 증가시킨다.

 

엔트리-최소공배수 찾기 알고리즘

 

* 디버깅

* 초기화

 

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

 

n=8

 

* 최소공배수 알고리즘

 

[1스텝]

n/n1의 나머지 and n/n2의 나머지

8/3의 나머지(2) and 8/8의 나머지(0) : false

 

n을 1만큼 증가 : 9

 

[2스텝]

n/n1의 나머지 and n/n2의 나머지

9/3의 나머지(0) and 9/8의 나머지(1) : false

 

n을 1만큼 증가 : 10

 

[3스텝]

n/n1의 나머지 and n/n2의 나머지

10/3의 나머지(1) and 10/8의 나머지(2) : false

 

n을 1만큼 증가 : 11

 

.....

 

[17스텝]

n/n1의 나머지 and n/n2의 나머지

24/3의 나머지(0) and 24/8의 나머지(0) : true

 

최소공배수 n = 24

 

 

* 실행 결과물

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

 

엔트리-최소공배수 수 입력받기

 

 

엔트리-최소공배수 수 입력

 

엔트리-최소공배수 실행결과 화면

 

 

엔트리를 통해 최소공배수를 찾는 프로그램을 작성해보았다. 수학적 논리로는 두 수의 최소공배수를 찾는 것은 그렇게 어렵지 않다. 그러나 이를 프로그램 코딩으로 구현하기 위해서는 또다른 논리와 창의가 필요하다.

여기서는 공배수 값을 하나씩 증가시켜가며 최소공배수를 찾았는데, 프로그램 구현상 논리와 창의는 한가지의 길이 아니라 여러 방법으로 구현이 가능한다.

지금까지는 이야기를 하지않았지만, 프로그램으로 구현하는 것만이 이제는 목표가 아니라, 프로그램 실행에 있어 최소의 시간, 최적의 코딩양 등을 목표로 코드를 최적화하는 방법을 찾기를 바란다.

이 방법 외에도 다양한 최소공배수를 찾는 알고리즘이 많을 것이다.

 

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

앞으로의 여러분의 모습을 기대합니다.

 

Just Do it!!!

Just Drag&Drop!!!

 

MagneticFieldSen