조합

[BOJ, Python] 소문난 칠공주

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 1. 먼저 25명(5X5) 중에 7명을 뽑는 경우를 구합니다. 조합(순서는 신경쓰지 않음) 으로 for문을 25만큼 돌면서 visited[i // 5][i % 5]를 방문체크해서 모든 조합을 구합니다. 2. 구한 조합이, 서로 가로세로로 붙어있는지 체크하기 위해 bfs를 돌립니다. bfs로 4방 탐색을 하면서, 방문한 적 있으면 조합에 속하는 학생이라는 의미이므로 솜파이면 som +=1, 도연파이면 doyeon += 1을 진행합니다. 3. bfs를 끝내고 솜파..

[백트래킹] 조합, 순열, 중복조합, 중복순열 (재귀이용)

목차 조합 순열 중복조합 중복순열 들어가며 백준에서 백트래킹 문제를 풀 때, 문제보고 대충 이런 식이면 되겠지 하고 문제들을 풀다 보니 헷갈리는 부분이 있었습니다. 그동안 머릿속에 정리된 내용 없이 중구난방으로 문제를 풀었는데, 정리된 내용이 없나 하고 찾아보다가 얍문님의 블로그 포스팅을 보고 이거다 싶어서 하나로 정리해두려고 합니다. 조합 조합이란? 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것을 의미합니다. 가장 중요한 것은 순서가 상관없다는 점입니다. 예를 들어 {1, 2, 3, 4, 5}로 이루어진 집합이 있을 때, 3개를 선택한다고 해봅시다. 이때 {1, 2, 3}과 {3, 2, 1}은 같은 부분집합입니다. 즉, {1, 2, 3} , {1, 2, 4},..