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" 1987. 알파벳 시간 제한: 2초 메모리 제한: 256MB 최적의 경로를 선택할 수 있는 규칙은 따로 없고, 가능한 경우를 모두 조사하는 수밖에 없다. 현재까지의 경로를 함께 저장하며, 순회하면 된다. 이때, k 거리의 동일한 칸이라도 지나온 경로에 따라 다른 경우가 되기 때문에, BFS를 하면 Queue에 지수적으로 추가된다. 반면에, DFS는 거리만큼 stack에 쌓으면서 들어가므로, 메모리에 부담이 비... GraphProblem SolvingBacktrackingBacktracking [Java] 백준 15650번 [N과 M(2)] 자바 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 고른 수열은 오름차순이어야 한다. 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 앞에서 풀었던 N과 M(1) 문제와 같은 B... BacktrackingDFSJava백준algorithmBacktracking 에너지 모으기 문제 N개의 에너지 구슬이 일렬로 있고 에너지 구슬을 이용해서 에너지를 모으려고 합니다. i번째 에너지 구슬의 무게는 W_i 입니다. 에너지를 모으는 방법은 다음과 같고 반복해서 사용가능합니다. 1. 에너지 구슬 하나를 고릅니다. 고른 에너지 구슬을 X라고 합니다. (첫번째, 마지막 제외) 2. X번째 에너지 구슬을 제거합니다. 3. W_x-1 X W_x+1의 에너지를 모을 수 있습니다. 제... BacktrackingbaekjoonBacktracking [BaekJoon] 1987 알파벳 (Java) 해당 문제는 NQueens문제처럼 상하좌우로 이동을 했을때 이동이 가능한가?에 대해 판단을 하며 DFS로 문제를 해결하면 쉽게 해결할 수 있다. DFS의 종료시점은 깊이가 아닌 이동이 불가능한 상태인지를 판단하며 상하좌우로 이동할 곳이 없으면 DFS를 더이상 깊게 들어가지 않게 코드를 작성하면 된다.... DFSBacktracking알고리즘 문제풀이baekjoonBacktracking 백준 17136번: 색종이 붙이기 색종이를 사이즈별로 붙이다가 더이상 붙일 수 없을 때 이전의 상태로 돌아가면 된다. 이 때 주의할 점이 몇가지 있다. 색종이를 붙였을 때 10x10 사이즈 종이 바깥으로 벗어나는지 확인. 같은 사이즈의 색종이는 5장까지 사용 가능하기 때문에 색종이가 남아있는지 확인. 색종이를 붙일 공간이 있는 지 확인. iterator에서 정수를 빼서 이전 상태로 돌아갈 수 있다는 사실!... BacktrackingpscppBacktracking [ BOJ / C++ ] 18429번 근손실 이번 문제는 백트레킹을 통해 해결하였다. n이라는 사이클동안 키트를 한번씩만 사용할 수 있으므로 사용 여부를 체크하는 bool형의 chk 배열을 선언해준다. DFS함수의 인자로 일수를 나타내는 day와 현재 중량을 나타내는 cur을 넣어준다. DFS함수 내에서 day와 n이 같을 때, cur이 500보다 크다면 cnt를 증가시켜준다. DFS함수 내에서 for문을 0부터 n-1까지 반복하고, ... Backtracking백트레킹bojcppBacktracking [백준] 14889번: 스타트와 링크 저번주는 엄청 바쁜 시간들을 보냈다. 면접 두 개에 주말에 코테도 있었다... 면접을 보면서 느낀것은 현직자의 입장에서 나는 프로젝트 경험이 많은 것이 아니구나 그리고 CS 공부를 정말 겉핧기 식으로 했었구나를 느꼈다. 그리고 그나마 가장 자신있는 부분이 프론트엔드인데, 자바스크립트나 관련 라이브러리를 써본 경험은 있지만 특정 상황에서 동작하기 위해 어떤 함수를 써야하는지에 대한 질문에 답을... 알고리즘JavaBacktracking브루투포스Backtracking [BOJ / C++] 14888 연산자 끼워넣기 (삼성기출) 문제풀이 주어진 수의 순서를 바꿀 수 없으므로, 인덱스 0부터 N-1까지 모두 선택하여야 한다. 따라서 dfs함수의 레벨을 주어진 수 배열의 인덱스로 따지고, N-1레벨까지 지금까지의 총 합 sum인자와 함께 재귀호출하며 백트래킹한다. 이때 가장 맨 앞의 숫자는 연산자와 관계없이 총 합에 언제든지 들어가있으므로, 첫 호출 형태는 다음과 같다. dfs(1, numbers[0]) : 1레벨 (1... psbojBacktracking삼성기출bruteforceBacktracking 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" 1987. 알파벳 시간 제한: 2초 메모리 제한: 256MB 최적의 경로를 선택할 수 있는 규칙은 따로 없고, 가능한 경우를 모두 조사하는 수밖에 없다. 현재까지의 경로를 함께 저장하며, 순회하면 된다. 이때, k 거리의 동일한 칸이라도 지나온 경로에 따라 다른 경우가 되기 때문에, BFS를 하면 Queue에 지수적으로 추가된다. 반면에, DFS는 거리만큼 stack에 쌓으면서 들어가므로, 메모리에 부담이 비... GraphProblem SolvingBacktrackingBacktracking [Java] 백준 15650번 [N과 M(2)] 자바 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 고른 수열은 오름차순이어야 한다. 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 앞에서 풀었던 N과 M(1) 문제와 같은 B... BacktrackingDFSJava백준algorithmBacktracking 에너지 모으기 문제 N개의 에너지 구슬이 일렬로 있고 에너지 구슬을 이용해서 에너지를 모으려고 합니다. i번째 에너지 구슬의 무게는 W_i 입니다. 에너지를 모으는 방법은 다음과 같고 반복해서 사용가능합니다. 1. 에너지 구슬 하나를 고릅니다. 고른 에너지 구슬을 X라고 합니다. (첫번째, 마지막 제외) 2. X번째 에너지 구슬을 제거합니다. 3. W_x-1 X W_x+1의 에너지를 모을 수 있습니다. 제... BacktrackingbaekjoonBacktracking [BaekJoon] 1987 알파벳 (Java) 해당 문제는 NQueens문제처럼 상하좌우로 이동을 했을때 이동이 가능한가?에 대해 판단을 하며 DFS로 문제를 해결하면 쉽게 해결할 수 있다. DFS의 종료시점은 깊이가 아닌 이동이 불가능한 상태인지를 판단하며 상하좌우로 이동할 곳이 없으면 DFS를 더이상 깊게 들어가지 않게 코드를 작성하면 된다.... DFSBacktracking알고리즘 문제풀이baekjoonBacktracking 백준 17136번: 색종이 붙이기 색종이를 사이즈별로 붙이다가 더이상 붙일 수 없을 때 이전의 상태로 돌아가면 된다. 이 때 주의할 점이 몇가지 있다. 색종이를 붙였을 때 10x10 사이즈 종이 바깥으로 벗어나는지 확인. 같은 사이즈의 색종이는 5장까지 사용 가능하기 때문에 색종이가 남아있는지 확인. 색종이를 붙일 공간이 있는 지 확인. iterator에서 정수를 빼서 이전 상태로 돌아갈 수 있다는 사실!... BacktrackingpscppBacktracking [ BOJ / C++ ] 18429번 근손실 이번 문제는 백트레킹을 통해 해결하였다. n이라는 사이클동안 키트를 한번씩만 사용할 수 있으므로 사용 여부를 체크하는 bool형의 chk 배열을 선언해준다. DFS함수의 인자로 일수를 나타내는 day와 현재 중량을 나타내는 cur을 넣어준다. DFS함수 내에서 day와 n이 같을 때, cur이 500보다 크다면 cnt를 증가시켜준다. DFS함수 내에서 for문을 0부터 n-1까지 반복하고, ... Backtracking백트레킹bojcppBacktracking [백준] 14889번: 스타트와 링크 저번주는 엄청 바쁜 시간들을 보냈다. 면접 두 개에 주말에 코테도 있었다... 면접을 보면서 느낀것은 현직자의 입장에서 나는 프로젝트 경험이 많은 것이 아니구나 그리고 CS 공부를 정말 겉핧기 식으로 했었구나를 느꼈다. 그리고 그나마 가장 자신있는 부분이 프론트엔드인데, 자바스크립트나 관련 라이브러리를 써본 경험은 있지만 특정 상황에서 동작하기 위해 어떤 함수를 써야하는지에 대한 질문에 답을... 알고리즘JavaBacktracking브루투포스Backtracking [BOJ / C++] 14888 연산자 끼워넣기 (삼성기출) 문제풀이 주어진 수의 순서를 바꿀 수 없으므로, 인덱스 0부터 N-1까지 모두 선택하여야 한다. 따라서 dfs함수의 레벨을 주어진 수 배열의 인덱스로 따지고, N-1레벨까지 지금까지의 총 합 sum인자와 함께 재귀호출하며 백트래킹한다. 이때 가장 맨 앞의 숫자는 연산자와 관계없이 총 합에 언제든지 들어가있으므로, 첫 호출 형태는 다음과 같다. dfs(1, numbers[0]) : 1레벨 (1... psbojBacktracking삼성기출bruteforceBacktracking 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