알고리즘 공부 8일차

1. 피보나치 수 (프로그래머스)

문제 설명

피보나치 수는 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을 완성해 주세요.

제한 사항

* n은 1이상, 100000이하인 자연수입니다.

입출력 예

nreturn

3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

---

해결 방법 : 피보나치 코드 개발

이유 : 효율적인 피보나치 코드 개발

참고 자료 : eda-ai-lab.tistory.com/488

문제 : programmers.co.kr/learn/courses/30/lessons/12945

 

def solution(n):
    Table = [0 for c in range(n+1)]
    Table[1] = 1
    for i in range(2, n+1):
        Table[i] = (Table[i-1] + Table[i-2]) % 1234567

    return Table[i]

 

---

2. 124나라의 숫자(프로그래머스)

문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법124 나라10진법124 나라

1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• n은 500,000,000이하의 자연수 입니다.

---

입출력 예

n                                                                            result

1	1
2	2
3	4
4	11

 

---

해결 방법 : 진법변환

이유 : 진법 변환쪽 공부를 더 해야겠음. divmod의 유무도 알아야했고 진법 변환은 이런 식으로 한다는걸 기억

참고 자료 : leedakyeong.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-124-%EB%82%98%EB%9D%BC%EC%9D%98-%EC%88%AB%EC%9E%90-in-python

문제 : programmers.co.kr/learn/courses/30/lessons/12899

 

def solution(n):
    if n<=3:
        return '124'[n-1]
    else:
        q, r = divmod(n-1, 3)
        return solution(q) + '124'[r]