1. 완전 탐색모든 경우의 수를 탐색한다.그래서 비용이 비싸다. 예를 들어그래프의 인접 행렬에서 연결된 노드들을 반환할 때 완전 탐색을 하게 된다.vector> adjacent(6, vector(6, 0));adjacent[0][1] = true;adjacent[1][1] = true;adjacent[2][2] = true;// 연결된 모든 노드 출력for (int y = 0; y "  2. 백트래킹백트래킹은 완전 탐색에서 가는 방향이 목표에 도달할 가능성이 없다고 판단되면더 이상 그 경로를 탐색하지 않고 되돌아가는 것을 말한다.모든 경우를 탐색하지 않고 조건에 따라 일정만 탐색하는 것을 말한다. 예시Q.N과 N개의 자연수가 주어진다.여기서 몇 개의 숫자를 골라 합을 mod11을 했을 때 나오는 가장 ..

조합어떤 리스트에서 N개를 중복 없이, 순서를 고려하지 않고 선택하는 것을 말한다.예를들어 {1,2,3}에서 2개를 선택하는 경우{1,2}{1,3}{2,3}총 3가지 경우의 수가 존재한다. 조합 형태int selectCount = 2; // 선택할 개수void combi(int start, vector v){ if (v.size() == selectCount) { // Logic return; } for (int idx = start + 1; idx v; combi(-1, v);}combi 함수는 재귀 함수이다.기저 사례를 충족할 때까지(size == 2) 빈 벡터에 인덱스를 순차적으로 집어 넣는다.기저 사례를 충족하면 함수 호출을 종료하고 이전 단계로 돌아간다.DFS와..

순열어떤 리스트에서 뽑는 순서에 따라 결과가 다른 경우를 말한다.예를들어 {1,2,3}에서 3개를 뽑는 경우{1,2,3}, {1,3,2}{2,1,3}, {2,3,1}{3,1,2}, {3,2,1}총 6가지의 경우의 수가 존재한다. 순열 형태vector list = {1,2,3}; do { for (int i : list) cout NextPermutaion(from, to) 입력값from : 리스트의 첫번째 요소to     : 리스트의 마지막 요소 (null)주의리스트는 사전에 오름차순으로 정렬되어 있어야 한다. 순열의 개수순열의 개수는 공식을 통해 구할 수 있다.n = 총 개수r = 선택할 개수nPr = n개 중에 r개를 선택하여 나오는 순열의 개수  참고 순열과 조합해당 포스트는 순열과 조합를 ..

재귀함수 (Recursion)함수 정의에서 자기 자신을 재참조하는 함수이다.큰 덩어리를 작은 덩어리로 나누어 풀 때 사용한다. 재귀함수 형태int Recursion(int n) { 1. 기저 사례 (종료조건) 2. 작업 수행 3. 재귀 호출}int factorial(int n) { if (n === 1) { return 1; } return n * factorial(n-1);} 재귀함수 호출에 따른 스택 변화함수 호출시 새로운 스택프레임이 생성되며 메모리 소모가 발생한다.처음 생성된 스택프레임은 마지막 재귀함수가 종료되기 전까지 유지된다.호출이 많을 경우 스택영역을 벗어나 스택 오버플로우가 발생할 수 있다. (오버플로우가 발생하면 프로그램은 종료된다...