[프로그래머스]피보나치 수

java
posted by 코딩 공부중 2022. 3. 18. 16:46
  • 피보나치 수
문제 설명

피보나치 수는 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은 2 이상 100,000 이하인 자연수입니다.
입출력 예nreturn
3 2
5 5
입출력 예 설명

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
   
    int fibo(int n,int[] memo){
        memo[0] = 0; 
        memo[1] = 1;
        
         for(int i=2; i<=n; i++){
            memo[i] = (memo[i-1] + memo[i-2]) % 1234567;
        }
        
        return memo[n];
        
    }
    
    public int solution(int n) {
        int[] memo = new int[n+1];
        int answer = 0;
        answer = fibo(n,memo);
        return answer;
    }
}
 cs

재귀가 아닌 dp로 해결함

 

'java' 카테고리의 다른 글

[프로그래머스] 이진 변환 반복하기  (0) 2022.03.28
[프로그래머스]로또의 최고 순위와 최저 순위  (0) 2022.03.28
[프로그래머스] 행렬의 곱셈  (0) 2022.03.17
[프로그래머스] 숫자의 표현  (0) 2022.03.11
[프로그래머스] 점프와 순간 이동  (0) 2022.02.23

[프로그래머스] 행렬의 곱셈

java
posted by 코딩 공부중 2022. 3. 17. 16:59

문제 설명

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.

제한 조건
  • 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
  • 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
  • 곱할 수 있는 배열만 주어집니다.
입출력 예arr1arr2return
[[1, 4], [3, 2], [4, 1]] [[3, 3], [3, 3]] [[15, 15], [15, 15], [15, 15]]
[[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20,

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
   
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int[][] answer = new int[arr1.length][arr2[0].length];
        int r = 0;
        for (int k = 0; k < arr1[0].length; k++) {
            for (int i = 0; i < arr1.length; i++) {
                r = arr1[i][k];
                for (int j = 0; j < arr2[0].length; j++) {
                    answer[i][j] += r * arr2[k][j];
                }
            }
        }
        return answer;
    }
}
 cs

 

효율성체크가 없어서 일반적인 행렬의 곱셈 식으로 for문을 세개 써서 풀었다.

스트라센 알고리즘 (Strassen Alogrithm)이라는 분할정복 방법으로 풀면 훨씬 효율적으로 가능하다고 한다,

이 알고리즘을 학습해서 다른 방식으로 풀어봐야할듯

'java' 카테고리의 다른 글

[프로그래머스]로또의 최고 순위와 최저 순위  (0) 2022.03.28
[프로그래머스]피보나치 수  (0) 2022.03.18
[프로그래머스] 숫자의 표현  (0) 2022.03.11
[프로그래머스] 점프와 순간 이동  (0) 2022.02.23
[프로그래머스] 올바른 괄호  (0) 2022.02.22

[프로그래머스] 숫자의 표현

java
posted by 코딩 공부중 2022. 3. 11. 12:08

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

  • 1 + 2 + 3 + 4 + 5 = 15
  • 4 + 5 + 6 = 15
  • 7 + 8 = 15
  • 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항
  • n은 10,000 이하의 자연수 입니다.
입출력 예nresult
15 4
입출력 예 설명

입출력 예#1
문제의 예시와 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int solution(int n) {
        int answer = 1;
        int count,sum = 0;
        
        for(int i=1; i<n; i++){
           // sum = i+(i+1);
            sum = i+i+1;
            count = i+2;
            while(true){
                if(sum==n){
                    answer++;
                    break;
                }
                if(sum>n){
                    break;
                }
                sum = sum+count;
                count+=1;
            }
            
        }
        return answer;
    }
}
 cs

규칙을 찾아서 푸는 문제

1부터 연속된 수를 합쳤을 때 나오는 값을 생각해보니 규칙을 알 수 있었다.

ex)

1,3,6,10,15...

2,5,9,14,20...

3,7,12,18,25...

 

'java' 카테고리의 다른 글

[프로그래머스]피보나치 수  (0) 2022.03.18
[프로그래머스] 행렬의 곱셈  (0) 2022.03.17
[프로그래머스] 점프와 순간 이동  (0) 2022.02.23
[프로그래머스] 올바른 괄호  (0) 2022.02.22
[프로그래머스] 땅따먹기  (0) 2022.02.16

티스토리툴바