궤도

문제 풀이 보통의 최단거리 문제와 달리 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 ..

문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호출한다. 소스코드 #include using namespace std; int cnt; void backtracking(int num) { if (num == 0) { //0이면 카운트 추가 cnt++; return; } for (int i = 3; i >= 1; i--) { //3부터 1까지 뺄 수 있는지 확인 if ((num - i) >= 0) backtracking(num - i); } } int main() { int t, n; cin >> t; for (int i = 0; i > n; backtracking(n)..

문제 풀이 가능한 모양을 하나하나 분리해서 찾는건 이 문제가 브루트포스라고 해도 너무한 방법이다. 보라색 조각을 제외한 나머지 4개의 조각은 백트래킹으로 탐색할 수 있는 조각이다. 백트래킹으로 탐색할 수 있다는걸 쉽게 설명하면 한붓 그리기처럼 탐색할 수 있단 뜻이다. 그럼 보라색 조각을 제외한 나머지 조각은 백트래킹으로 처리한다고 치고, 보라색 조각은 어떻게 처리할까? 이런 조각 하나가 있다고 하자. 이 조각을 기준으로 상하좌우에 조각을 붙이면 이런 + 모양이 될 것이다. 여기에 상하좌우 중 하나의 조각만 빼면 가능한 모든 보라색 조각의 경우가 나올 것이다. 소스코드 링크 = 0) && (nr = 0) && (nc < M)) { //범위에 들어오면 저장 cnt++; arr[i] =..

문제 풀이 홀수인 두 소수의 합으로 짝수를 나타내는 문제이다. 홀수인 두 소수이므로 3부터 시작하면 될 것이고 입력값의 절반까지만 탐색하면 된다. 만약 입력이 8이라면 3+5와 5+3은 같은 말이기 때문이다. 그리고 두 소수의 차가 가장 큰 것을 출력하라고 했는데 그럼 뭐 3부터 탐색하다가 두 소수를 찾으면 바로 출력하면된다. 20은 3+17로도 나타낼 수 있고 7+13으로도 나타낼 수 있지만 두 수의 차가 가장 큰 것은 먼저 발견된 3+17이다. 이 소수를 찾는 과정에서 시간초과가 나지 않도록 빠르게 구하는 것이 중요하다. 나는 에라토스테네스의 체를 사용했다. myunji.tistory.com/61 [백준] 1929번 : 소수 구하기 문제 풀이 에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토..

문제 풀이 예제 입력1을 오름차순 정렬해보자 -10 -9 2 4 4 여기서 중복을 제거하면 -10 -9 2 4 이 배열의 인덱스는 당연히 왼쪽에서부터 0, 1, 2, 3이다. 그리고 이건 각 숫자에 대해 해당 숫자보다 작은 수의 개수가 된다. 소스코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N; long long input; vector arr, sort_arr; cin >> N; for (int i = 0; i > input; arr.push_back(input); //원래 배열 } sort_arr = arr; sort..