[알고리듬] #47 구글입사 문제

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

무한 연습

while문을 사용할 수 있는 문제들을 해결하여 봅시다.

 

 

 

1. 팩토리얼 계산

∙n!은 n팩토리얼(factorial)로 읽으며, n이하의 모든 양의 정수 곱을 의미합니다.
5! = 5*4*3*2*1 = 120입니다. 단, 0!=1로 약속합니다.

 

코드를 실습하고, 분석하세요.

example	description
n=10000 f=1 while n>0:     f * = n     n- = 1 print(f)	∙10000!의 값을 구하는 프로그램이다. 결과는 약 이다. ∙n을 감소하지 않으면 무한 루프(endless loop)가 된다. 탈출조건을 확인하는 습관을 갖자.

 

 

2. 피보나치 수열

∙피보나치 수열(fibonacci sequence)은 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 됩니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .....

example	description
n=10 a,b=0,1 while n>0:     print(a,end=' ')     a,b=b,a+b     n- =1	∙n-nacci (엔 나치)수열은 (n-1)개의 0과 1개의 1로 시작하여 n개의 합을 다음 수열의 값으로 한다. 0,  1로 시작하는 피보나치수열은 ∙2-nacci 수열이다. 0, 0, 1 로 시작하는 수열은 ∙3-nacci 수열이다. 왼쪽은 처음부터 10개의 피보나치 수열을 출력하는 프로그램이다. 'a,b=b,a+b'는 b는 a에, a+b는 b에 바인딩된다.

 

※ [참고] 피보나치 수

 

피보나치 수가 처음 언급된 문헌은기원전 5세기 인도의 수학자 '핑갈라'가 쓴 책이다.

유럽에서 피보나치 수를 처음 연구한 것은 레오나르도 피보나치로 토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다. n 번째 달의 토끼 수는

• 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
• 두 달 이상이 되면 토끼는 번식 가능하다.
• 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
• 토끼는 죽지 않는다.

따라서 첫 달에는 새로 태어난 토끼 한 쌍이 있고, 두 번째 달에는 그대로 토끼 한 쌍, 세 번째 달부터는 이 토끼 한 쌍이 새끼를 낳게 되어 토끼가 2쌍이 되고, 네 번째 달에는 3쌍, 다섯 번째 달에는 5쌍이 된다. 이때 n번째 달에 a 쌍의 토끼가 있었고, 다음 n+1번째 달에는 새로 태어난 토끼를 포함해 b쌍이 있었다고 하자. 그러면 그다음 n+2 번째 달에는 a+b 쌍의 토끼가 있게 된다. 이는 n번째 달에 살아있던 토끼는 충분한 나이가 되어 새끼를 낳을 수 있지만, 바로 전 달인 n+1번째 달에 막 태어난 토끼는 아직 새끼를 낳을 수 없기 때문이다.

 

3. google 입사문제

∙양의 정수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 하자.

예를 들면 f(11)=4, f(13)=6이다. 그렇다면 f(n)=n이 되는 첫 번째 수는 당연히 1이다.

두 번째 수는 무엇인가?

 

3-1 문제의 이해

1부터 11사이의 정수에는 몇개의 1이 있을까요?

1 2 3 4 5 6 7 8 9 10 11

모두 4개의 1이 있습니다.

1부터 11사이의 정수에 있는 1의 개수를 f(11)이라하면 f(11)=4입니다.

f(10)은 얼마입니까? 답은 2입니다.

f(1)은 1부터 1사이에 있는 1의 개수이고 답은 1입니다. 즉, f(1)=1입니다.

f(1)의 1과 답 1이 같습니다.

그렇다면 f(n)의 답이 n이 되는 수는 얼마일까요?

 

3-2 해결 방법

숫자 2부터 1씩 증가하면서 각 숫자에 있는 1의 개수를 조사하고, 조사한 개수를 계속 더하면(누적하면)  f(n)=n이 되는 숫자가 나오지 않을까요?

 

3-3 코딩하기

example	description
n=2 sum=1 while n!=sum:     n+=1     sum+=str(n).count('1') print(n)	n과 sum이 같지 않은 동안 반복합니다. n=2 , 그 때까지 1의 개수는 1개(sum=1) 를 초기값으로 두고 3부터 시작함 3에 있는 '1'의 개수를 sum에 누적, 다음은 4, 다음은 5, ... 결과는 199981

 

연봉 1억이 넘는 대기업의 입사 문제입니다.

할만하지요?

 

오늘도 수고하셨습니다.

안녕!