[카테고리:] 자바 코딩테스트 강좌

문제 설명

계단 수는 다음과 같은 규칙을 따릅니다. n자리 수이며, 각 자리 숫자는 오름차순으로 증가해야 합니다. 즉, 인접한 두 자리 수의 차이는 정확히 1이어야 합니다. 예를 들어, 123, 234, 345는 모두 계단 수입니다.

문제

N이 주어질 때, N자리 계단 수의 개수를 구하는 프로그램을 작성하세요.

입력

• 첫 번째 줄에 자연수 N이 주어집니다. (1 ≤ N ≤ 100)

출력

• N자리 계단 수의 개수를 10007로 나눈 나머지를 출력합니다.

예제 입력

3

예제 출력

14

설명

N이 3이면, 3자리 계단 수는 123, 132, 210, 321, 234, 345, 456, 567, 678, 789 등 총 14개가 존재합니다.

문제 풀이 과정

이 문제를 해결하기 위해서는 다이나믹 프로그래밍(Dynamic Programming)의 기법을 사용할 수 있습니다.

계단 수는 이전 N-1자리 수를 기반으로 한 N자리 수의 조합으로 생각할 수 있습니다. N-1자리 수의 마지막 숫자에 따라 N자리 수의 마지막 숫자가 결정되므로, 이를 고려하여 DP 배열을 업데이트하면 됩니다.

풀이 접근 방식

1. 상태 정의: dp[n][last]를 n자리 계단 수 중 마지막 자리 수가 last인 경우의 개수로 정의합니다. n은 자리 수를 의미하며, last는 마지막 숫자(0~9)를 의미합니다.
2. 초기 상태 설정: 1자리 수의 경우(즉, N=1일 때) 각 숫자(1~9)는 각기 1개의 경우의 수를 가집니다. 따라서 dp[1][1] ~ dp[1][9]는 1, dp[1][0]는 0입니다.
3. 상태 전이: n자리 수는 n-1자리 수에서 만들어집니다. 마지막 숫자가 last일 때, 마지막 숫자는 last-1 또는 last+1일 수 있습니다. 이를 수식으로 표현하면 다음과 같습니다.

                       dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]
                       

   여기서 last는 1부터 8까지의 범위를 가질 수 있습니다(0과 9는 각각 한쪽에 한정되므로).

4. 결과 계산: N자리 수의 개수는 dp[N][0] + dp[N][1] + … + dp[N][9]의 합입니다. 그러나 문제에서 요구하는 것은 10007로 나눈 나머지이므로, 계산 과정에서 이 연산을 수행해야 합니다.

자바 코드 구현

                import java.util.Scanner;

                public class StairNumber {
                    public static void main(String[] args) {
                        Scanner sc = new Scanner(System.in);
                        int N = sc.nextInt();
                        int MOD = 10007;

                        // DP 배열 초기화
                        int[][] dp = new int[N + 1][10];

                        // 1자리 수 초기화
                        for (int i = 1; i < 10; i++) {
                            dp[1][i] = 1;
                        }

                        // DP 테이블 구성
                        for (int n = 2; n <= N; n++) {
                            for (int last = 0; last <= 9; last++) {
                                if (last > 0) { // last가 0이 아닐 경우
                                    dp[n][last] += dp[n - 1][last - 1];
                                }
                                if (last < 9) { // last가 9가 아닐 경우
                                    dp[n][last] += dp[n - 1][last + 1];
                                }
                                dp[n][last] %= MOD; // MOD 연산
                            }
                        }

                        // 결과 합산
                        int result = 0;
                        for (int last = 0; last <= 9; last++) {
                            result = (result + dp[N][last]) % MOD;
                        }

                        // 결과 출력
                        System.out.println(result);
                        sc.close();
                    }
                }
            

예시

입력

3

출력

14

위의 코드를 실행하게 되면, 3자리 계단 수의 개수를 정확하게 구할 수 있습니다.

추가 사항

문제를 해결하고 난 후, 다양한 테스트 케이스로 알고리즘의 정확성을 검증하는 것이 중요합니다. 또한 코드를 최적화하거나 다양한 방법으로 알고리즘을 접근하여 그 결과를 비교하는 것도 좋은 방법입니다.

마지막으로, 다이나믹 프로그래밍 문제는 많은 경우 그래프 이론과도 연결될 수 있으니, 항상 이러한 관점을 갖고 문제를 푸셔야 합니다.

문제 설명

여러분은 최근에 신입사원 채용을 위한 코딩테스트를 준비하고 있습니다. 이 코딩테스트 문제는
‘거짓말쟁이가 되긴 싫어’라는 주제로 구성되어 있습니다. 이 문제에서는 여러 직원의 이야기를
바탕으로 누군가가 거짓말을 하고 있는지를 판단해야 합니다. 직장 내에서 누가 진실을 말하고
누가 거짓말을 하는지를 명확히 구분하기 위한 알고리즘을 개발해야 합니다.

