개념 가지치기(Pruning)는 탐색 과정에서 필요없는 과정을 줄여 최적화 시키는 것입니다. 단편적인 예를 들면, 탐색한 값들 중 최솟값을 구하는 문제에서 현재까지 탐색한 결과값보다 값이 커질 경우 더이상 탐색하지않고 종료하는 것이 가지치기입니다. 위 사진*은 특정 방법으로 노드 하나하나 탐색하고 있을때, 결과의 최솟값을 구해야하는 문제에서 모든 곳을 탐색한 경우의 수라고 가정해보겠습니다. 이 문제의 답이 빨간색 노드가 가지고있는 값이 최솟값이라고 하고 파란색 노드가 빨간색 노드의 값보다 커지는 위치라고 했을때, 위처럼 모든곳을 탐색할 필요가 있을까요? 파란색 노드 아래로는 탐색하지 않아도 적어도 최솟값이 아니란걸 알 수 있습니다. 따라서 탐색하지 않고 종료하는것이 가지치기 입니다. * 설명을 위한 사진..

목표 부분집합의 원소를 구할 수 있다. 부분집합의 개수를 구할 수 있다. 이번 부분집합에서는 위 두가지 목표에 대해 조합을 통한 구현과 bitmask를 통한 구현을 알아보겠습니다. 구현 RecursiveSubset 첫번째는 조합을 이용한 풀이인데, 조합에 대한 코드나 지식이 부족하다면 여기를 참고하세요. 부분집합은 " 멱집합(개수) = nC0 + nC1 + nC2 + ... nCr + nCr+1 ... + nCn" 와 같은 성질을 가지고 있습니다. 조합 함수에 파라미터로 r을 넘겨주면 쉽게 구할 수 있습니다. void Comb(int idx, int curr, int r) { if (idx == r) { for (int i = 0; i < r; ++i) cout

개념 서로 다른 n개의 수 중에 r개를 선택 nCr = n! / (n-r)! * r! 리스트를 순서에 상관없이 수를 뽑는 것입니다. 사실 완전탐색으로 풀리는 문제가 있지만 많은 문제들이 그렇지 않습니다. 그럴때 최적화를 하여 답을 도출해 내는것이 중요한데, 최적화하기 앞서서 기본 뼈대가되는 탐색인 조합탐색을 알아보도록 하겠습니다. 구현 재귀 호출을 이용해서 조합을 구성하기 위해서는 네가지 파라미터가 필요합니다. nCr에서 n nCr에서 r 기저 조건을 위한 idx 어느곳을 탐색할지 정하는 curr 그러나 n과 r이 고정되어 있다면 idx와 curr만 사용할수도 있습니다. 이처럼 재귀 호출은 변형에 용이합니다. 그리고 아래와 같은 배열 2가지가 필요합니다. 나열한 수를 담을 배열 나열되어져야 할 수를 담은..

문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 해설 단순구현 시뮬레이션 문제입니다. 문제의 조건을 간단히 정리하자면 아래와 같습니다. 공기청정기는 첫번째 열에서 2행을..

문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 해설 단순 구현 시뮬레이션 문제이지만 패턴을 발견하기 까지 고민을 좀 요구했던 문제이다. 문제는 크게 두 부분으로 나눌 수 있..

개념 서로 다른 n개의 수 중에 r개를 선택하여 나열 nPr = n x n-1 x n-2 ...... x n-r+1 리스트를 순서대로 수를 뽑아 나열하는 것. 즉, 순서에 의미가 있는 것이 순열입니다. 반대로 순서에 의미가 없다면 조합이 되겠습니다. Itreative function Recursive function Itreative function은 c++의 STL인 next_permutation 방식입니다. 설명과 직접 구현을 해보도록 하겠습니다. Recursive function은 재귀 호출 방식입니다. 마찬가지로 직접 구현 해보도록 하겠습니다. Iterative function (next_permutation) ① 뒤쪽부터 탐색하며 꼭대기를 찾자 꼭대기를 왜 찾아야 할까요? 두 가지 리스트를 가지..