- Today
- Total
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- MariaDB
- CSS
- LEVEL1
- First Project
- javascript
- 코딩테스트
- typescript
- Docker
- Git
- 에러핸들링
- LEVEL 2
- TMIL
- java
- 배포
- TWIL
- LEVEL 1
- react
- sql
- 프로그래머스
- CRUD
- Refactoring
- TIL
- Err-Handling
- 아고라스테이츠
- 코어 자바스크립트
- 면접을 위한 cs 전공지식 노트
- 알고리즘
- 오늘도 개발자가 안된다고 말했다
- 리팩터링 2판
- mongodb
Archives
성장에 목마른 코린이
(Advanced) Algorithm with Math - 멱집합 본문
728x90
(Advanced) Algorithm with Math - 멱집합
어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합 이라고 합니다.
집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개입니다. 그리고 이 모든 부분집합을 통틀어 멱집합이라고 합니다.
이렇게 모든 부분집합을 나열하는 방법은 다음과 같이 몇 단계로 구분할 수 있습니다.
부분집합을 나열하는 방법에서 가장 앞 원소가 있는지, 없는지에 따라 단계를 나누는 기준을 결정합니다.
멱집합을 구하는 방법에서 각 단계를 유심히 살펴보면, 순환 구조를 띠는 것을 확인할 수 있습니다.
여기서 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법입니다.
따라서, 문제를 작은 단위로 줄여나가는 재귀를 응용할 수 있습니다.
예를 들어 PowerSet 이라는 멱집합의 개수를 리턴하는 함수를 작성한다면, PowerSet 함수에서 자기 자신을 호출하며 문제를 더 작은 문제로 문제의 크기를 줄여 해결할 수 있습니다.
문제가 가장 작은 단위로 줄어들고, 함수가 리턴될 때 카운트를 올리는 방식으로 멱집합의 개수를 구할 수 있습니다.
'CodeStates > Section 3 (백엔드)' 카테고리의 다른 글
데이터베이스 설계 (관계형 데이터베이스) (0) | 2022.04.07 |
---|---|
ACID (Atomicity, Consistency, Isolation, Durability) (0) | 2022.04.07 |
Algorithm with Math - GCD, LCM (최대 공약수, 최소 공배수) (0) | 2022.04.06 |
Algorithm with Math - 순열, 조합 (nPr, nCr) (0) | 2022.04.06 |
알고리즘과 수학 (0) | 2022.04.06 |
Comments