궤도

문제 풀이 먼저 모든 친구 관계를 저장한다. 메모리를 아끼기 위해 myunji.tistory.com/291?category=1154147 [백준] 1707번 : 이분 그래프 문제 풀이 이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다. 위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으 myunji.tistory.com 이때 썼던 방법으로 저장했다. i번째 사람을 시작점으로 하는 dfs를 N번 돌리면서 문제의 조건에 맞는 친구 5명을 찾으면 리턴한다. 문제를 풀고 다른 사람들의 코드를 보니 친구 관계 4개를 찾는걸 종료 조건으로 한 사람들이 많았다. 근데 그거나 이거나 같은 말이니까 상관없다. 소스코드 #include #include u..

문제 풀이 예제 입력 2에 대해 그냥 중복 상관없이 모든 수열을 사전순으로 출력하면 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 가 될 것이다. 여기서 중복을 제거해야 하는데 처음엔 아무리 머리를 굴려봐도 비효율적인 방법만 떠올랐다. 출력한 수열을 모두 저장해서 비교한다거나...각 숫자의 등장횟수를 세서 계산한다거나... 그러다가 백트래킹 과정을 그림으로 그려봐야겠다 싶었다. 현재 1을 선택한 상황에서 백트래킹으로 7을 선택했다. (1-7) 그리고 더 이상 고를 필요가 없으니 다시 1로 올라와서 9로 내려간다. 9가 선택된 상태이다. (1-9) 또다시 1로 올라와서 9를 선택하려고 보니 이전에 선택한 값과 같은 값이다. 이러면 탐색을 하지 않는 것이다. 9 1 9..

문제 풀이 비트연산과 관련된 문제이다. 여기저기에서 배운거라 개념은 잘 알지만 막상 문제를 풀어보려니까 살짝 당황한건 사실이다. S에 들어올 수 있는 값을 7까지로 제한하도록 하겠다. S = 0이라고 하고 이걸 8자리의 2진수로 표현해보면 0000 0000 이다. 여기부터 시작하자. add 3을 한다고 하자. 1

문제 풀이 dp로 풀면 더 빨리 풀 수 있을텐데 난 그냥 완전탐색(브루트포스)으로 풀었다. 문제를 풀고 보니 dfs를 사용한 코드가 많았다. 근데 뭔가 논리가 그냥 이대로 dp 쓰면 되는거 아닌가 싶긴 했다. 소스코드 #include #include #include using namespace std; int N, money, result; vector input; void backtracking(int idx) { if (money > result) //최대 비용 비교 result = money; for (int i = idx; i N; for (int i = 0; i > dur >> profit; in..

문제 풀이 백트래킹으로 탐색하면서 S가 되는 값이 나오는지 확인하면 된다. 부분수열의 길이가 정해진건 아니라 이와 관련된 종료조건은 딱히 없다. S와 같은 부분수열의 합을 찾자마자 return을 하는 실수를 할 수도 있다. 근데 만약 S=0이고 주어진 정수가 -7 7 -3 3이라면 -7 7도 가능한 부분수열이지만 -7 7 -3 3도 가능한 부분수열이다. 이걸 놓치지 않도록 하자. 소스코드 #include using namespace std; int input[20], N, S, sum, cnt; void backtracking(int idx) { for (int i = idx + 1; i < N; i++) { //중복되는 수열을 제거하기 위해 sum += input[i]; //visited 처리 if (..

문제 풀이 사전순으로 출력하라고 했으니까 일단 문자 입력을 정렬해야할 것이다. 백트래킹으로 C길이의 문자열을 만들고, 이 문자열이 모음 1개 이상, 자음 2개 이상의 규칙을 충족하는지 확인하면 된다. 소스코드 #include #include using namespace std; int L, C; char input[15], arr[15]; bool isPromising() { int vowel = 0; for (int i = 0; i = 1) && ((..

문제 풀이 보통의 최단거리 문제와 달리 TSP 문제는 처음 출발지점으로 돌아와야 한다. 그냥 백트래킹으로 경로를 끝까지 찾다가 마지막 지점에서 처음 출발지점으로 돌아올 수 있는 길이 있는지만 확인하면 된다. 소스코드 #include using namespace std; int matrix[10][10], N, cost, min_cost = -1; bool visited[10]; //실시간으로 값을 갱신하는 코드는 갱신을 취소하는 부분을 반드시 넣어야 함 void backtracking(int start, int cur, int num) { if (num == N) { //종료 조건 if (matrix[cur][start] != 0) { //처음 시작점으로 돌아올 수 있는가? cost += matrix[c..

문제 풀이 myunji.tistory.com/73 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇기 때문에 전역 변수 쓸 일이 좀 많다. 백트래킹 문제를 그림으로 myunji.tistory.com 이때 백트래킹으로 풀었던 문제였는데... www.cplusplus.com/reference/algorithm/next_permutation/?kw=next_permutation next_permutation - C++ Reference function template std::next_permutation default (1)template bool next_permutation (Bidi..