완전탐색
-
백준 17825 주사위 윷놀이Algorithm/BOJ 2021. 4. 4. 18:53
출처: www.acmicpc.net/problem/17825 분류: 완전탐색 접근방식 꽤나 시간이 오래 걸렸던 문제네요.. 저는 5개의 루트로 나눠서 생각을 해봤는데요, 이동하고 나서 해당 칸이 다른 루트로 가야 한다면 루트를 바꿔주는 방식으로 풀었습니다. 이런 식으로 루트를 생각하면 다음과 같이 초기화 해줄 수 있습니다. var root = [[Int]](repeating: [Int](), count: 5) root[0] = (0...19).map { $0 * 2 } root[1] = [0, 13, 16, 19] root[2] = [0, 22, 24] root[3] = [0, 28, 27, 26] root[4] = [25, 30, 35, 40, 0] 1, 2, 3 같은 경우 특정 칸에서 멈출 때만 이동..
-
백준 17779 게리맨더링 2Algorithm/BOJ 2021. 4. 4. 15:59
출처: www.acmicpc.net/problem/17779 분류: 완전탐색 접근방식 주어진 요구사항 대로 구역을 나눠서 찾으면 되는 완전탐색 문제였습니다. 5번 구역의 범위를 계산하는 부분에서 애를 많이 먹었습니다... 😭 각 구역을 구분하는 부분만 다시 보면 될 것 같은데 간단하게 살펴보겠습니다. 우선 5구역을 시작하는 점을 (pr, pc) 라고 하면, 1구역의 r, c를 검사할 때, c p.c), pr - (c - pc) 보다 크거나 같은지로 계산해줄 수 있습니다. if c p.c && r >= p.r - (c-p.c)) { population[0] += map[r][c] } 같은 방식으로 2구역을 생각해보면, 큰 범위는 c > pc + d1 && r p.c+d1, r = p.c && r = p.c..
-
백준 17406 배열 돌리기4Algorithm/BOJ 2021. 3. 29. 14:00
출처: www.acmicpc.net/problem/17406 분류: 완전탐색 접근방식 주어진 rcs 의 순열을 뽑아주고 주어진 대로 잘 구현하면 되는 문제였습니다. 아직 순열이 익숙하지 않으시다면 여기로 :) 완전탐색의 문제는 늘 그렇죠. 알겠는데 어케 구현하냐....... 머리가 안 돌아가서 배열 돌리는 데 한참이 걸렸습니다 😭 이건 뭐 다른 방법보다 직접 해보면서 익숙해지는 게 최선 같아요 저는 미리 회전할 부분을 카피해놓고 사이즈별로 위, 아래, 오른쪽, 왼쪽을 각각 포문돌면서 밀어주는 방식으로 구현했씁니다. 처음에 회전할 부분만 그 크기만큼의 배열로 복사해놓고, 그부분을 또 계산해서 하는 방식으로 했는데요... 그냥 굳이 다른 크기의 배열에 힘들게 복사해서 계산하지 말고 원복 배열을 그대로 카피해..
-
백준 16637 괄호 추가하기Algorithm/BOJ 2021. 3. 29. 12:03
출처: www.acmicpc.net/problem/16637 분류: 완전탐색 접근방식 크게 두 부분을 이해하면 문제를 해결할 수 있습니다. 1. 괄호치기 2. 연산하기 0. 전처리 먼저 저는 괄호가 쳐질 연산자를 선택하는 방법을 이용할 것이기 때문에 전처리 작업에서 숫자와 연산자를 각각 배열에 분리해서 담아줬습니다. for char in readLine()! { if char.isNumber { numbers.append(Int(String(char))!) } else { operators.append(char) } } 1. 괄호치기 "괄호가 중복되지 않는다" , "괄호 안의 연산자는 1개" 라는 조건을 이용해서 해결했습니다. 위 조건을 생각해보면 괄호 안의 연산자는 오직 1개뿐이므로 연산자 중에서 괄호..
-
백준 17471 게리맨더링Algorithm/BOJ 2021. 3. 28. 21:02
출처: www.acmicpc.net/problem/17471 분류: 완전탐색 접근방식 n이 최대 10밖에 안 되기 때문에 완전탐색으로 해결할 수 있었습니다. 각 구역을 0, 1 중 하나가 되는 조합을 뽑아서 해당 조합이 조건을 만족하는지 확인하는 방식으로 해결했습니다. 풀이를 떠올리는 건 어렵지 않았는데 구현에서 꽤나 시간을 잡아먹었네요.. 때문에 하나씩 차근차근 살펴보면서 정리해보겠습니다. 먼저 각 구역의 인구, 인접 구역, 파티(정당), 최소 차이 를 담을 변수들이 필요했습니다. 구역의 최대 인구가 100이기 때문에 모든 구역의 인구가 100이여도 차이는 1000을 넘지 않습니다. 초기값은 그냥 여유롭게 10000으로 잡아줬습니다. var population: [Int] = [0] var adjace..
-
백준 17136 색종이 붙이기Algorithm/BOJ 2021. 3. 28. 19:14
출처: www.acmicpc.net/problem/17136 분류: 완전탐색 접근방식 가능한 색종이를 열심히 붙이면 되는 문제였습니다. 처음엔 크기가 5x5인 색종이부터 먼저 붙여나가는 방식으로 접근했는데 이렇게 되면 틀리더라구요.. 반례가 있나봅니다. 따라서 백트래킹으로 모든 경우를 찾아주는 방식으로 접근해야 합니다!! 그리고 이것도 단순히 크기가 1인 색종이부터 확인해나가면 모두 1인 칸일 경우에는 엄청난 연산이 필요하게됩니다. 크기 5부터 접근해서 찾고, 이미 찾은 최소 케이스보다 많이 사용하게되면 그 이상은 무의미하니 거기서 중단해주면 시간을 단축시킬 수 있습니다. 나머지는 단순 구현이라 코드를 보시면 어렵지않게 이해가 되실 것 같습니다 :) 해결방법 func solution() { typeali..
-
백준 10819 차이를 최대로Algorithm/BOJ 2021. 3. 16. 13:20
출처: www.acmicpc.net/problem/10819 분류: 완전탐색, 순열 접근방식 n이 최대 8밖에 되지 않아 가능한 배열 조합을 모두 구해서 주어진 식대로 계수의 최댓값을 계산했습니다. 주어진 예제에서는 [8, 15, 1, 20, 4, 10] 경우에 가장 큰 최댓값이 나오는데 어떤 경우에 최대가 나오는 특별한 규칙이 있는건지는 잘 모르겠습니다.. ㅠㅠ 순열을 오랜만에 해서 처음에는 배열을 만들어가고 해당 수를 넣었는지 체크하는 bool 배열을 만들고... 굉장히 비효율적으로 풀었었네요 ㅠㅠ 덕분에 오랜만에 순열을 다시 복습해볼 수 있어서 좋았네요 :) 전통적인 순열은 스왑을 통해 백트래킹 방식으로 구할 수 있습니다. 앞에서부터 해당 자리에 들어갈 수를 채워넣어가는 방식으로 바꿀 자리의 인덱스..
-
백준 1107 리모컨Algorithm/BOJ 2020. 7. 16. 11:56
출처: www.acmicpc.net/problem/1107 분류: 완전 탐색 접근방식 돌고돌아 결국 순수한 완전탐색으로 해결한 문제입니다. 고장난 숫자 버튼이 주어질 때 원하는 채널을 만들기 위해 필요한 조작 횟수를 구하는 문제입니다. 조정할 수 있는 채널 중에서 원하는 채널과 가장 가까운 채널로 가서 + 혹은 - 로 조작하면 최소의 수를 구할 수 있... 을줄 알았으나, 생각보다 간단한 문제는 아니었습니다. 가장 가까운 채널을 어떻게 만들 것인가, "처음엔 수어진 숫자의 각 자리 마다 위, 아래로 가까운 수를 뽑으면 가장 가까운 수가 되겠구나." 라고 생각하고 접근했습니다. 5000 2 5 0 이렇게 주어지면, 5 와 0을 피해 가장 가까운 각 자리 수를 up, down으로 만들면, 밑으로 가장 가까운..