8월1일 - 알고리즘?

주어진 숫자들로 원하는 합 만들기 & 아라비아 숫자를 로마 숫자로 변환하기

오늘은 두 가지 문제를 해결하는 프로그램을 작성해보자. 첫 번째는 주어진 숫자들 중 일부를 더해서 원하는 합을 만들 수 있는지 확인하는 프로그램이고, 두 번째는 아라비아 숫자를 로마 숫자로 변환하는 프로그램이다.

1. 주어진 숫자들로 원하는 합 만들기

이 문제는 부분 집합 합(Subset Sum) 문제로도 알려져 있다. 주어진 숫자들 중 일부를 더해서 원하는 합을 만들 수 있는지를 확인하는 프로그램을 작성한다. 이는 백트래킹(Backtracking)이나 동적 프로그래밍(Dynamic Programming)으로 해결할 수 있다.

코드 구현 (자바)

import java.util.Arrays;

public class SubsetSum {

    public static boolean isSubsetSum(int[] nums, int target) {
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                if (nums[i - 1] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][target];
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int target = 9;
        System.out.println("Is subset with sum " + target + " present: " + isSubsetSum(nums, target));
    }
}

예제 실행 결과

Is subset with sum 9 present: true

설명

이 프로그램은 동적 프로그래밍을 사용하여 주어진 숫자들로 원하는 합을 만들 수 있는지 확인한다. dp[i][j]는 i개의 숫자들로 j라는 합을 만들 수 있는지를 나타낸다.

2. 아라비아 숫자를 로마 숫자로 변환하기

아라비아 숫자를 로마 숫자로 변환하는 문제를 해결해보자. 로마 숫자는 다음과 같이 표현된다:

1 = I
4 = IV
5 = V
9 = IX
10 = X
40 = XL
50 = L
90 = XC
100 = C
400 = CD
500 = D
900 = CM
1000 = M

코드 구현

public class ArabicToRoman {

    public static String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder roman = new StringBuilder();

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                roman.append(symbols[i]);
            }
        }

        return roman.toString();
    }

    public static void main(String[] args) {
        int number = 3549;
        System.out.println("Roman numeral of " + number + " is: " + intToRoman(number));
    }
}

예제 실행 결과

Roman numeral of 3549 is: MMMDXLIX

설명

이 프로그램은 아라비아 숫자를 로마 숫자로 변환한다. 큰 값부터 시작하여 주어진 숫자를 계속 빼고 해당 로마 숫자 문자를 결과에 추가한다.

So...

오늘은 두 가지 문제를 해결하는 프로그램을 작성해보았다. 첫 번째는 부분 집합 합 문제를 해결하는 프로그램으로, 동적 프로그래밍을 이용해 주어진 숫자들로 원하는 합을 만들 수 있는지 확인했다. 두 번째는 아라비아 숫자를 로마 숫자로 변환하는 프로그램으로, 큰 값부터 차례대로 변환하는 방식을 사용했다. 이러한 문제를 통해 자료구조와 알고리즘의 중요성을 다시 한번 느낄 수 있었다.