백트래킹

[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},..

[Algorithm] 백트래킹(Backtracking)

백트래킹이란 ? 백트래킹은 모든 경우의 수를 고려하는 알고리즘을 의미합니다. 트리 형태의 상태공간이 있을 때, DFS와 같은 완전탐색 알고리즘을 사용하여 모든 지점을 탐색하게 됩니다. DFS는 현재 지점에서 방문할 곳이 있으면 재귀를 호출하여 계속해서 이동하는 특징이 있습니다. 하지만, DFS는 모든 곳을 방문하기 때문에 비효율적인 측면이 있습니다. 따라서 목표지점이 될 가능성이 있는지를 검사한 후 그 지점들만 방문하는 것을 백트래킹 알고리즘이라 합니다. 즉, 백트래킹은 DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 효율적으로 찾는 알고리즘 입니다. 백트래킹과 DFS의 차이점? 백트래킹과 DFS의 차이점을 많이 헷갈려하시는데, ..