부분집합 – 피곤한아이의 개발 블로그

[알고리즘] 17471. 게리맨더링

2026년 02월 04일2024년 02월 26일 작성자: 피곤한아이

0. 문제 17471번: 게리맨더링 1. 문제 이해 2. 제출 가. 통과 solve()에서 가능한 부분집합이 없거나 하나인 경우를 빠르게 걸러낼 생각이었다. 하지만 실제 구현하고 보니 시간복잡도도 상승하고 코드도 더 많이 복잡해졌다. 나. 개선 다. 참고 강사님 코드.

종류 설명 기호 시간 복잡도 순열 N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수 nPr O(N!) 조합 N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수 nCr O(n! /( r! x (n-r)!)) 부분집합 N개의 원소로 부분집합을 만드는 모든 경우의 수 nHr O(2^N) 집합에 포함된 원소들을 선택하는 것. 원소들의 그룹에서 최적의 부분 … 더 읽기