4. 분해와 추상 함수(Decomposition and abstraction through functions)

강의링크: https://youtu.be/SXR9CDof7qw?si=iD7TskyctqpU8CL3

 

 

- 지금까지 배운 것(python)

assignment, conditionals, I/O, looping constructs(for, while), data => turing complete

 

이러한 것만으로는 코드를 쓸 때 우리가 옳은 곳에 있는지 확인하기 위해 어떤 것이 어디에 있는지, 어디서 가는지 모두 알아내기는 어려움

 

그래서 여기에 추가할 수 있는 것(오늘 배울 것)

1) decomposition(분해): 코드에 구조를 두는 방법(코드를 모듈로 나누는 방법. 코드는 프로세스의 성분들을 분리함)

2) abstractions(추상화): 자세한 내용을 숨기게 함

 

 

- Functions

함수가 위의 2가지를 모두 제공함

함수가 하려는 것:

1) 모듈로 나누기(break up into modules)

2) 자세한 것을 숨기도록 함(suppress detail)

3) create "new primitives"(새로운 초기 명령을 만드는 것) = "일반화"(computation의 일반적인 패턴, ex)제곱근 계산하기 등)

 

def - keyword

name(x) -> 여기서 x는 formal parameters를 정의함

                x는 place holder로서 기능(사용자가 x값을 주면 이 함수 내부에서 x가 나올 때마다 그 값을 사용함)

return - keyword

           computation에서 이 return을 가지면 computation을 멈춤. 즉, 함수로부터 control을 돌려줌. 그리고 다음 명령들의 값을 가지고 와서 전체 computation의 값으로 리턴함 -> ? 이해 안 됨(더 찾아보기)

None - special value

      이 computation에서 돌아올 값이 없음을 의미하는 것. none이 return되면 인터프리터에서 어떤 값도 출력되지 않음

 

 

- 이것들을 어떻게 적용하는가?

Invoke function by passing invalues for the parameters(파라미터 값을 넘겨서 함수를 적용함)

ex) sqrt(16) 을 입력하면

x를 16에 바인딩하게 됨. 이 바인딩은 local(프로시저 코드의 국한된 곳에서 이 바인딩을 가짐)

 

- Local bindings do not affect global bindings

ex)

def f(x):
	x = x+1
    return x

인터프리터에 x = 3

z = f(3)을 입력한 후 x와 z를 프린트하면 각각 3 과 4가 나옴

 

인터프리터에서 함수를 호출하면 local table이 만들어진다고 보면 됨

이 local table의 변수는 다른 바인딩에 영향을 미치지 않음

- interpreter x --> 3(binding)

sqrt x --> 16 ans --> 0                --> 이 함수가 return되면 이 local table이 없어짐

 

def sqrt(x):
  """Returns the square root of x, if x is a perfect square.
  	   Prints an error message and returns None otherwise"""
	ans = 0
    if x >= 0:
    	while ans*ans < x: ans += 1
        if ans*ans != x:
        	print(x, 'is not a perfect square')
            return None
        else: return ans
    else:
    	print(x, 'is a negative number')
        return None

<인터프리터에서>

>>> test = sqrt(16)
>>> test
4
>>> test = sqrt(34)
34 is not a perfect square
>>> test
>>> test == None
True

sqrt만 호출하면 그 리턴 값이 행해지지만, 이 함수를 test에 바인딩하면 test 값을 볼 수 있다.(이 부분 이해가 되는 듯하면서도 잘 안 됨..)

 

abstractions(추상화)는 함수의 구체적인 사항을 숨겨준다.(ex-제곱근, 제곱근이 무엇인지는 누구나 알고 있으므로 굳이 구체적인 내용을 다 보여줄 필요가 없음)

하지만 코드가 무엇을 하고 있는지 알 수 있도록 프로그램을 짤 때 comment를 쓰는 것이 필요하다.

 

 

- 코드를 쓸 때 분해, 추상화를 어떻게 쓸 것인가?

 

<Farmyard problem>

농장에 닭과 돼지들이 있다. 닭, 돼지의 마리 수는 모르지만 전체의 머리는 20개, 다리는 56개이다.

닭과 돼지는 각각 몇 마리인가?

 

우리는 이 문제를 선형 방정식으로 풀 수 있다.

numP + numC =20

(4*numP) + (2*numC) = 56

 

컴퓨터에서는 가능한 모든 예를 나열해서 검사하는 방법이 있다.(enumerate & check)

ex) 닭 0마리, 돼지 20마리인 경우/닭 1마리, 돼지 19마리인 경우/ 닭 2마리, 돼지 18마리인 경우... 를 나열해서 가능한 케이스를 검사하는 것 

이러한 방법을 brute force algorithm이라고 하기도 함

 

def solve(numLegs, numHeads):
	for numChicks in range(0, numHeads + 1):
		numPigs = numHeads - numChicks
		totLegs = 4*numPigs + 2*numChicks
		if totLegs == numLegs:
			return (numPigs, numChicks)
	return (None, None)

def barnYard():
	heads = int(input('Enter number of heads: '))
	legs = int(input('Enter number of legs: '))
	pigs, chickens = solve(legs, heads)
	if pigs == None:
		print('There is no solution')
	else:
		print('Number of pigs:', pigs)
		print('Number of chickens:', chickens)

 

 

- 반복(Recursion)

프로그램을 적절한 사이즈의 덩어리들로 나누는 방법이다.

어떤 문제를 같은 프로그램의 simpler version + 실행할 수 있는 단계로 쪼개는 것

 

• base case - 가장 간단한, 가능한 solution
• inductive step - break problem into (simpler version or recursive step of same problem) + (some other steps)

ex) 미국인 국적을 예로 들면, 미국인 국적을 갖는 케이스는

1) 미국에서 태어난 경우 - base case

2) 그렇지 않은 경우 - 부모가 미국인인 경우

                            부모 중 한명이 미국인인 경우

 

recursion을 잘 보여주는 예시: 회문(Palindrome) 검사하기

*회문이란 madam이나 nurses run처럼 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어나 구를 말함

 

ex) input으로 준 string이 회문인지 확인하고 싶음(해결하고자 하는 problem)

string의 요소가 없거나(0) 1이면 회문임 -> base case

string이 1보다 긴 길이를 가진다면, 양끝의 점이 같은 문자인지 확인하고 이를 반복해서 확인하면 됨

 

def isPalindrome(s):
	"""Returns True if s is a palindrome and False otherwise"""
	if len(s) <= 1: return True
	else: return s[0] == s[-1] and isPalindrome(s[1:-1])

 

- 피보나치

토끼의 수 구하기

def fib(x):
	"""Return fibonacci of x, where x is a non-negative int"""
	if x == 0 or x == 1: return 1
	else: return fib(x-1) + fib(x-2)