문제 내용

N명의 직원이 있습니다. 각 직원(A, B, C, …)은 다른 직원에 대해서
‘A는 거짓말쟁이다’, ‘B는 거짓말쟁이다’와 같은 식으로 주장합니다.
각 직원의 주장은 모두 신뢰할 수 있고, 주장이 맞지 않는 경우
일반적으로 그 주장은 거짓말이 됩니다.

입력

• 첫 번째 줄에 직원의 수 N (1 ≤ N ≤ 1000)가 주어집니다.
• 다음 N줄에 각 직원의 주장에 대한 정보가 주어집니다. 각 주장은 “이 직원은 거짓말쟁이다” 형식입니다.

출력

가장 거짓말을 많이 한 직원의 수를 출력합니다. 거짓말을 하지 않은 직원의 수가 1명일 경우에는
0을 출력합니다.

문제 풀이 과정

이 문제를 해결하기 위해서는 직원 간의 관계를 분석하고, 각 직원의 주장을 바탕으로
거짓말을 하는 직원 수를 계산해야 합니다. 여기서 우리는 각 직원의 주장이
어떻게 연결되어 있는지를 파악해야 합니다.

1단계: 데이터 구조 설계

우선, 각 직원의 주장을 저장할 수 있는 데이터 구조를 선택해야 합니다.
우리는 각 직원의 번호를 key로 하고, 그 직원이 거짓말이라고 주장하는 직원 리스트를
value로 가지는 Map을 사용할 수 있습니다.

예를 들어, 직원 1이 직원 2를 거짓말쟁이라고 주장한다면, Map은 다음과 같습니다:

                {
                    1: [2],
                    2: [3, 4],
                    3: [1],
                    ...
                }
            

2단계: 그래프 탐색 (DFS 또는 BFS)

Map 구조가 준비되었다면, 이제 그래프 탐색을 통해 누가 진실을 말하고 누가
거짓말을 하고 있는지를 판단해야 합니다. 이를 위해 DFS(Depth-First Search) 또는
BFS(Breath-First Search) 알고리즘을 활용합니다.

3단계: 수집된 데이터 기반으로 결과 계산

탐색이 완료되면 각 직원이 거짓말을 하는지에 대한 정보를 바탕으로
누가 거짓말을 가장 많이 했는지를 계산해 최종 결론을 내립니다.

4단계: 전체적인 코드 작성

자바를 사용하여 위의 단계들을 코드로 구현할 것입니다. 아래는
해당 문제를 해결하기 위한 코드의 예시입니다:

                
                    import java.util.*;

                    public class Main {
                        public static void main(String[] args) {
                            Scanner scanner = new Scanner(System.in);
                            int n = scanner.nextInt();
                            Map> statements = new HashMap<>();
                            
                            // 직원 주장을 입력받기
                            for (int i = 1; i <= n; i++) {
                                int liarIndex = scanner.nextInt();
                                if (!statements.containsKey(i)) {
                                    statements.put(i, new ArrayList<>());
                                }
                                statements.get(i).add(liarIndex);
                            }

                            int maxLiars = 0;

                            // 각 직원에 대해 거짓말쟁이 수를 계산
                            for (int i = 1; i <= n; i++) {
                                HashSet visited = new HashSet<>();
                                boolean[] isLiar = new boolean[n + 1];
                                isLiar[i] = true;

                                dfs(i, statements, visited, isLiar);

                                int countLiars = 0;
                                for (int j = 1; j <= n; j++) {
                                    if (isLiar[j]) countLiars++;
                                }
                                maxLiars = Math.max(maxLiars, countLiars);
                            }
                            System.out.println(maxLiars);
                        }

                        private static void dfs(int employee, Map> statements, 
                                                HashSet visited, boolean[] isLiar) {
                            if (visited.contains(employee)) return;
                            visited.add(employee);

                            if (statements.containsKey(employee)) {
                                for (int liar : statements.get(employee)) {
                                    isLiar[liar] = true;
                                    dfs(liar, statements, visited, isLiar);
                                }
                            }
                        }
                    }
                
            

결론

본문에서는 ‘거짓말쟁이가 되긴 싫어’라는 주제로 문제를 정의하고,
그 문제를 해결하기 위한 알고리즘을 단계별로 설명했습니다.
직원들의 주장에 대한 정보를 활용해 누가 거짓말을 했는지를 분석하고,
그 결과를 통해 거짓말을 가장 많이 한 직원을 알아낼 수 있습니다.
이 과정을 통해 코딩테스트 준비와 알고리즘 문제 해결 능력을 향상시킬 수 있습니다.