알루 코딩

다이나믹 프로그래밍(동적 계획법) 이란 ? : 컴퓨터 연산을 하면서 중복되는 연산을 줄이자는 목적으로 나온 기법이다. 보통, 다이나믹이라고 하면 '프로그램이 실행되는 도중에' 라는 의미로 쓰이는데(ex.동적할당), 여기서는 그런 의미는 아니다. 연산을 줄이자는 것이 목적이라면, 재귀함수로 프로그램을 짤 수도 있는 것 아니냐고 생각할 수 있다. 물론, 할 수는 있다. 하지만, 수가 크다면, 실행시간은 기하급수적으로 늘어나기 때문에, 계속해서 재귀함수를 호출하는 것은 컴퓨터에 많은 부하를 줄 수 있다. 예를 들어, 피보나치 수열을 재귀함수로 구현한다면, n이 100 이기만 해도, 연산 횟수가 약 1,000,000,000,000,000,000,000000,000,000번이다. 즉, 1초에 1억번 정도의 연산을..

시간제한이 2초여서 팩토리얼 함수를 재귀로 구현해도 무방한 문제 같았다. 주어진 n 에 따라 팩토리얼 함수로 n! 구하고 그 n! 을 string 화시켜서 뒤에서부터 0의 개수를 세면 되는 문제였다. (코드는 아래와 같다.-python) def factorial(n): # 팩토리얼을 구하는 재귀함수 if n == 0: return 1 elif n == 1: return 1 else: return factorial(n-1)*n def findzero(n): # 숫자 맨 뒤에 0이 몇개 있는지 출력하는 함수 cnt = 0 string_number = str(n) reverse_number = string_number[::-1] for s in reverse_number: if s != '0': break e..