무냐의 개발일지
[OSSU] <MITx 6.00.1x_Intro CS> Week2/ Bisection Search, Loop, Binary, Iteration/Recursive (복잡한 문제해결엔 Recursive!) 본문
[OSSU] <MITx 6.00.1x_Intro CS> Week2/ Bisection Search, Loop, Binary, Iteration/Recursive (복잡한 문제해결엔 Recursive!)
무냐코드 2024. 4. 16. 21:58👩💻 문제
iteration = 0
while iteration < 5:
count = 0
for letter in "hello, world":
count += 1
if iteration % 2 == 0:
break
print("Iteration " + str(iteration) + "; count is: " + str(count))
iteration += 1
💡 결과
Iteration 0; count is: 1
Iteration 1; count is: 12
Iteration 2; count is: 1
Iteration 3; count is: 12
Iteration 4; count is: 1
✍️ 해설
while 문 안에서 나머지가 계속 돌아가는 거니까, iteration이 4가 될때까지 반복 (총 4회)
그 안에서 for 문은 그 아래가 계속 돌아가는 거니까
iteration = 0 일때는 count + 1 하고 멈춤
iteration = 1 일때는 count +1+1+1+1+1+1+1+1+1+1+1+1 하고 멈춤
이런 식으로 반복되는거임
🥳 배운점
for문, while문을 정확히 다시 이해했다
👩💻 문제
In this problem, you'll create a program that guesses a secret number!
The program works as follows: you (the user) thinks of an integer between 0 (inclusive) and 100 (not inclusive). The computer makes guesses, and you give it input - is its guess too high or too low? Using bisection search, the computer will guess the user's secret number!
Here is a transcript of an example session:
Please think of a number between 0 and 100!
Is your secret number 50?
Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. l
Is your secret number 75?
Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. l
Is your secret number 87?
Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. h
When the user enters something invalid, you should print out a message to the user explaining you did not understand their input. Then, you should re-ask the question, and prompt again for input. For example:
Is your secret number 91?
Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. y
Sorry, I did not understand your input.
💡 풀이 #1 (내가 푼 거)
low = 0
high = 100
guess = (low+high)//2
print('Please think of a number between 0 and 100!: ')
print(f'Is your secret number {guess}?')
answer = input("Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly.")
while answer != 'c':
if answer not in ['h','l','c']:
print('Sorry, I did not understand your input.')
else:
if answer == 'h':
high = guess
elif answer == 'l':
low = guess
guess = (low+high)//2
print(f'Is your secret number {guess}?')
answer = input("Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly.")
print('Game over. Your secret number was: ',guess)
💡 풀이 #2 (교수님 답안 _ 더 깔끔하다)
print("Please think of a number between 0 and 100!")
# At the start the highest the number could be is 100 and the lowest is 0.
hi = 100
lo = 0
guessed = False
# Loop until we guess it correctly
while not guessed:
# Bisection search: guess the midpoint between our current high and low guesses
guess = (hi + lo)//2
print("Is your secret number " + str(guess)+ "?")
user_inp = input("Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. ")
if user_inp == 'c':
# We got it right!
guessed = True
elif user_inp == 'h':
# Guess was too high. So make the current guess the highest possible guess.
hi = guess
elif user_inp == 'l':
# Guess was too low. So make the current guess the lowest possible guess.
lo = guess
else:
print("Sorry, I did not understand your input.")
print('Game over. Your secret number was: ' + str(guess))
✍️ 해설
조금씩 절반 자르는 지점을 대답에 따라 좁혀가면서 답을 찾는 문제이다.
input함수를 사용하여 구현하고, while, if문으로 해결 가능하다
🥳 배운점
guessed = False로 두고 c일 경우 True로 바꿔주는 아이디어가 새로웠다.
몫을 구하는 // 를 쓴 것도 그렇고.
그리고 나는 입력값이 c,l,h 일때를 별도로 떼서 생각했는데,
교수님은 아예 하나의 if문으로 묶어서, c,l,h아닌 모든 경우 에러메세지가 나오도록 설정하였다.
이게 훨씬 깔끔했다.
👩💻 이진수 구하는 법
LEET 코드에 나왔는데 여기서 개념을 설명해주네! 십진법을 이진법으로 구하는 원리말이야
💡 코드
#Int to Binary
num = 64
if num<0:
isNeg =True
num = abs(num)
else:
isNeg=False
result= ''
if num==0:
result = '0'
while num>0:
result = str(num%2) + result #이렇게 하면 구한 나머지가 새로 구하는 애들 뒤로 밀린다
num = num//2
if isNeg:
result = '-'+result
print(result)
10진법 정수가 아닌 유리수를 이진법으로 바꾸려면?
2의 제곱수를 곱해서 이 수를 정수로 일단 만들고 -> 이걸 이진법으로 표현 후 -> 곱해줬던 2의 제곱수만큼 소숫점을 앞으로 옮겨주면 됨!!
💡 코드
#float to Binary
x = float(input('Enter decimal number btw 0 and 1 : '))
p=0
while (x * (2**p)) % 1 != 0: #x에 2의 거듭제곱을 곱한게 정수가 될 때까지 반복
print('Remainder : '+str(x*(2**p)- int(x*(2**p))))
p += 1
num = int(x * (2**p)) #최종적으로 2의 거듭제곱을 곱해서 정수가 된 애를 num
#이제 num을 2진수로 바꿔야겠지
result = ''
if num ==0:
result = '0'
while num>0:
result = str(num%2) + result
num = num //2
#이제 소숫점을 다시 복원시켜줘야겠지 2^p 만큼 옮겨놨으니까
#만약 7자리를 해야한다고 하면, 이진수 111이라고 했을 때, 0.0000111 이니까
#len(num)= 3, p = 7, 만들어야하는 0는 5개
for i in range(p-len(result)): #0,1,2,3,4니까 5개 !
result = '0'+ result
result = result[0] + '.' + result[1:]
print('The binary representation of Decimal '+ str(x) + ' is '+ result)💡 결과
Enter decimal number btw 0 and 1 : 0.375
Remainder : 0.375
Remainder : 0.75
Remainder : 0.5
The binary representation of Decimal 0.375 is 0.11
근데 만약에 이걸 정수로 만들어주는 2의 제곱수가 없다고 한다면?
If there is no integer p such that a power of 2 multiplied by x gives me a whole number, then the best I'm going to get is an internal representation that's close.
integer는 apporximation이 아니라 exact number 입니다
👩💻 다항식의 해 구하는 법 (Newton- Raphson)
예시 )
하나의 해를 갖는 다항식의 해를 구하는 법
( g= 우리가 구하는 다항식 근의 근사값)
{ g - (g^2 - 다항식의 상수값) } / (미분한 식에 g 대입한 값)
# y = x^2 = 24 인 식의 해를 구하는 것
epsilon = 0.01
y = 24.0
guess = y/2.0
numGuesses = 0
while (guess**2 - y) >= epsilon:
numGuesses += 1
guess = guess - (guess**2 - y)/(2*guess) #just a formula
print('numGuesses: ',numGuesses)
print('Square root of '+str(y)+' is about '+str(guess))
🥳 배운점
오..? 이런 식으로 구할수가 있어?
👩💻 제곱수 구하기
Exercise: iter power
ESTIMATED TIME TO COMPLETE: 6 minutes
Write an iterative function iterPower(base, exp) that calculates the exponential by simply using successive multiplication. For example, iterPower(base, exp) should compute by multiplying base times itself exp times. Write such a function below.
This function should take in two values - base can be a float or an integer; exp will be an integer >= 0. It should return one numerical value. Your code must be iterative - use of the ** operator is not allowed
💡 풀이 #1 (내가 푼 거) Using Iteration
#Exercise: Power iter
def iterPower(base, exp):
n=1
result = base
if exp==0:
return 1
elif exp==n:
return base
else:
while n<exp:
result *= base
n+=1
return result
💡 풀이 #2 (교수님)
def iterPower(base, exp):
'''
base: int or float.
exp: int >= 0
returns: int or float, base^exp
'''
result = 1
while exp > 0:
result *=base
exp -= 1
return result
💡 풀이 #3 (내가 푼 거) Using Recursion
def recurPower(base,exp):
result = 1
if exp ==0:
return result
else:
return base * recurPower(base, exp-1)
print(recurPower(4,3))
✍️ 해설
훨씬 간편. 일단 처음에 base *= base 했다가 4제곱근... 이상이 나와서 놀랐음. base를 변경시키면 안되고, result라는 새로운 변수를 만들어서, 거기다가 base를 차근차근 곱해줘야 함!
그리고 exp를 하나씩 줄여가면서 곱해주면 됨
확실히 recursion이 간편하고 보기 좋다 !!
🥳 배운점
깔끔하고 간결하게 코드 짜는 법
모든 값에 대해 참이라는 것을 수학적으로 추론할 수 있다.
👩💻 Recursion (Towers of Hanoi)
#from , to , sparse 세개의 기둥이 있는 하노이 문제
#from 에서 to 로 옮길거다
def printMove(fr, to):
print ('Move From '+str(fr)+ ' to '+str(to))
def Towers(n, fr, to, spare):
if n==1:
printMove(fr, to)
else:
Towers(n-1, fr, spare, to)
Towers(1, fr, to, spare)
Towers(n-1, spare, to, fr)
print(Towers(4, 'P1', 'P2', 'P3'))
👩💻 Iteration (gcd)
Exercise: gcd iter
ESTIMATED TIME TO COMPLETE: 5 minutes
The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder. For example,
gcd(2, 12) = 2
gcd(6, 12) = 6
gcd(9, 12) = 3
gcd(17, 12) = 1
Write an iterative function, gcdIter(a, b), that implements this idea. One easy way to do this is to begin with a test value equal to the smaller of the two input arguments, and iteratively reduce this test value by 1 until you either reach a case where the test divides both a and b without remainder, or you reach 1.
💡 풀이 #1 (내가 푼 거)
def gcdIter(a,b):
c = min(a,b)
d = max(a,b)
div = c
if d%c == 0:
return c
else:
while not (d%div == 0 and c%div == 0):
div -=1
return div
💡 풀이 #2 (교수님)
#New solution
def gcdIter(a,b):
c = min(a,b)
while a%c !=0 or b%c !=0:
c -=1
return c✍️ 해설 ( 아! 너무 잘 풀었다)
1) a = b 면 둘 중 하나가 gcd니까 하나 리턴
2) a > b 면 a%b = 0 이면 gcd는 b
3) a > b 인데 a%b != 0 이면, a도 나누어 떨어지고, b도 나누어 떨어지게 하는 c를 구해야지
c는 8에서 부터 시작해서 두 숫자들 모두 나누어본다 20/8, 8/8 = 하나만 0으로 떨어진다 20/5, 8/5 = 하나만 0으로 떨어진다 .... 20/4, 8/4 = 둘 다 0으로 떨어진다
ex) 20, 8
하지만 훨씬 쉬운 풀이는, 굳이 min, max 나누지 않고 그냥 min만 구해다가,
두 숫자 다 나누어떨어지지 않는다면 계속 min-1 하면서 나눠주다가, 드디어 둘 다 나누어 떨어지면 !!! c를 리턴한다
🥳 배운점
하면 된다 >_<
그리고 변수를 여러개 만들기보다, 하나의 변수로 풀어낼 수 있는 방법이 항상 있다.
👩💻 Recursion (gcd)
The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder. For example,
gcd(2, 12) = 2
gcd(6, 12) = 6
gcd(9, 12) = 3
gcd(17, 12) = 1
A clever mathematical trick (due to Euclid) makes it easy to find greatest common divisors. Suppose that a and b are two positive integers:
If b = 0, then the answer is a
Otherwise, gcd(a, b) is the same as gcd(b, a % b)
💡 풀이
def gcdRecur(a,b):
#여기서 나누는 애를 b라고 두는거다
if b==0:
return a
else:
return gcdRecur(b, a%b)
✍️ 해설
예1)
(a,b) = 12, 2 라는 숫자가 있다고 하면,
(b, a%b) = (2, 0) 뒤에가 0이 되었으므로, 앞의 숫자 2가 정답이다.
예2)
(a,b) = 20, 12 라고 한다면,
20%12 != 0 이지. 그러면 b를 앞으로 땡기고, 뒤에는 20%12=8을 놓는다. (12, 8)
그래서 다시 12%8 != 0 이니까 다시 자리를 바꿔서, (8, 4)
8%4 = 0 이니까 최종적으로 답은 b !!! 결국, 뒤에 숫자가 0이 될때까지 반복하며, 누가 크든 상관 없다
예3)
(a, b) = (12, 20) 라고 해도, 12%20 나머지는 12 => 20, 12 이렇게 바꾸게 되니까, 결국 위와 과정이 똑같게 된다.
예4)
(a,b) = (4, 4)인 경우에도 그럼 무조건 recursion을 거쳐서, ( 4, 0 ) 으로 나와야 한다
🥳 배운점
이거 진짜... 생각을 하면서 풀어야되네