📙[Algo] 24.02.15 ~ 24.02.16 알고리즘

알고리즘 문제) BOJ 15649. N과 M (1)

• 링크 : https://www.acmicpc.net/problem/15649

문제 요약

• 1부터 N까지 자연수 중 중복 없이 M개를 고른 수열

시간 제한

• 1초

입력

• N M
  • 1≤M≤N≤8

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

접근법

• N=4, M=2
• 1~4로 구성된 2자리 수 구하기
• 11 (X) → 숫자 중복 안 됨

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] arr;
    static boolean[] visited;

    public static void recur(int cur) {
        if (cur == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(arr[i]+" ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= N; i++) {
            if(visited[i]) continue;

            visited[i] = true;
            arr[cur] = i;
            recur(cur + 1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];
        visited = new boolean[N + 1];

        recur(0);

        br.close();
    }
}

 

알고리즘 문제) BOJ 15650. N과 M (2)

• 링크 : https://www.acmicpc.net/problem/15650

문제 요약

• 1부터 N까지 자연수 중 중복 없이 M개를 선택한 수열
• 수열은 오름차순일 것

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

접근법

• 오름차순이어야 하므로, 321 이런거 X

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] arr;

    public static void recur(int cur, int start) {
        if (cur == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(arr[i]+" ");
            }
            System.out.println();
            return;
        }

        for (int i = start; i <= N; i++) {
            arr[cur] = i;
            recur(cur + 1, i + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];

        recur(0, 1);

        br.close();
    }
}

 

알고리즘 문제) BOJ 15651. N과 M (3)

• 링크 : https://www.acmicpc.net/problem/15651

문제 요약

• 1부터 N까지 자연수 중 M개를 고른 수열
• 같은 수를 여러 번 골라도 됨

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur) {
        if (cur == M) {
            for (int i = 0; i < M; i++) {
                sb.append(arr[i] + " ");
            }
            sb.append("\\n");
            return;
        }

        for (int i = 1; i <= N; i++) {
            arr[cur] = i;
            recur(cur + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];

        recur(0);
        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 15652. N과 M (4)

• 링크 : https://www.acmicpc.net/problem/15652

문제 요약

• 1부터 N까지 자연수 중 M개를 고른 수열
• 같은 수를 여러 번 골라도 됨
• 수열은 비내림차순(오름차순)일 것

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur, int start) {
        if (cur == M) {
            for (int i = 0; i < M; i++) {
                sb.append(arr[i] + " ");
            }
            sb.append("\\n");
            return;
        }

        for (int i = start; i <= N; i++) {
            arr[cur] = i;
            recur(cur + 1, i);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];

        recur(0, 1);
        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 15654. N과 M (5)

• 링크 : https://www.acmicpc.net/problem/15654

문제 요약

• N개의 자연수 중에서 M개를 고른 수열

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8
• N개의 수가 주어진다.
  • 수는 10000이하 자연수

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

접근법

• 배열에서 M개를 고르는데, 중복 X

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] nums;
    static int[] answer;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur) {
        if (cur == M) {
            for (int i = 0; i < M; i++) {
                sb.append(answer[i] + " ");
            }
            sb.append("\\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            answer[cur] = nums[i];
            recur(cur + 1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];
        answer = new int[M];
        visited = new boolean[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);
        recur(0);
        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 15655. N과 M (6)

• 링크 : https://www.acmicpc.net/problem/15655

문제 요약

• N개의 자연수 중에서 M개를 고른 수열
• 이때 수열은 오름차순 형태여야 함

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8
• N개의 수가 주어진다.
  • 수는 10000이하 자연수

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] nums;
    static int[] answer;
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur, int start) {
        if (cur == M) {
            for (int i = 0; i < M; i++) {
                sb.append(answer[i] + " ");
            }
            sb.append("\\n");
            return;
        }

        for (int i = start; i < N; i++) {
            answer[cur] = nums[i];
            recur(cur + 1, i + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];
        answer = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);
        recur(0, 0);
        System.out.println(sb);

        br.close();
    }
}

알고리즘 문제) BOJ 15656. N과 M (7)

• 링크 : https://www.acmicpc.net/problem/15656

문제 요약

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러번 골라도 됨

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8
• N개의 수가 주어진다.
  • 수는 10000이하 자연수

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] nums;
    static int[] answer;
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur) {
        if (cur == M) {
            for (int i = 0; i < M; i++) {
                sb.append(answer[i] + " ");
            }
            sb.append("\\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            answer[cur] = nums[i];
            recur(cur + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];
        answer = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);
        recur(0);
        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 15657. N과 M (8)

• 링크 : https://www.acmicpc.net/problem/15657

문제 요약

• N개의 자연수 중 M개를 고른 수열
• 같은 수 중복 가능
• 오름차순일

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8
• N개의 수가 주어진다.
  • 수는 10000이하 자연수

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] nums;
    static int[] answer;
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur, int start) {
        if (cur == M) {
            for (int i = 0; i < M; i++) {
                sb.append(answer[i] + " ");
            }
            sb.append("\\n");
            return;
        }

        for (int i = start; i < N; i++) {
            answer[cur] = nums[i];
            recur(cur + 1, i);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];
        answer = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);
        recur(0, 0);
        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 2529. 부등호

• 링크 : https://www.acmicpc.net/problem/2529

문제 요약

• K개 부등호가 주어졌을 때, 부등호 관계를 만족하는 K+1자리의 정수 중 최댓값, 최솟값 찾기
  • 0~9중 선택, 숫자들은 모두 다름

시간 제한

• 1초

입력

• 부등호 문자 개수 k
  • 2≤K≤9
• k개의 부등호 기호가 주어짐

출력

• 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수 출력
• 첫자리가 0인정수도 포함 가능

접근법

1. 완전 탐색으로 생각하기
   • k의 범위가 9개까지므로 최대 10자리 정수까지 구하게 됨. 0~9까지 모든 숫자를 일일이 대입하면서 비교한다면 총 9번 비교하게 되고, 대략 101010101010101010 ⇒ 1억개 연산 소요(9중 for문)
   • for문의 개수가 k에따라 달라지므로 재귀함수를 구현한다.
2. 백트랙킹 가지치기
   • 앞에서부터 숫자를 넣어가며 부등호 관계를 만족하는 애들만 채워가면서, 만족하는 정수는 리스트에 담는다.
   • 리스트를 정렬하고 최소, 최대값을 꺼낸다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int k;
    static String[] signs;
    static int[] arr;
    static ArrayList<String> answer = new ArrayList<>();
    static boolean[] visited;

    static boolean check(int cur) {

        if (cur <= 1) return true;

        if (cur > 1) {
            if (signs[cur - 2].equals("<") && arr[cur - 2] >= arr[cur - 1]) return false;
            if (signs[cur - 2].equals(">") && arr[cur - 2] <= arr[cur - 1]) return false;
        }

        return true;
    }
    static void recur(int cur) {

        if (!check(cur)) return;

        if (cur == k + 1) {
            String str = "";
            for (int i = 0; i < k + 1; i++) {
                str += String.valueOf(arr[i]);
            }
            answer.add(str);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            arr[cur] = i;
            recur(cur + 1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        k = Integer.parseInt(br.readLine());
        signs = br.readLine().split(" ");

        arr = new int[k + 1];
        visited = new boolean[10];

        recur(0);

        Collections.sort(answer);

        sb.append(answer.get(answer.size()-1)+"\\n");
        sb.append(answer.get(0));

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}