Backtracking <Baekjoon> #23290 Simulation, BFS, DFS, Backtracking_마법사 상어와 복제 c++ 따라서 물고기 번호 vector<int> fnum, scent_time을 저장하는 맵을 만들어준다 현재 시간을 Time 이라고 두고, 물고기가 상어에게 잡혀 사라질 때 scent_time=Time 을 넣어준다. 그러고 후에 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라질 때, Time-scent_time==2인 경우 scent_time=0으로 만들어주는 방법을 사용한다 1. star... DFSalgorithmBacktracking"삼성SW"simulationBFS"삼성SW" [BaekJoon] 1987 알파벳 (Java) 해당 문제는 NQueens문제처럼 상하좌우로 이동을 했을때 이동이 가능한가?에 대해 판단을 하며 DFS로 문제를 해결하면 쉽게 해결할 수 있다. DFS의 종료시점은 깊이가 아닌 이동이 불가능한 상태인지를 판단하며 상하좌우로 이동할 곳이 없으면 DFS를 더이상 깊게 들어가지 않게 코드를 작성하면 된다.... DFSBacktracking알고리즘 문제풀이baekjoonBacktracking [BOJ / C++] 2580 스도쿠 문제풀이 입력을 받을 때 비어있는 칸의 좌표를 blank 벡터에 다 넣어놓는다. (vetor<pair<int,int>> blank) blank 인덱스 0부터~ blank size까지 레벨을 뻗으면서 스도쿠를 완성시켜주며 dfs를 진행한다. 따라서 blank size까지 레벨이 뻗었을 때 스도쿠가 완성되고, 이때 여러개의 답이 있을 때 하나만 출력해주면 되므로 exit(0)을 사용했다. 3.d... BacktrackingpsbojBacktracking [BOJ / C++] 14889 스타트와 링크 (삼성 기출) 문제풀이 N명의 사람 중, 스타트/링크로 나뉘어진 모든 조합을 구한 후 차이를 계산해서 그 중 제일 작은 것을 출력해야 한다. 조합을 구하기 위해 res배열을 0으로 초기화하고, 전형적인 조합 dfs를 사용하면서 2/N개의 원소를 1로 만들어준다. 총 2/N개가 선택되었을 때 res배열엔 2/N개의 1과 2/N개의 0이 있을 것이다. 1인 것을 스타트팀, 0인 것을 링크팀으로 하여 능력치 차... psbojBacktracking삼성기출bruteforceBacktracking [BOJ / C++] 16987 계란으로 계란치기 기본적인 dfs문제에 조건이 조금 들어있는 문젠데 어이없게 헤맸다. 계란을 칠 때 계란 벡터 내 값 자체를 안바꿔주고, 다른 변수에 넣어두고 변수값을 바꿔줬다. dfs 호출 후 다시 값을 안 돌려놓음 😀 문제풀이 dfs 함수 (hitEgg) 인자로 계란의 start 인덱스를 받는다. 가장 오른쪽에 위치한 계란일 경우 종료한다. 현재 계란이 깨져있는 경우 바로 다음 인덱스로 재귀호출 모든 계란... BacktrackingbruteforcepsbojBacktracking BOJ : 1182 부분수열의 합 순열이므로 index를 이용했다. visit 은 부분수열 숫자들의 index의 리스트들로 이루어진 리스트. 해당 부분수열의 마지막 index보다 큰 index가 visit 에 추가된다.... BacktrackingalgorithmBacktracking [SWEA] 1949. 등산로 조성 제일 긴 등산로의 길이를 반환하라! 높이 : [1, 20] 가장 높은 곳들에서 시작 현재 높이보다 작은 높이로만 이동 가능 한 번 최대 K깊이만큼 산을 깎을 수 있음 (⭐️ 깎았을 때 높이가 0이 되는 것은 허용) 가장 높은 지형들에서 DFS()를 호출하여 가장 긴 등산로를 찾는다. DFS로 구현했다. 좌표를 기록할 Pair 클래스를 구현했다. 산을 깎았을 때 map[][] 의 값을 바꾸지 ... DFSBacktrackingSWEA알고리즘Backtracking [09663] N-Queen 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 함수 bool isAvailable(int x, int y) x, y좌표에 que... Backtracking백준단계별로 풀어보기Backtracking <Baekjoon> #14888 DFS_연산자 끼워넣기 c++ 삼성 코딩테스트 기출 문제라고 한다 숫자들이 주어지고 그 사이에 적절하게 연산자를 끼워넣어서 최댓값과 최솟값을 구해야 한다. 주어진 연산자를 모두 다 썼을 때의 sum을 maxSum, minSum 과 비교해서 최댓값, 최솟값을 구해준다. e.g. num={1,2,3,4,5,6}, (+)2개, (-)1개, (x)1개, (÷)1개인 경우 1 ⓐ 2 ⓑ 3 ⓒ 4 ⓓ 5 ⓔ 6 에서 각 ⓐⓑⓒⓓⓔ... algorithmDFSBacktrackingbaekjoon"삼성SW""삼성SW" <Baekjoon> #14500 DFS_테트로미노 c++ 처음에는 문제를 보고 모든 테트로미노의 모양을 구해야 하는 아이디어밖에 떠오르지 않았다. 그래서 다른 사람들의 풀이를 많이 참고했다. (실제로 어떤 사람은 모든 경우의 수를 구한 사람도 보았다) 먼저 테트로미노를 보면 ㅜ 이 모양 이외에는 깊이가 4인 모양임을 알 수 있다 (테트로미노를 대칭시키고 회전을 시킬 수 있다고 했으므로) DFS 함수 DFS 함수의 파라미터로는 int y, int x... algorithmDFSBacktrackingbaekjoon"삼성SW""삼성SW" [leetcode] Combination Sum III 유의할점 문제 제대로 읽기 풀이 sum이 n보다 큰경우 . temp에 저장된 갯수가 원하는 갯수 k 보다 큰경우 → backtracking 크기가 k에 도달했을때, sum과 같을때 → 정답 크기가 k에 도달했을때, sum과 다름 → backtracking 코드 C++... BacktrackingarrayBacktracking 백준 2961, 도영이가 만든 맛있는 음식 - Brute Force, Backtracking 백트래킹 구현에 약간의 차이 브루트 포스 + 백트래킹: 백트래킹으로 조합(부분 집합)을 구성하고, 구성한 모든 경우를 확인 n 개의 재료들 중에서 1 ~ n 개 조합 (중복 X, 순서 X) 선택 1개 조합 선택 후, 차이 계산 2개 조합 선택 후, 차이 계산 n 개 조합 선택 후, 차이 계산 각 조합들에 대해 맛 최소 차이 갱신해나감 조합(Combination): C(n, k) = n! x ... 알고리즘코딩 테스트백준 2961 도영이가 만든 맛있는 음식백트래킹brute forceBacktracking브루트 포스Backtracking
<Baekjoon> #23290 Simulation, BFS, DFS, Backtracking_마법사 상어와 복제 c++ 따라서 물고기 번호 vector<int> fnum, scent_time을 저장하는 맵을 만들어준다 현재 시간을 Time 이라고 두고, 물고기가 상어에게 잡혀 사라질 때 scent_time=Time 을 넣어준다. 그러고 후에 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라질 때, Time-scent_time==2인 경우 scent_time=0으로 만들어주는 방법을 사용한다 1. star... DFSalgorithmBacktracking"삼성SW"simulationBFS"삼성SW" [BaekJoon] 1987 알파벳 (Java) 해당 문제는 NQueens문제처럼 상하좌우로 이동을 했을때 이동이 가능한가?에 대해 판단을 하며 DFS로 문제를 해결하면 쉽게 해결할 수 있다. DFS의 종료시점은 깊이가 아닌 이동이 불가능한 상태인지를 판단하며 상하좌우로 이동할 곳이 없으면 DFS를 더이상 깊게 들어가지 않게 코드를 작성하면 된다.... DFSBacktracking알고리즘 문제풀이baekjoonBacktracking [BOJ / C++] 2580 스도쿠 문제풀이 입력을 받을 때 비어있는 칸의 좌표를 blank 벡터에 다 넣어놓는다. (vetor<pair<int,int>> blank) blank 인덱스 0부터~ blank size까지 레벨을 뻗으면서 스도쿠를 완성시켜주며 dfs를 진행한다. 따라서 blank size까지 레벨이 뻗었을 때 스도쿠가 완성되고, 이때 여러개의 답이 있을 때 하나만 출력해주면 되므로 exit(0)을 사용했다. 3.d... BacktrackingpsbojBacktracking [BOJ / C++] 14889 스타트와 링크 (삼성 기출) 문제풀이 N명의 사람 중, 스타트/링크로 나뉘어진 모든 조합을 구한 후 차이를 계산해서 그 중 제일 작은 것을 출력해야 한다. 조합을 구하기 위해 res배열을 0으로 초기화하고, 전형적인 조합 dfs를 사용하면서 2/N개의 원소를 1로 만들어준다. 총 2/N개가 선택되었을 때 res배열엔 2/N개의 1과 2/N개의 0이 있을 것이다. 1인 것을 스타트팀, 0인 것을 링크팀으로 하여 능력치 차... psbojBacktracking삼성기출bruteforceBacktracking [BOJ / C++] 16987 계란으로 계란치기 기본적인 dfs문제에 조건이 조금 들어있는 문젠데 어이없게 헤맸다. 계란을 칠 때 계란 벡터 내 값 자체를 안바꿔주고, 다른 변수에 넣어두고 변수값을 바꿔줬다. dfs 호출 후 다시 값을 안 돌려놓음 😀 문제풀이 dfs 함수 (hitEgg) 인자로 계란의 start 인덱스를 받는다. 가장 오른쪽에 위치한 계란일 경우 종료한다. 현재 계란이 깨져있는 경우 바로 다음 인덱스로 재귀호출 모든 계란... BacktrackingbruteforcepsbojBacktracking BOJ : 1182 부분수열의 합 순열이므로 index를 이용했다. visit 은 부분수열 숫자들의 index의 리스트들로 이루어진 리스트. 해당 부분수열의 마지막 index보다 큰 index가 visit 에 추가된다.... BacktrackingalgorithmBacktracking [SWEA] 1949. 등산로 조성 제일 긴 등산로의 길이를 반환하라! 높이 : [1, 20] 가장 높은 곳들에서 시작 현재 높이보다 작은 높이로만 이동 가능 한 번 최대 K깊이만큼 산을 깎을 수 있음 (⭐️ 깎았을 때 높이가 0이 되는 것은 허용) 가장 높은 지형들에서 DFS()를 호출하여 가장 긴 등산로를 찾는다. DFS로 구현했다. 좌표를 기록할 Pair 클래스를 구현했다. 산을 깎았을 때 map[][] 의 값을 바꾸지 ... DFSBacktrackingSWEA알고리즘Backtracking [09663] N-Queen 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 함수 bool isAvailable(int x, int y) x, y좌표에 que... Backtracking백준단계별로 풀어보기Backtracking <Baekjoon> #14888 DFS_연산자 끼워넣기 c++ 삼성 코딩테스트 기출 문제라고 한다 숫자들이 주어지고 그 사이에 적절하게 연산자를 끼워넣어서 최댓값과 최솟값을 구해야 한다. 주어진 연산자를 모두 다 썼을 때의 sum을 maxSum, minSum 과 비교해서 최댓값, 최솟값을 구해준다. e.g. num={1,2,3,4,5,6}, (+)2개, (-)1개, (x)1개, (÷)1개인 경우 1 ⓐ 2 ⓑ 3 ⓒ 4 ⓓ 5 ⓔ 6 에서 각 ⓐⓑⓒⓓⓔ... algorithmDFSBacktrackingbaekjoon"삼성SW""삼성SW" <Baekjoon> #14500 DFS_테트로미노 c++ 처음에는 문제를 보고 모든 테트로미노의 모양을 구해야 하는 아이디어밖에 떠오르지 않았다. 그래서 다른 사람들의 풀이를 많이 참고했다. (실제로 어떤 사람은 모든 경우의 수를 구한 사람도 보았다) 먼저 테트로미노를 보면 ㅜ 이 모양 이외에는 깊이가 4인 모양임을 알 수 있다 (테트로미노를 대칭시키고 회전을 시킬 수 있다고 했으므로) DFS 함수 DFS 함수의 파라미터로는 int y, int x... algorithmDFSBacktrackingbaekjoon"삼성SW""삼성SW" [leetcode] Combination Sum III 유의할점 문제 제대로 읽기 풀이 sum이 n보다 큰경우 . temp에 저장된 갯수가 원하는 갯수 k 보다 큰경우 → backtracking 크기가 k에 도달했을때, sum과 같을때 → 정답 크기가 k에 도달했을때, sum과 다름 → backtracking 코드 C++... BacktrackingarrayBacktracking 백준 2961, 도영이가 만든 맛있는 음식 - Brute Force, Backtracking 백트래킹 구현에 약간의 차이 브루트 포스 + 백트래킹: 백트래킹으로 조합(부분 집합)을 구성하고, 구성한 모든 경우를 확인 n 개의 재료들 중에서 1 ~ n 개 조합 (중복 X, 순서 X) 선택 1개 조합 선택 후, 차이 계산 2개 조합 선택 후, 차이 계산 n 개 조합 선택 후, 차이 계산 각 조합들에 대해 맛 최소 차이 갱신해나감 조합(Combination): C(n, k) = n! x ... 알고리즘코딩 테스트백준 2961 도영이가 만든 맛있는 음식백트래킹brute forceBacktracking브루트 포스Backtracking