brute force
-
백준 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..
-
백준 2210 숫자판 점프Algorithm/BOJ 2021. 3. 29. 14:34
출처: www.acmicpc.net/problem/2210 분류: dfs, 완전탐색 접근방식 왔던 칸을 다시 가도 되므로 그냥 보드의 범위를 넘지 않는지만 체크하면서 6자리까지 dfs 로 계속 숫자를 더해주고 set에 담아서 개수를 출력하면 되는 문제였습니다. 저는 다음 칸을 만들고 filter로 범위를 걸러주는 식으로 풀어서 먼저 범위를 체크하고 만드는 것보다 시간이 좀 더 걸린 것 같네요! 해결방법 typealias Point = (r: Int, c: Int) var board = [[String]]() var digitSet = Set() for _ in 0.. [Point] { return [ (p.r+1, p.c), (p.r-1, p.c), (p.r, p.c+1), (p.r, p.c-1) ].f..
-
백준 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..
-
백준 13460 구슬 탈출 2Algorithm/BOJ 2020. 7. 24. 13:32
출처: www.acmicpc.net/problem/13460 분류: 완전 탐색 접근방식 상하좌우로 회전시킬 수 있는 보드판 위에 빨강, 파랑 구슬, 빠져나갈 구멍이 있을 때 움직여서 빨간 구슬만 구멍에 넣어야 할 때 최소 횟수를 찾는 문제입니다. 단, 횟수가 10번을 초과하면 안됩니다. 판의 크기가 3 ~ 10 까지로 매우 작고 10번이라는 제한이 있기 때문에 모든 경우를 다 탐색해서 말그대로 완전 탐색으로 해결할 수 있습니다. 개인적으로 구현이 꽤나 까다로웠던 문제였습니다. 상하좌우로 다 해본다는 게 말은 쉽지만 생각보다 까다로웠습니다. 두 구슬은 겹칠 수 없기 때문에 다른 구슬이 앞에 있다면 그 구슬 뒤까지 움직여야 하고 말이죠... 구현 아이디어는 다음과 같습니다. 빨간 구슬과 파란 구슬은 계속 굴..