[코딩테스트] [1759] 암호 만들기 & [10971] 외판원 순회 2 & [14888] 연산자 끼워넣기

[1759] 암호 만들기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

128 MB

85939

41270

28280

44.931%

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

문제풀이

• C개의 문자를 이용해서 L길이의 암호를 만들자
• 최소 한 개의 모음, 최소 두개의 자음이 필요
• 문자는 알파벳 소문자, 중복 없음
• 3 ≤ L ≤ C ≤ 15
• 암호는 알파벳이 증가하는 순서로 배열

Base Case

암호가 원하는 길이를 만족했을 때

        if(length == l) {
            if (vowelCnt >= 1 && l - vowelCnt >= 2) {
                System.out.println(password);
            }
            return;
        }

Recursive Case

암호의 index 번째 문자를 input[index]로 고르는 경우

암호의 index 번째 문자를 input[index]로 고르지 않는 경우

        if(index < c) {
            // password에 input[index] 사용하는 경우
            password[length] = input[index];
            int v = isVowel(input[index]) ? 1 : 0;
            generate(length + 1, index + 1, vowelCnt + v);

            // password에 input[index] 사용하지 않는 경우
            password[length] = 0;
            generate(length, index + 1, vowelCnt);
        }

모음인지 확인하는 함수

    static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

필요한 변수 선언 및 입력 받기

class Main {
        static int l, c;
        static char[] input;
        static char[] password;
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            l = sc.nextInt();
            c = sc.nextInt();
    
            input = new char[c];
            password = new char[l];
            for (int i = 0; i < c; i++) {
                input[i] = sc.next().charAt(0);
            }
            Arrays.sort(input);
            generate(0, 0, 0);
        }
        <---생략---->

[10971] 외판원 순회 2

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

256 MB

63699

23971

14314

34.333%

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

문제 풀이

• N개의 도시를 방문하고 출발 정점으로 복귀해야 한다.
• 간선마다 비용이 존재한다.
• 순회 가능한 경로 중 최소 비용을 사용하는 경로를 구하자.

이 문제는 NP-hard로 유명한 문제이다.

N이 10이하이므로 완전탐색으로 접근해보자. 10!은 3,628,800의 경우가 나온다.

1억~3억이 1초안에 수행될 수 있어 3백만은 빠르게 연산할 수 있다.

재귀함수를 이용해서 완전 탐색을 해보자.

인접 행렬

인접행렬이란, {i} - {j}의 연결관계를 행렬로 표현한 것이다.

src: {1} → dist:{2} 간선의 비용은 10이다.

그래프의 방향 표현이 가능

n개의 정점 → n^2의 공간 복잡도

간선 조회 / 저장 시간 복잡도: O(1)

특정 정점의 모든 간선 조회: O(n)

Base Case

모든 도시(정점)을 모두 방문하고 현재의 내위치가 출발 위치랑 동일한 경우

BaseCase에 도달했을때 도시를 순회하는데 든 비용을 기록, 최솟값과 대조하자.

        if(node == start && cnt == n) {
            answer = Math.min(answer, sum);
            return;
        }

Recursive Case

아직 방문하지 않았고 간선이 연결되어있는 정점을 향해 탐색하자.

만약 다음 방문하는 곳이 0이면 가지 못하는 곳이니 다음 방문할 곳이 0이 아니고 방문한 적이 없다면 여행하자.

그 이후 다른 간선에서 올 것을 대비하여 방문을 false로 변경하자.

        for(int i = 0; i < n; i++) {
            if(!visited[i] && w[node][i] != 0) {
                visited[i] = true;
                travel(start, sum + w[node][i] , i, cnt + 1);
                visited[i] = false;
            }
        }

필요한 변수 선언 및 입력 받기

class Main {
    static int n;
    static int[][] w;
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        w = new int[n][n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j ++) {
                w[i][j] = sc.nextInt();
            }
        }
        travel(0, 0, 0, 0);
        System.out.println(answer);
    }
    <---생략--->

