Part of your World

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

입출력 예

numbers result

입출력 예 설명

입출력 예 #1

2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2

9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

스택을 이용해 풀 수 있다. 문제의 요구사항에 따라 자신보다 큰 가장 가까운 숫자를 찾기 위해, 우선 모든 숫자의 뒷 큰수를 -1로 설정해두고, 오른쪽부터 왼쪽으로 스택에 숫자를 넣어가며, 스택의 최상위 숫자보다 큰 숫자가 나올 경우 해당 숫자를 스택에서 빼고 그 자리에 뒷 큰수를 저장한다.

package LV2;

import java.util.Stack;

public class H154539 {
    public int[] solution(int[] numbers) {
        // numbers의 길이를 length에 저장한다.
        int length = numbers.length;

        // 결과를 담을 배열 answer를 초기화하고, 모든 원소를 -1로 설정한다.
        int[] answer = new int[length];

        // 숫자를 저장할 스택을 생성한다.
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < length; i++) {
            answer[i] = -1;
        }

        // 오른쪽에서 왼쪽으로 이동하면서 각 숫자에 대한 뒷 큰수를 찾는다.
        for(int i = length - 1; i >= 0; i--) {
            // 현재 숫자가 스택의 최상위 숫자보다 크면, 스택에서 숫자를 빼고 뒷 큰수를 현재 숫자로 설정한다.
            while(!stack.isEmpty() && stack.peek() <= numbers[i]) {
                stack.pop();
            }

            // 스택이 비어있지 않고, 스택의 최상위 숫자가 현재 숫자보다 크다면, 뒷 큰수를 스택의 최상위 숫자로 설정한다.
            if(!stack.isEmpty() && stack.peek() > numbers[i]) {
                answer[i] = stack.peek();
            }

            // 현재 숫자를 스택에 넣는다.
            stack.push(numbers[i]);
        }

        // 모든 숫자의 뒷 큰수를 담은 배열을 반환한다.
        return answer;
    }
}

answer 배열을 입력받은 numbers의 길이로 초기화하고, 모든 원소를 -1로 설정한다. 그 후, 스택을 생성한다.

그 다음, 오른쪽부터 왼쪽으로 숫자를 보면서, 현재 숫자가 스택의 최상위 숫자보다 클 경우, 스택에서 숫자를 빼고 해당 숫자의 뒷 큰수를 현재 숫자로 설정한다. 이 과정을 반복하여 모든 숫자에 대한 뒷 큰수를 찾는다. 마지막으로, 현재 숫자를 스택에 넣는다.

모든 숫자에 대해 이 과정을 반복하면, 최종적으로 모든 숫자의 뒷 큰수를 찾을 수 있다.

문제 설명

정수가 담긴 리스트 num_list가 주어질 때, 모든 원소들의 곱이 모든 원소들의 합의 제곱보다 작으면 1을 크면 0을 return하도록 solution 함수를 완성해주세요.

제한사항

• 2 ≤ num_list의 길이 ≤ 10
• 1 ≤ num_list의 원소 ≤ 9

입출력 예

num_list result

입출력 예 설명

입출력 예 #1

• 모든 원소의 곱은 120, 합의 제곱은 225이므로 1을 return합니다.

입출력 예 #2

• 모든 원소의 곱은 840, 합의 제곱은 529이므로 0을 return합니다.

package Lv0;
/*
정수가 담긴 리스트 num_list가 주어질 때, 
모든 원소들의 곱이 모든 원소들의 합의 제곱보다 작으면 1을 크면 0을 return하도록 solution 함수를 완성해주세요.
 */
public class H181929 {
	public int solution(int[] num_list) {
		int answer = 0;
		int product = 1;

		for (int num : num_list) {
			answer += num;
			product *= num;
		}
		int square = answer * answer;
		if (product < square) {
			return 1;
		} else {
			return 0;
		}
	}
}

동적 계획법 (Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제들로 나누어 풀고, 그 결과를 저장해 재사용하여 주어진 문제를 최적화하는 방법이다.

이는 '분할 정복' 알고리즘의 기본적인 원리를 따르지만, 동적 계획법은 각 하위 문제들이 중첩되어 있는 경우에 특히 효과적이다. 그래서, 동적 계획법은 공통의 하위 문제들을 여러 번 다시 풀지 않도록 이를 메모이제이션 (memoization)하여, 알고리즘의 계산 효율성을 대폭 향상시킨다.

동적 계획법은 일반적으로 두 가지 기본 단계를 거친다.

1. 하향식 접근법(Top-down): 문제를 하위 문제로 나눈다. 만약 하위 문제가 이미 해결되었다면, 저장된 결과를 사용한다. 아니라면, 문제를 해결하고 결과를 저장한다.
2. 상향식 접근법(Bottom-up): 가장 작은 하위 문제부터 시작하여, 작은 하위 문제들의 해결을 바탕으로 큰 문제의 해결책을 구성해 나간다.

동적 계획법은 최단 경로 문제, 0-1 배낭 문제, 피보나치 수열 등 다양한 문제에 적용될 수 있다. 그러나 동적 계획법이 모든 최적화 문제에 효과적인 것은 아니다. '최적 부분 구조(Optimal Substructure)'와 '중복된 하위 문제(Overlapping Subproblems)' 조건을 만족하는 문제에 대해서만 동적 계획법을 적용할 수 있다.

public class Main {
    public static long fib(int n) {
        long[] dp = new long[n+1];
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 10 번째 피보나치 수를 출력
    }
}

dp라는 이름의 long형 배열은 메모이제이션을 위한 저장 공간으로 사용된다. 각 n에 대한 피보나치 결과가 이 배열에 저장된다. 이미 계산된 결과를 재사용할 수 있게 되어 중복 계산을 피하고 효율성을 높일 수 있다.