백트래킹

1. 개요 안녕하세요. 이 문제의 유형은 브루트포스, 백트래킹입니다. 모든 경우의 수를 도입해 보고 정답을 구할 수 있는지 확인해 보시면 됩니다. 이 문제에서 경우의 수는 N * N 크기의 복도 빈칸 세 곳을 결정하는 개수를 의미하겠죠. N은 6 이하까지 가능하니깐 최악의 경우는 36C3이 됩니다. 또 세 곳만 결정하면 되니깐 삼중 for loop로 풀이하셔도 무방합니다. 하지만 벽을 세울 곳이 5가지나 그 이상이라면 백트래킹이 더 간편하겠죠. 2. 문제 풀이2 - 1. 벽 위치 결정하기 위 설명과 같이 삼중 for loop나 백트래킹을 사용해서 빈 칸 세 곳을 벽으로 결정하시면 됩니다. 최악의 경우 시간복잡도는 O(36C3) = O(28,560)가 됩니다. 2 - 2. 학생 감지하기 선생님들이 놓인..

1. 개요 안녕하세요. 이 문제의 유형은 백트래킹입니다. 응용이 거의 없어 쉽게 풀이할 수 있었습니다. 백트래킹을 적용할 수 있는 판단 기준은 N이 매우 작아야 합니다. 대략적으로 N이 20 이하인 경우 백트래킹 적용이 가능합니다.  그런데 테스트케이스가 신경쓰여 적용을 못하시는 경우도 있을 것 같습니다. 문제에서 테스트케이스가 최대 몇 개까지 주어지는지 명시되어있지 않습니다. 보통 이런 경우에는 시간복잡도에 영향을 주지 않는다는 의미이므로 신경 쓰실 필요가 없습니다. 2. 문제 풀이 func(int idx, int score)라는 함수를 선언해 재귀로 구현하여 백트래킹을 구현했습니다. idx는 포지션 번호입니다. 11명의 선수 중 0이 아니고 포지션이 결정되지 않은 선수를 선택하여 idx번 포지션을 부..

1. 개요 안녕하세요. 이번에 풀어본 문제의 유형은 백트래킹입니다. 단순하게 백트래킹을 사용하면 끝이라 쉬웠지만 관리해야 할 데이터가 적진 않아서 이를 처리할 방법을 생각해야 하는 문제였습니다. 정답이 되는 조건을 만족하는 경우가 여러 개 존재하는 입력 데이터가 존재하고 그중 사전순으로 가장 빠른 순 하나만 출력해야 합니다. 이 두 가지 경우를 처리할 수 있어야 풀이할 수 있는 문제였습니다. 2. 문제 풀이 우선 각 입력으로 주어지는 데이터는 식재료의 영양분이고, 각각 단백질, 지방, 탄수화물, 비타민, 비용이 주어집니다. 이를 헤더의 tuple를 using 키워드를 사용해 tiii로 명명하여 관리해 줍니다. 그리고 연산 과정을 단순화하기 위하여 operator+=() 함수를 오버라이딩하여 구현했습니다..

1. 문제 풀이 문제 유형은 백트래킹입니다. 저는 각 재귀 함수에서 부메랑의 중심이 되는 cx, cy를 결정하면 날개 두 부분을 계산한 다음 사용 중인지 배열 밖을 벗어나는지 검사한 뒤 유효하다면 계산에 더해주는 방식을 사용했습니다. 배열의 크기가 5 x 5여서 백트래킹을 사용했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typ..

1. 문제 풀이 문제 유형은 백트래킹 + 그래프 탐색입니다. 연구소의 도면을 입력받을 때, 벽을 제외한 칸들을 countOfBlank라는 변수에 저장했습니다. 그리고 2를 입력받은 위치 ( i, j )에 대해서 virus라는 pair 를 저장하는 벡터에 위치 정보를 삽입했습니다. 풀이에 대한 방법은 간단합니다. 백트래킹을 통해 virus에 저장된 위치 중 m개를 선택해 준 다음, 그래프 탐색을 돌리면 됩니다. 이때, flood fill과 최단 거리 갱신을 동시에 진행하고, flood fill 된 칸 수와 countOfBlank의 개수가 같은지 비교하는 처리를 해주면서 값을 반환하게 하는 방식을 사용했습니다.  2. 코드#include using namespace std;typedef long long l..

1. 문제 풀이 2차원 배열이 나오길래 DFS나 BFS일거라고 추측하였는데, 문제를 모두 읽어보고 핀이 최대 8개라는 조건을 확인하고 백트래킹을 사용할 수 있음을 파악했습니다. 배열의 크기가 안 주어져있길래 직접 예제 입력을 확인했습니다. base condtion을 지정하는 방법이 까다롭지만 flag 변수를 둬서 해결했습니다. 실행부는 좀 길긴 하지만 문제의 요구 사항을 직관적으로 구현했습니다. 문제를 풀이하고 질문게시판 구경을 좀 했는데, 남은 핀의 개수를 가지고 이동 횟수를 계산할 수 있다는 사실을 알았습니다. 그 이유는 이동 한 번에 핀 하나가 지워지므로 (남은 핀) = (원래 핀 개수) - (이동 횟수)가 된다고 합니다. 그래서 제 코드는 개선할 여지가 있어 보입니다만 할 일이 많아서 넘어가기로 ..

1. 문제 풀이 브루트포스 애드훅 문제였습니다. 저는 백트래킹을 사용했습니다. 입력받은 문자열의 각 알파벳 빈도수를 기록하였습니다. 그 후 각 숫자에 해당하는 단어들이 문자열 s에서 몇 개까지 뽑아낼 수 있는지 검사해 cnt 배열에 저장했습니다. 이 두 작업은 백트래킹 내 body가 커지지 않게 하려고 전처리한 겁니다. 백트래킹의 base condition은 k가 10일 때 남아있는 알파벳이 있는지 검사하는 방식으로 했습니다. 만약 남아있는 게 없다면 true를 반환해 순차적으로 종료되게 하였습니다. 백트래킹의 body에서는 숫자 k를 1개부터 cnt[k]까지 하나씩만 추가하면서 k+1로 넘어가게 했고, cnt[k]까지 추가해도 true를 반환 못 받았다면 k 숫자를 추가하지 않고 넘어가게 했습니다.  ..

1. 문제 풀이 백트래킹 문제입니다. 계란의 내구도 정보를 백트래킹의 조건 중 하나로 사용하면 쉽게 풀 수 있습니다. 예를 들어 i번째 계란으로 j번째 계란을 친다고 한다면 s[i]는 w[j]만큼 감소시키고, s[j]는 w[i]만큼 감소시키면서 s[i]나 s[j]가 0 이하가 되면 계란이 깨진 것으로 간주할 수 있습니다. 따라서 상태 공간 트리에서 깨진 계란과 아직 깨지지 않은 계란을 판별할 수 있어 문제 풀이가 가능합니다. 2. 코드// Authored by : chjh2129#include using namespace std;int n;int s[10], w[10]; // s[i] : i-th 계란 내구도, w[i] : i-th 계란 무게int ans; // 깰 수 있는 계란의 최대 개수/* k-t..