완전탐색
[Power Set] 부분집합을 생성하는 다양한 방법
부분집합을 만들고, 모든 원소를 탐색한다. 리스트 or 스트링의 원소들의 모든 조합(순서X)을 확인해야 하는 문제에 적합합니다. 라이브러리 없이 부분집합을 생성하는 방법을 알아보자! 부분집합? n개의 원소를 가진 집합의 원소를 일부 또는 전체로만 이루어진 집합이다. 원소가 n개인 집합의 모든 부분집합의 수는 2^n 개이다. 해당 원소를 포함하거나, 안하거나의 2가지 경우이기 때문에 각각의 경우의 수를 곱한 것이 된다. 구현 ✅ 다중 반복문 원래 집합의 갯수에 따라 반복문의 횟수를 지정한다. 가장 단순한 방법이지만 비효율적이고, 재사용이 불가능하다. bit = [0, 0, 0, 0] for i in range(2): bit[0] = i for j in range(2): bit[1] = j for k in ..
[Permutation] 순열을 생성하는 다양한 방법
라이브러리 없이 순열을 생성하는 방법을 알아보자! 순열이란 n개의 서로 다른 숫자를 순서 대로 나열하는 모든 경우의 수 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산 수식으로 간단하게 표현하면 아래와 같고 아래 수식은 팩토리얼과 동일하다. $${\displaystyle n!=n(n-1)(n-2)\cdots \cdot 2\cdot 1}$$ 완전탐색 완전 탐색시 리스트 or 문자열의 모든 원소를 탐색해야하며, 모든 순서를 검색해야 하는 경우 사용하기에 적합하다. 모든 경우의 수를 확인해야 하는 APS 문제들의 경우 사용할 수 있다. 구현 ✅ 반복문 간단하게 구현이 가능하고 직관적이다. 하지만, 원소의 갯수에 따라 for문을 조정해야 해서 여러 상활에 대응 불가 for i in range(1, 4): ..