거북이의 IT 공부

백트래킹이란? 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는(Backtracking) 기법을 말한다. -> 반복문의 횟수를 줄여서 효율적이다!!! 좀더 정확하게 말하자면 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 가는 기법을 말한다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다'(완전 탐색 기법) 에 기본 아이디어가 있다. 대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색) 이 있다. 하지만 DFS 는 모든곳..

문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 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 36 37 38 39 #include #include #define MAX 15 using namespace std; vector visited1(MAX); vector visited2(MAX + MAX); vector visi..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 코드 저번시간에는 재귀를 통한 '순열 구현'을 배웠다면 이번시간에는 재귀를 통한 '조합 구현'이다. ** 참고 사이트 : https://yabmoons.tistory.com/99 [ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++) 브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는 결과 값을 찾는 방식이다..

문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹이란? 아래에 정리해 두었다! https://bunnnybin.tistory.com/entry/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-Backtracking-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%B4%EB%9E%80 백트래킹 (Backtracking) 알고리즘이란? 백트래킹이란? 해를 찾아가는 도중, 지금의 경로가 해..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 나의 코드 bfs 코드를 많이 풀었지 dfs는 푼 경험이 없는 것 같아서 dfs로 풀어보았다. 앞으로 배울 백트래킹 알고리즘에 도움이 되기 위해! dfs에서 주의할 점은 일단 인접한 노드는 방문표시를 하고 스택에 집어넣는다. 그래야지 방문한 인접 노드를 또 방문하는 패해를 없앤다. 물론 스택에서 나온 현재 보는 노드가 이미 방문 표시가 되었음을 인지하자. 그러나 dfs는 ..