[C, C++ 알고리즘]7 n-Queens Problem - BackTracking n-Queens Problem : n x n의 채스판에서 n개의 Queen들이 서로 공격하지 못하게 배치하는 문제. BackTracking : Solution을 찾기 위해 탐색을 하던 중 하고 있는 탐색이 Solution에 도달하지 못할 것 같으면, 그 경로를 더 이상 가지 않는 것. 이는 반복문의 횟수를 줄일 수 있어 효과적이다. Promising : 해가 될 가능성이 있음을 나타냄. Pruning : 유망하지 않아 그 노드에 가지 않음. ----> 어떤 노드의 Promising을 판단하고 만약 유망하지 않다면(Solution에 포함되지 않는 다면), Pruning 후 BackTracking으로 부모 노드로 돌아가는 과정. 코드를 작성할때 이를 기억하며 고려하면서 작성해보자. *** 목표 *** n =.. 2021. 12. 13. All pairs Shortest path Problem - Floyd Warshall Algorithm. All pairs Shortest path(ASP) Problem - 모든 쌍에 대한 최단 거리을 구하는 문제. Floyd Warshall Alogrithm은 ASP 이다. 이를 DP로 구현해보도록 하자. Vertex가 n개가 있고(V1, V2, .... , Vn), Directed, weighted graph이고, 이때 weight는 nonnegative 하다. /// Matrix W /// * i -> j 인 path가 있으면 그 path의 weight를 입력한다. W[i, j] = weight of path i -> j * i -> j 인 path가 없으면 무한대 값을 입력한다. W[i, j] = ∞ * i -> i 이거나 j -> j 인 path는 0을 입력한다. W[i, j] = 0 /// Ma.. 2021. 12. 10. [백준 1010] 다리 놓기 이번 문제는 점화식만 구하면 된다. DP[2][2] = DP[1][1] DP[2][3] = DP[1][2] + DP[1][1] DP[2][4] = DP[1][3] + DP[1][2] + DP[1][1] 규칙이 보이는가? DP[2][3] = DP[1][2] + DP[1][1] 에서 DP[1][1]을 DP[2][2]로 치환하면 DP[2][3] = DP[2][2] + DP[1][2] DP[2][4] = DP[1][3] + DP[1][2] + DP[1][1] 에서 DP[1][2] + DP[1][1]를 DP[2][3]으로 치환하면 DP[2][4] = DP[2][3] + DP[1][3] 그림으로 그리면 쉽다. 이해하기. 한번 해보는 걸 추천s #include using namespace std; int main().. 2021. 11. 26. [백준 1009] 분산처리 이게 분산처리라곤 하는데 사실 규칙만 알고있으면 거창하지 않게 푸는 문제이다. 1~10 까지 컴퓨터가 있고, 주어진 숫자가 얼마든 1의 자리만 얻으면 되는 것이다. 그리고 1 ~ 9 까지의 숫자들의 제곱들은 4개 주기로 숫자가 반복되는 것을 알 수 있다. 그러면 a는 10의 나머지를, b는 4의 나머지를 가지고 풀면 값은 같아지게 된다. 근데 이때, a % 10 == 0, b % 4 == 0 일때는 예외로써 a = 10, b = 4로 처리를 해주면 되겠다. #include #include using namespace std; typedef long long ll; int main() { int T; cin >> T; while(T--){ int a, b, c; cin >> a >> b; if(b%4 ==.. 2021. 11. 15. 이전 1 2 다음