[백준 baekjoon] N과 M 모든 유형 뽀개기 - Java

박소은·2024년 5월 29일
0

알고리즘 공부

목록 보기
1/13

순열

1. 순열

서로 다른 n개에서 r개를 택해 일렬로 나열하는 것

  • 문제

    https://www.acmicpc.net/problem/15649

    • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
    • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 풀이법
    • visit[] 배열 사용 : 중복되어 저장되는지를 체크한다.
    • 0 <= i < n : 비내림차순 정렬 X
    • if(!visit[i]) 일 때 arr[depth] 에 값을 저장
    • if (depth == r) 이 되면 arr의 값을 문제의 조건에 맞게 처리하고 return한다.

2. 중복 순열

서로 다른 n개에서 중복을 허락하여 r개를 택해 일렬로 나열하는 것

  • 문제

    https://www.acmicpc.net/problem/15651

    • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
    • 1부터 N까지 자연수 중에서 M개를 고른 수열
    • 같은 수를 여러 번 골라도 된다.
  • 풀이법
    • 이미 사용한 값을 중복해서 사용해도 상관 없다.
      • visit[] 배열 사용 X
      • if(!visit[i]) 확인 X
    • 0 <= i < n
      • 비내림차순 정렬 X
    • arr[depth] 에 값을 저장
    • if (depth == r) 이 되면 arr의 값을 문제의 조건에 맞게 처리하고 return한다.

3. 같은 것이 있는 순열

  • 경우의 수

    • n개 중에 같은 것이 각각 p개, q개, ... , r개씩 있을 때 이들을 모두 일렬로 나열하는 순열의 수는

        n! / (p! * q! * r!) (단, p+q+...+r = n)
  • 문제

    https://www.acmicpc.net/problem/15663

    • N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
    • N개의 자연수 중에서 M개를 고른 수열
    • N개의 자연수에는 서로 같은 수가 존재할 수 있다.
  • 풀이법

4. 같은 것이 있는 중복 순열

  • 문제
    https://www.acmicpc.net/problem/15665
    N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

    • N개의 자연수 중에서 M개를 고른 수열
    • 같은 수를 여러 번 골라도 된다.
  • 풀이법

    • before 변수 사용
      • 이전에 탐색한 노드의 값을 저장한다.
      • 현재 탐색하려는 노드의 값이 이전에 탐색한 노드의 값 (before)과 같은지를 체크한다.
      • 만약 같다면, 뒤이어 만들어질 수열은 직전에 만든 수열과 같다. 중복되는 수열이 있으면 안되기 때문에 이 경우를 건너뛰고 탐색을 진행한다.
      • 다를 경우에만 arr[depth] 에 현재 노드의 값을 저장한다.
    • HashSet을 이용해볼까?
    • 0 <= i < n
      • 비내림차순 정렬 X
        • ex) 91과 19를 다르게 count한다.
    • if (depth == r) 이 되면 arr의 값을 문제의 조건에 맞게 처리하고 return한다.

조합

1. 조합

서로 다른 n개에서 r개를 택하는 것

  • 문제
    https://www.acmicpc.net/problem/15650
    • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
    • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
    • 고른 수열은 오름차순이어야 한다.
  • 풀이법

2. 중복 조합

서로 다른 n개에서 중복을 허락하여 r개를 택하는 것

  • 경우의 수

    • 2개의 문자 a, b에서 중복을 허락하여 3개를 택하는 조합은 aaa, aab, abb, bbb 4가지이다.
  • 문제
    https://www.acmicpc.net/problem/15652

    • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
    • 같은 수를 여러 번 골라도 된다.
    • 1부터 N까지 자연수 중에서 M개를 고른 수열
    • 고른 수열은 비내림차순이어야 한다.
    • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
  • 풀이법

3. 같은 것이 있는 조합

  • 문제
    https://www.acmicpc.net/problem/15664

    N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

    • N개의 자연수 중에서 M개를 고른 수열
    • 고른 수열은 비내림차순이어야 한다.
    • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
  • 풀이법

4. 같은 것이 있는 중복 조합

  • 문제
    https://www.acmicpc.net/problem/15666

    N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

    • N개의 자연수 중에서 M개를 고른 수열
    • 같은 수를 여러 번 골라도 된다.
    • 고른 수열은 비내림차순이어야 한다.
    • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
  • 풀이법

    • before 변수 사용
      • 이전에 탐색한 노드의 값을 저장하고 현재 탐색하려는 노드의 값과 비교한다.
      • 다를 경우에만 arr[depth] 에 현재 노드의 값을 저장한다.
    • cnt <= i < n
      • 비내림차순 정렬 O
      • 현재 노드의 값을 사용했다면 이전 노드의 값은 탐색할 필요가 없다.
    • if (depth == r) 이 되면 arr의 값을 문제의 조건에 맞게 처리하고 return한다.

정리

유형이 많아서 시간을 들여서 정리를 해보았다. 헷갈리지 않게 틈틈이 복습하자!

profile
Backend Developer

0개의 댓글