###2019.03.13 TIL
======================== 1.알고리즘 문제 ————- 문제 : 1부터 10000000을 모두 더한 값을 구하여라.
조건.
- 단 for문 혹은 while문은 안된다.
- 함수로 만들어라
- signiture(def sumto(start,end) —> interger).
# 함수를 정의할 때는 항상 이름(변수) —> 리턴값이 제시되야 한다.
나의 풀이 방법
의식의 흐름.
일단 문제를 보자마자 나도 모르게 가우스의 덧셈이 떠올랐다.
따라서 가장 처음 푼 방법은 가우스의 덧셈을 활용하여 풀었다.
가우스의 덧셈 참조 : 네이버 블로그
def sumto(start, end):
result = (start+end) * ((end - start +1)/2)
print(result)
return result
sumto(1, 100)
5050.0
굉장히 간단하게 해결하였다. 하지만 여기서 원하는 것은 알고리즘 문제를 해결하는 것이기에 조금 더 생각해 보기로 하였다.
###다음 생각한 해결 책은 reduce함수를 쓰는 것이었다.
#급하게 reduce가 함수인지 특정 객체의 메소드인지가 궁금해졌다.
오늘 알게 된 사실인데 함수와 메소드는 서로 비슷하게 많이 사용하지만 엄연히
다르다. 메소드는 객체가 가지고 있는 동작이다. 함수와 메소드는 기본적으로 일련의 동작을 실행한다는 점에서 동일하나, 메소드는 특정 객체가 가지고 있는 동작을 가지고 있고, 메소드를 실행하기 위해서는 객체를 통해야만 실행가능하다. 그에 비해 함수는 함수 자체가 그 동작을 정의한 객체이다.
###reduce를 통한 해결책 의식의 흐름.
기본적으로 reduce함수의 사용법에 대해 알고 있어야 한다.
reduce를 한번 python에서 help를 활용하여 사용법에 대해 알아보면,
>>> from functools import reduce
>>> help(reduce)
>>> Help on built-in function reduce in module _functools:
reduce(...)
reduce(function, sequence[, initial]) -> value
reduce는 내장함수가 아니라 functools의 module라는 것이 나와 있고
함수를 정의하는 이름(매개변수) —>value가 추가적으로 잘 설명되어 있다.
조금 더 자세히 보면 function에는 람다함수가 들어갈 것이고(#람다함수를 한마디로 말하면 일시적인 함수이다.)
sequence에는 iterable이 들어갈 것이고, 초기값은 필요에 의해 첨부 할 수 있다.
lambda함수에 대해서는 정리해놓은 것을 곧 업로드 할 예정이다.
이를 바탕으로 reduce를 적용하여 해당문제를 풀어보았다.
>>>from functools import reduce
>>>def sumto(start, end):
result = reduce(lambda x,y : x+y, range(start, end+1))
return result
>>>sumto(1,100)
>>>5050
reduce는 lambda함수 내에서 2개의 매개변수를 받아서 하나의 값으로 만들 때 쓰는 것이고,
하다 하나 더해가는 것이라 위의 풀이법에 비해서는 비효율적이라 생각되었다.
이후에 선생님이 추가적으로 하나의 문제를 더 내주었는데 이번 문제는 좀 더 어려웠다.
step을 추가하여 일정한 step마다 띄어가며 더하라는 것이었다.
def sumto(start, end, step): 이라는 시그니처를 주셨고
만약 sumto(1, 10, 2) —> 1 + 3 + 5 + 7 + 9 = 25가 반환되어야 한다.
가오스의 덧셈을 활용하여서는 쉽게 길이 보이지 않았지만 reduce를 통해서는 길이 보였다.
결국 step이라는 것은 1과 다음 숫자 사이의 차이이고 이것과 산술연산자 %(나머지 반환)를
활용하여 구해보았다.
>>>from functools import reduce
>>>def sumto(start, end, step):
>>> result = reduce(lambda x,y : x+y if (y-start)%step == 0 else x, range(start, end + 1)
>>> return result
>>>
>>>sumto(1, 10, 2)
>>>25
>>>sumto(1, 10, 3)
>>>22
위와 같이 아주 잘 나왔다. 생각보다 고민하는 시간이 좀 길었는데 문제를 해결할 수 있었다!!.
하지만 역시 선생님의 풀이는 짧고 간단했다. 주룩 ㅠㅠ
###선생님 풀이 재귀함수를 통한 접근
>>> def sumto(start, end):
>>> if start == end:
>>> return s #기저함수 설정
>>> return sumto(start, end-1) + end
>>>
>>> sumto(1, 10)
>>> 55
>>>
>>> sumto(1, 10000000)
>>> RecursionError: maximum recursion depth exceeded in comparison
ㅎㅎㅎ 몸소 간단하게 해결해주시고 Error가 나는 것도 보여주셨다.
출제자의 의도는 재귀함수로 구현을 할 수 있는지 보고, 이것이 터질 것을 예상하고
위에 내가 풀었던 수학을 이용할 풀이를 구현하기까지 바랬다고 한다.
추가적으로 등차수열 더하는 공식 n(a+1)/2를 통해 n을 잘 만지면 step을 넣는 것까지
구현해 볼 수 있다고 하셨다.
# 이것은 다음에 복습할 때 꼭 해봐야 되겠다.
그리고 이 등차수열을 설명해주시면서 버블 정렬의 T(n)을 구하는 방법도 추가적으로 설명해주셨는데
n이 4개일때 제일 앞에 꺼는 if문을 3번 돌아야 하고 다음 것은 2번 그 다음 것은 1번 이런식으로
계산해 나가야 하므로 1+2+3+….+n-1이고 이것을 등차수열 더하는 공식으로 해보면
n(a+l)/2 —-> (n-1)(1+n-1)/2 = (n* 2 + 3n)/ 2 —> T(n** 2)으로 나왔다.