알고리즘(최댓값과 최솟값, 최솟값 만들기, 피보나치 수, 행렬의 곱셈) - Java

[최댓값과 최솟값]

* 로직

• 공백을 기준으로 split을 진행하고
• 최댓값과 최솟값을 갱신해주면 된다

 

// 최댓값과 최솟값
import java.util.StringTokenizer;

public class Problem_MAX_MIN {

    public static void main(String[] args) {
        String s = "1 -2 -3 4";
        String answer = solution(s);
        System.out.println(answer);
    }

    public static String solution(String s) {
        String answer = "";
        StringTokenizer st;

        st = new StringTokenizer(s, " ");
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        while (st.hasMoreTokens()) {
            int value = Integer.parseInt(st.nextToken());
            min = Math.min(min, value);
            max = Math.max(max, value);
        }

        answer += min + " ";
        answer += max;

        return answer;
    }
}

 

 

---

[최솟값 만들기]

* 로직

• A와 B를 정렬한 뒤, A는 작은 수부터 B는 큰 수부터 차례대로 곱해주면 가장 최솟값이 나오게 된다

 

// 최솟값 만들기
import java.util.Arrays;

public class Problem_MakeMinValue {

    public static void main(String[] args) {
        int[] A = {1, 4, 2};
        int[] B = {5, 4, 4};
        int answer = solution(A, B);
        System.out.println(answer);
    }

    public static int solution(int []A, int []B) {
        int answer = Integer.MAX_VALUE;

        // sort
        Arrays.sort(A);
        Arrays.sort(B);

        // A는 작은 값부터, B는 큰 값부터
        int acc = 0;
        for(int i=0; i<A.length; ++i) {
            int a = A[i];
            int b = B[B.length-i-1];

            acc += (a*b);
        }

        answer = Math.min(answer, acc);       
        return answer;
    }
}

 

 

---

[피보나치 수]

* 로직

• 반복문과 재귀의 방법이 있지만, 이번 문제는 재귀 + 메모이제이션을 사용했다

 

// 피보나치 수
import java.util.Arrays;

public class Problem_Fibonacci {
    static int[] dp;
    static int mod = 1234567;

    public static void main(String[] args) {
        int n=3;
        int answer = solution(n);
        System.out.println(answer);
    }

    public static int solution(int n) {
        int answer = 0;

        dp = new int[n+1];
        Arrays.fill(dp, -1);
        doFibo(n);

        return answer = dp[n];
    }

    private static int doFibo(int n) {
        if(n <= 1) return dp[n] = n;
        if(dp[n] >= 0) {
            return dp[n];
        }

        return dp[n] = (doFibo(n-2) + doFibo(n-1)) % mod;
    }
}

 

 

---

[행렬의 곱셈]

* 로직

• (r * c) 행렬과 (a * b) 행렬의 곱이 이루어지면, 정답의 배열 사이즈는 r * b가 되기 때문에 미리 설정한다
• A 행렬의 첫행을 꺼내고 B행렬의 가로의 길이(b)만큼 포문을 돌며 answer[i][k]를 채운다
• A 행렬의 마지막행까지 이를 반복한다

 

// 행렬의 곱셈
public class Problem_MatrixMultiply {

    public static void main(String[] args) {
        int[][] arr1 = {
                {1, 4}, {3, 2}, {4, 1}
        };

        int[][] arr2 = {
                {3,3}, {3,3}
        };

        int[][] answer = solution(arr1, arr2);
        for(int[] ans : answer) {
            for(int value : ans) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }

    public static int[][] solution(int[][] arr1, int[][] arr2) {
        int[][] answer = {};
        int r = arr1.length;
        int c = arr2[0].length;

        answer = new int[r][c];
        for(int i=0; i<arr1.length; ++i) {
            for(int k=0; k<arr2[0].length; ++k) {
                int acc = 0;
                for(int j=0; j<arr1[i].length; ++j) {
                    acc += arr1[i][j] * arr2[j][k];
                }
                answer[i][k] = acc;
            }
        }

        return answer;
    }
}