[14888] 연산자 끼워넣기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

512 MB

119331

55196

36667

47.061%

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

문제풀이

이 문제는 수열 사이에 덧셈, 뺄셈, 곱셈, 나눗셈을 넣을 수 있다.

연산자의 우선순위를 무시하고 앞에서 뒤 순서로 계산하는 문제이다.

나눗셈은 몫만 취한다. 만들어지는 결과의 최대, 최소를 구하는 문제이다.

숫자의 개수가 최대 11개이므로 연산자의 개수는 10개가 최대이다.

숫자는 순서가 바뀌지 않고 연산자만 바뀐다.

경우의 수는 총 4^10 == 2^20 == 1,048,576이다.

연산자별 개수 제한이 있으므로, 실제로는 경우의 수가 더 적다.

Base Case

수열의 마지막 숫자에 대한 연산이 완료되었을 때가 재귀 함수가 종료될 때이다.

• 결과 값이 MAX를 갱신 가능하다면 대입
• 결과값이 Min을 갱신 가능하다면 대입

        if (index == n) {
            max = Math.max(max, sum);
            min = Math.min(min, sum);
            return;
        }

Recursive Case

문제에서 정의한 연산 가능횟수가 남아있는 경우에 가능.

사칙연산

• 덧셈, 0
• 뺄셈, 1
• 곱셈, 2
• 나눗셈, 3

        for (int i = 0; i < 4; i++) {
            if (operators[i] > 0) {
                operators[i]--;
                if (i == PLUS) {
                    solve(index + 1, sum + numbers[index]);
                } else if (i == MINUS) {
                    solve(index + 1, sum - numbers[index]);
                } else if (i == MUL) {
                    solve(index + 1, sum * numbers[index]);
                } else if (i == DIV) {
                    if (numbers[index] != 0) {
                        solve(index + 1, sum / numbers[index]);
                    }
                }
                operators[i]++;
            }
        }

필요한 변수 선언 및 입력 받기

사칙연산을 분류하기 위해 PLUS, MINUS, MUL, DIV를 선언해주자.

그리고 n, 수열, 사칙연산 가능 횟수를 입력 받자.

max와 min을 각각 최소값, 최대값으로 설정하여 답이 나왔을때 갱신할 수 있게 해주자.

class Main {
    static final int PLUS = 0;
    static final int MINUS = 1;
    static final int MUL = 2;
    static final int DIV = 3;
    static int n;
    static int[] numbers;
    static int[] operators = new int[4];
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        numbers = new int[n];
        for (int i = 0; i < n; i++)
            numbers[i] = sc.nextInt();
        for (int i = 0; i < 4; i++)
            operators[i] = sc.nextInt();

        solve( 1, numbers[0]);

        System.out.println(max);
        System.out.println(min);
    }
    <----생략---->

전체코드

 import java.util.*;

class Main {
    static final int PLUS = 0;
    static final int MINUS = 1;
    static final int MUL = 2;
    static final int DIV = 3;
    static int n;
    static int[] numbers;
    static int[] operators = new int[4];
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        numbers = new int[n];
        for (int i = 0; i < n; i++)
            numbers[i] = sc.nextInt();
        for (int i = 0; i < 4; i++)
            operators[i] = sc.nextInt();

        solve( 1, numbers[0]);

        System.out.println(max);
        System.out.println(min);
    }

    static void solve(int index, int sum) {
        if (index == n) {
            max = Math.max(max, sum);
            min = Math.min(min, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operators[i] > 0) {
                operators[i]--;
                if (i == PLUS) {
                    solve(index + 1, sum + numbers[index]);
                } else if (i == MINUS) {
                    solve(index + 1, sum - numbers[index]);
                } else if (i == MUL) {
                    solve(index + 1, sum * numbers[index]);
                } else if (i == DIV) {
                    if (numbers[index] != 0) {
                        solve(index + 1, sum / numbers[index]);
                    }
                }
                operators[i]++;
            }
        }
    }
}