문제:

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1<=N<=90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

첫째 줄에 N자리 이친수의 개수를 출력한다.

풀이 방법:

직접 1번과 2번 규칙을 만족하는 수를 찾기 위해서 N자리의 이친수를 생성하는 일을 하면 시간초과, 메모리초과가 발생하게 된다. 즉 매우 큰 수이며 많은 작업이 필요하다. 따라서 규칙이 있음을 알게 되었다.

N=1일 때에는 [ 1 ] 하나이다. N=2일 때, [10] 하나이다. N=3일 때, [100, 101] 두 개이다. N=4일 때, [1000, 1001, 1010] 세 개다. .....

이렇게 계속 반복해 나가다 보면 피보나치 함수를 이루는 것을 알 수 있다. 즉 초기 두 항이 1, 1인 피보나치 함수이다.

1
2
3
4
5
6
7
n=int(input())
a,b=1,1
count=1
while(count<n):
    a,b=b,a+b
    count+=1
print(a)
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1037. 약수  (0) 2019.05.02
[BOJ]2156. 포도주 시식  (0) 2019.05.01
[BOJ]1003. 피보나치 함수  (0) 2019.04.26
[BOJ]9461.파도반 수열  (0) 2019.04.25
[BOJ]9095. 1,2,3 더하기  (0) 2019.04.24

문제:

피보나치 수는 F(0)=0, F(1)=1일 때, 1 이상의 n에 대하여 F(n)=F(n-1)+F(n-2) 가 적용되는 수 입니다.


예를 들어


F(2)= F(0)+F(1)=0+1=1

F(3)= F(1)+F(2)=1+1=2

F(4)= F(2)+F(3)=1+2=3

F(5)= F(3)+F(4)=2+3=5


와 같이 이어집니다.


2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.


풀이 방법:

일반적으로 피보나치 수열을 푸는 방법으로 재귀를 많이 사용한다. 하지만 재귀 문제의 경우에는 일부 유형에는 좋은 효율을 보여주지만 적어도 피보나치 수열에서는 숫자가 커질수록 시간이 많이 걸린다. 따라서 이번에는 파이썬의 특성을 이용해서 빠르게 구할 수 있는 방법을 소개 하려고 한다.
파이썬에서는 a,b=b,a와 같이 값이 변경하는 것이 가능하다. 따라서 이를 이용해서 피보나치 수열을 풀 수 있다.

1
2
3
4
5
6
def solution(n):
    a,b = 0,1
    for i in range(n):
        a,b=b,a+b
    answer=a%1234567
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.행렬의 곱셈  (0) 2019.03.20
[Programmers]Lv 3.최고의 집합  (0) 2019.03.19
[Programmers]Lv 3.줄 서는 방법  (0) 2019.03.17
[Programmers]Lv 2. 최솟값 만들기  (0) 2019.03.16
[Programmers]Lv 3. 야근 지수  (2) 2019.03.15

문제:

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸,1칸,1칸,1칸)
(1칸,2칸,1칸)
(1칸,1칸,2칸)
(2칸,1칸,1칸)
(2칸,2칸)

의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리 뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면,5를 return하면 됩니다.

풀이 방법:

임의의 수 n이 주어졌다고 하자. 한번에 움직일 수 있는 칸은 1칸 혹은 2칸이기 때문에 n으로 이동하기 위해서는 n-2칸에서 2칸을 사용해서 n번째 칸으로 오거나 n-1에서 1칸을 이동해서 n칸으로 이동하는 방법이 있다. 재귀를 사용해서 풀어도 괜찮으나 피보나치 수열을 이루기 때문에 피보나치 수열을 이용해서 풀었다.

1
2
3
4
5
def solution(n):
    a,b =1,2
    for i in range(n-1):
        a,b=b,a+b
    return a%1234567
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 방문길이  (0) 2019.03.13
[Programmers]Lv 2.숫자의 표현  (0) 2019.03.12
[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
[Programmers]Lv 3.베스트앨범  (0) 2019.03.09
[Programmers]Lv 2.땅따먹기  (0) 2019.03.08

문제:

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.


 

 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다..


[1,1,2,3,5,8,...]


 지수는 문들 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.


타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.


풀이 방법:

다음 직사각형의 한 변의 길이는 이전의 두 개의 직사각형 한 변의 길이 합으로 만들어진다. 이 말은 직사각형의 길이가 피보나치 수열을 따른 다는 것이다. 따라서 피보나치 수열을 이용해서 직사각형의 변의 길이를 구한 뒤에 둘레를 구해주면 된다.

1
2
3
4
5
6
7
def solution(N):
    a,b=1,1
    while(N>1):
        a,b=b,a+b
        N-=1
    answer=a*2+b*2
    return answer
cs



저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24
[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22
[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21
[Programmers]Lv 2. 위장  (0) 2019.02.20

문제:

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

타일을 가로로 배치 하는 경우
타일을 세로로 배치 하는 경우

직사각형 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

보통 이러한 문제는 패턴이 있기 때문에 패턴을 찾으려고 했다.
n이 1일때 1가지 방법,     2일 때 2가지 방법,     3일 때 3가지 방법,     4일 때 5가지 방법,     5일 때 8가지 방법...

1,2,3,5,8,13,.....

n이 증가함에 따라 방법의 갯수는 피보나치 수열을 따르면서 증가하고 있었다. 즉 피보나치를 활용해서 풀면 된다. 다음과 같이 간단하게 구할 수 있다.

1
2
3
4
5
def solution(n):
    a,b=1,1
    for i in range(n):
        a,b=b,a+b
    return a%1000000007
cs
 


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3.타일 장식물  (0) 2019.02.23
[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22
[Programmers]Lv 2. 위장  (0) 2019.02.20
[Programmers]Lv 1.N으로 표현  (0) 2019.02.19
[Programmers]Lv 2. H-Index  (0) 2019.02.18

+ Recent posts

티스토리툴바