부분집합

📖 문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 💡 풀이 방식 • 부분 집합 (백트래킹, 재귀) + BFS 필요 자료구조 [전역변수] - 인구 수 저장용 1차원 int형 배열 - 그래프 정보를 저장하기 위한 그래프 리스트 배열 - 부분 집합용 사용 여부 표시용 1차원 boolean형 배열 - 최솟값 [BFS용] - 방문할 원소를 저장하는 Integer형 큐 - 방문 표시용 1차원 boolean형 배열 (연결되었는지 확인용) [두 그룹에 속한 원소들 저장하고, 차이 저장용] - 구역A 원소들 저장할 Integer형 리스트 -..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS (백트래킹) 필요 자료구조 - 1차원 int형 정답 배열 lion - 점수 차이가 최대일 때 라이언이 쏜 화살 수를 저장하는 1차원 int형 배열 arrows 백트래킹으로 n개를 뽑는 조합을 생성해 화살을 어디에 얼마나 맞추는지 구할 수 있다. 그런데 이 때 n = 10일 때 시간초과가 나므로, 백트래킹 메서드의 반복문에 가지치기(특정 조건 추가)해줘야 한다! 여기서 특정 조건은 과녁 i에 라이언이 임의의 점수에서 어피치에게 점수를 따내기 전까지 (arrows[i]

📖 문제 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 💡 풀이 방식 • 백트래킹 부분집합 (재귀) 을 활용해 팀을 나누고, 각 팀별로 능력치를 합하고 그 차이를 최솟값과 비교해 정답으로 출력한다. 💥 유의사항 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다. → 부분집합 🔺 코드 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 31 32 33 34 35 ..