[알고리듬] #58 A와 B의 관계

파이썬 실습창을 열 수 있습니다.실습창 열기

 

 

A와 B의 관계

 

두 수 A, B가 있습니다.
A와 B의 관계가 다음과 같을 때, 'A + B'를 구하여 보세요.

A * B =360
A - B =9

 

 

1. 문제 분석

A와 B는 어떤 숫자일까?

• 상식적으로 생각하면 A와 B는 양의 정수입니다.
  굳이 따진다면 음수나 실수도 가능할 수 있지만 양의 정수로 보는 것이 타당합니다.
• 또한, A와 B는 A * B = 360 이므로 1이상 360이하의 정수입니다.
  A와 B는 분수가 아닐 것이기 때문입니다.
• 또, A - B = 9 이므로 A는 B보다 큰 수입니다.
• 정리하면 'A와 B는 1이상 360이하의 정수이며, A가 B보다 크다.'입니다.

2.  알고리듬 설계

많은 사람들이 방정식을 생각할 것입니다.

• 방정식은 여러 문제해결 방법 중의 한가지입니다.
  방정식 보다 더 좋은 방법이 있을 수 있습니다.
• 컴퓨터에서 방정식 방법으로 해결할 수 있지만 복잡합니다(확장 행렬 등의 사용).
• 문제 해결의 가장 기본적인 방법은 모든 경우를 조사하는 것입니다.
  모든 방법을 조사하는 것을 먼저 생각하고, 그 다음에 더 좋은 방법을 생각합니다.

● 모든 경우 조사

이 문제에서 모든 경우는 어떠한 경우일까요?

A가 1이고 B가 1인 경우,  A가 1이고 B가 2인 경우, ... ,A가 1이고 B가 360인 경우

A가 2이고 B가 1인 경우,  A가 2이고 B가 2인 경우, ... ,A가 2이고 B가 360인 경우

:

:

A가 360이고 B가 1인 경우,  A가 360이고 B가 2인 경우, ... ,A가 360이고 B가 360인 경우

 

이렇게 129600 (=360*360)가지 경우를 모두 조사하여 문제의 조건에 맞는 경우를 찾으면 됩니다.

컴퓨터는 빠르니까 금방 찾을 것입니다.

이 방법을 사용하여 봅시다.

 

[참고] 상태공간 트리

• 모든 경우를 조사하는 방법을 저돌적 방법(brute-force method), 순진한 방법(native method), 순차적 방법(sequence method)  등으로 부릅니다.
• 또한, 모든 경우를 상태공간 트리(status-space tree, 수형도)라 합니다.
  상테공간 트리에서 해(답)를 찾는 것이 문제 해결의 기본 개념입니다.
• 자세한 문제해결전략(problem solving strategy)은 다음에 공부합니다.

3. 코딩하기

코딩에 도전하시겠습니까?

mul,sub=360,9                         # A와 B를 곱한 값과 뺀 값
for a in range(1,mul+1):
    for b in range(1,mul+1):
        if a*b==mul and a-b==sub:
            add=a+b
print(add) 

'''
조금 개선한 방법도 있습니다.
불필요한 검사를 제거하여 실행시간을 단축할 수 있습니다.
mul,sub=360,9               
for a in range(1,mul+1):    
    b=mul//a          # b를 계산으로 찾음  
    if a-b==sub:      # 곱셈을 확인할 필요가 없음   
        add=a+b
        break         # 답을 찾았으면 for문을 벗어남
print(add) 
'''

 

모든 경우를 조사하는 상태공간 트리 방법은 많이 사용되는 쉽고 좋은 방법입니다.

모든 경우를 조사하는 방법에 익숙해지도록 여러 문제들을 제시하겠습니다.

오늘도 수고하셨습니다.

안녕!