순열 / 조합 / 부분집합

Algorithm/이론

Dev Warrior Jungi 2025. 5. 2. 01:45

모든 순서의 경우를 구하는 것

주어진 원소들을 순서를 고려해 나열

// 예: [1, 2, 3] → 가능한 순열:

[1, 2, 3]  
[1, 3, 2]  
[2, 1, 3]  
[2, 3, 1]  
[3, 1, 2]  
[3, 2, 1]

// 총 경우의 수 : n! (팩토리얼)

예시 문제

[백준 15649] Java - N과 M (1)

https://www.acmicpc.net/problem/15649 N과 M (1) 1) 문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개

devwarriorjungi.tistory.com

순서를 고려하지 않고 n개 중 r개를 뽑는 경우

// 예: [1, 2, 3] 중 2개를 고른 조합:

[1, 2]  
[1, 3]  
[2, 3]

// 총 경우의 수: nCr = n! / (r!(n-r)!)

예시 문제

[백준 15650] Java - N과 M (2)

https://www.acmicpc.net/problem/15650 N과 M (2) 1) 문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개

devwarriorjungi.tistory.com

원소 집합에서 모든 조합을 나열하는 것
뽑거나 안 뽑거나 → 선택의 여지가 2가지씩 있음

// 예: [1, 2]의 부분집합:

[]  
[1]  
[2]  
[1, 2]

// 총 경우의 수: 2^n

예시 문제

[백준 1182] Java - 부분수열의 합

https://www.acmicpc.net/problem/1182 부분수열의 합 1) 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램

devwarriorjungi.tistory.com