궤도

문제 풀이 비트연산과 관련된 문제이다. 여기저기에서 배운거라 개념은 잘 알지만 막상 문제를 풀어보려니까 살짝 당황한건 사실이다. 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..

문제 풀이 myunji.tistory.com/299 [백준] 10972번 : 다음 순열 문제 풀이 myunji.tistory.com/19?category=1154147 [EPPER] 11회 6번 문제 풀이 접근을 잘못했던 문제. 하필이면 그 접근으로도 입력 예시는 전부 다 맞게 나와서 난 그게 맞는 줄 알았다. 근데 혹시나 하는 마. myunji.tistory.com 이 문제의 반대 버전이다. 풀이도 반대로 하면 될테니까 그냥 이번에도 내장 함수를 써야겠다. www.cplusplus.com/reference/algorithm/prev_permutation/?kw=prev_permutation prev_permutation - C++ Reference function template std::prev_pe..

문제 풀이 myunji.tistory.com/19?category=1154147 [EPPER] 11회 6번 문제 풀이 접근을 잘못했던 문제. 하필이면 그 접근으로도 입력 예시는 전부 다 맞게 나와서 난 그게 맞는 줄 알았다. 근데 혹시나 하는 마음에 돌려본 테스트 케이스에서 오류를 발견했다. 먼저 myunji.tistory.com 비슷한 문제를 푼 적 있다. 이때는 알고리즘을 막 공부할 떄라 그렇게 효율적인 코드를 짠 것 같진 않지만 어떤식으로 푸는지에 대한 풀이는 알고 있으니까 www.cplusplus.com/reference/algorithm/next_permutation/?kw=next_permutation next_permutation - C++ Reference function template ..