kakasoo

숫자가 예쁜 문제다, 14500번. 일단 문제에 대해서 간단한 해설을 쓰자면, 이건 무조건 dfs로밖에 풀 수 없는 문제다. 간단히 문제를 요약하건대, 아무 숫자가 적혀져 있는 2차원 배열이 주어질 때, 그 배열 위에 테트로미노 (이상, 위에 나와 있는 5가지 도형, 그리고 그 도형의 회전과 대칭)를 올려서 테트로미노 위에 적혀져 있는 숫자들의 합이 가장 큰 것을 구하는 문제이다. 고로 테트로미노가 4칸을 합쳐서 만든 도형이라는 특성 상, dfs든 bfs든 4칸이 되는 순간, 합을 반환하고 종료시켜야 하는데, bfs는 한 지점으로부터 상하좌우로 이동하기 때문에, 만들어진 도형이 반드시 인접할 거란 보장이 없다. 그에 반해 dfs는 한붓그리기와 같은 형태라서 안심하고 사용할 수 있다. 다만 dfs의 경우에..

질문에 있는 글인데, 너무나 잘 정리되어 있어서 가지고 왔다. (*이런 것에는 저작권이 없겠지?) 1. 가중치가 없는 최단 경로, 한 마디로 다익스트라 알고리즘을 써야 하는 게 아니면 무조건 bfs라는 것. 2. 모든 칸을 0으로 하나씩 바꿔보는 브루트 포스는, 최악의 경우 (1000 * 1000)^2의 반복이 된다. (map size = 1000 * 1000, 이고 각각의 칸이 모두 1인 경우가 있을 수 있기 때문에 1000000000000 번이다.) 3. 칸마다 방문 체크를 하는 방식으로는 풀 수 없다. 이거 참 중요한 이야기인데, 벽을 부수지 않은 세계와 벽을 부순 적 있는 세계가 있다고 가정해보자. 벽을 부수지 않은 세계를 0번 세계, 그리고 부순 세계를 1번 세계라고 할 때, 0번 세계에서 0번..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; int n, s, sum, counted; int arr[21]; bool visited[21]; void dfs (int start) { visited[start] = true; int cur = start; sum += arr[start]; if (sum == s) { counted++; } for (int i = start + 1; i > n >> s; for (int i = 0; i > arr[i]; for (i..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include using namespace std; int startLink[21]; int arr[21][21]; int visited[21]; int n; void dfs(int cnt, int start) { if (cnt == n / 2) { for (int i = 0; i

알고리즘 구분 알고리즘을 공부하며 가장 헷갈린 것이, 알고리즘의 이름이 무얼 의미하는지 몰랐던 부분이었다. n-Queen 문제를 풀 때도, 풀이를 보고 신기했던 경험이 있었지만 백트래킹에 대한 이해는 얕았다. 그러나 그것이 스도쿠 문제를 풀면서 완전한 이해로 갖춰지게 된 거 같다. 일단 기본적으로, 브루트 포스가 있다. 브루트 포스는 for문이든 중첩된 for문이든 간에 모든 경우의 수를 다 찾아보는 방식이다. 이 브루트 포스에서 방문한 칸을 체크하는 것으로 효율을 꾀하는 것이 dfs와 bfs로 나타난다. 그러나 dfs는 갈래의 마지막까지 방문한 다음에 옳고 그름을 판단하는데, 다음의 문제가 있다 1) 만약 재귀가 끝나지 않는다면? -> 런 타임 에러가 발생한다. 2) 중간에 틀린 걸 판별했다면? -> ..