내 맴

문제 ) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net [ 풀이 ] Baekjoon 사이트에는 이 문제가 Backtracking Algorithm이라고 분류되어있길래 Backtracking방법으로 풀어야 하나 했는데, promising한 node들을 추려줘야하는데 그 기준이 없는거 같았다. Maximum과 Minimum값을 둘 다 구해줘야하기 때문에 그냥 모든 경우의 수를 확인해야만..

문제 ) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [ 풀이 ] Backtracking Algorithm을 사용하여 문제를 풀어주었다 - Backtracking Algorithm 이란? ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - Node가 Promising한지 ..

문제 ) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [ 풀이 ] Backtracking Algorithm을 사용하여 문제를 풀어주었다 - Backtracking Algorithm 이란? ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - Node가 Promising한지 ..

- Backtracking Algorithm ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ 모든 경우의 수를 전부 고려한다 ( 브루트 포스 Algorithm과 유사) ✔ 최적화(optimization) 문제와 결정(decision) 문제 ( yes or no question) 를 해결할수있다. ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - 순서 1. State Space Tree에서 DFS를 실시한다 2. 각 Node가 promising한 지 점검 3. If Node가 promising한 경우 → 자손 Node 탐색 Else non promising한 경우 → 부모 Node..

문제 ) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [ 설명 ] N개의 Queen을 서로 상대를 공격하지 않도록 NxN 체스판에 위치 시키는 문제 → 상대를 공격하지 않으려면 같은 행,열,대각선 상에 위치하면 안된다 예를들어 4 Queen의 경우 , 첫번째 queen을 (1,1)에 둔다면 2번째 queen은 노란색으로 표시한 자리에는 올 수 없다. [ 풀이 ] Backtracking Algorithm으로 풀 수 있는 대표적인 문제다. - Backtrack..