boj
-
백준 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..
-
백준 2632 피자판매Algorithm/BOJ 2021. 4. 2. 13:14
출처: www.acmicpc.net/problem/2632 분류: 이분탐색 접근방식 이분탐색을 통해 해결해볼 수 있었습니다. 전체적인 풀이 과정은 다음과 같습니다. 1. 각 피자에서 가능한 피자 조각을 모두 구한다. (n == 1000 이므로 n^2 이면 충분합니다.) 2. 한쪽 피자에서 선택했을 경우 또는 하지 않을 경우 다른 쪽 피자의 값이 무엇이 되어야 할지 기대할 수 있기 때문에 이를 이분탐색으로 파악합니다. 가능한 피자 조각을 구할 때 주의해야 할 점은 피자 조각이 원형이라는 점입니다. 주어진 예제처럼 2 2 1 7 2 에서 피자 조각 경우를 구할 때, 원형으로 생각을 해줘야 합니다. 2 2 1 7 2 - 여기서 1부터 시작한다면 가능한 조합은 [1], [1, 7], [1, 7, 2], [1, ..
-
백준 1981 배열에서 이동Algorithm/BOJ 2021. 4. 1. 21:05
출처: www.acmicpc.net/problem/1981 분류: 이분탐색 접근방식 이 문제는 n이 최대 100으로 100 x 100 배열이기 때문에 단순 무식하게 BFS 접근하면 시간초과를 맞게 됩니다. 어떻게 하면 방문을 범위를 제한할 수 있을까요? 이 문제에서도 이분탐색의 아이디어를 적용해볼 수 있습니다. 우선 차이가 가장 작아지는 경우는 언제일까요? 경로의 최대최소가 같은 경우면 차이가 최소가 될 수 있겠죠? 때문에 최소는 언제나 가능성이 있으니 0으로 둡니다. 그럼 차이가 최대가 될 때는 언제일까요? 배열에 나오는 최대값과 최소값이 모두 들어있을 때, 즉 최대 - 최소가 차이의 최대가 되겠네요. 저희는 최소를 구해야 하기 때문에 만약 0 ~ 8 까지 가능성이 있을 때, 차이를 4로해서 가는 경우..
-
백준 3020 개똥벌레Algorithm/BOJ 2021. 3. 31. 11:36
출처: www.acmicpc.net/problem/3020 분류: 이분탐색 접근방식 이 문제는 가로 20 세로 50만이므로 모두 탐색한다거나 h만큼 일일이 배열에 담아준다거나 하는 방식으로는 시간초과를 면하기 어렵습니다. 저희가 원하는 건 특정 높이에서 만나는 장애물의 개수 입니다. 순서는 상관이 없죠! 따라서 이분탐색을 떠올려볼 수 있습니다. 대신 종유석과 석순이 서로 반대방향으로 나있기 때문에 이분탐색 upper/lower 바운드를 잘 섞어서 사용해줘야 하겠습니다. 이분탐색 upper/lower bounds가 익숙하지 않으시다면 여기를 읽어주세요 :] 조금 더 구체적으로 알아볼게요. 석순과 종류석의 높이를 따로 배열에 담고 정렬해줍니다. 저는 석순이 난 방향부터 높이를 1로 생각해서 계산해보려고 합니..
-
백준 1520 내리막 길Algorithm/BOJ 2021. 3. 30. 14:00
출처: www.acmicpc.net/problem/1520 분류: DP, DFS 접근방식 DFS 방식으로 원하는 칸에 도달하는 경로를 찾아나갈 수 있습니다. 대신 모든 경우를 탐색하면 시간제한에 걸리게 되므로 DP를 활용해야 합니다. 현재 칸에서 가능한 경우의 수는 이미 모두 탐색을 했기 때문에 방문한 칸을 다시 방문할 필요는 없고 저장된 방문 횟수만 가져옵니다. 구체적으로는 처음에 DP 배열에 -1을 넣어두고 방문하면 0으로 초기화하고 값을 더해줍니다. DP가 -1일 경우에만 탐색하고 아니면 DP의 값만 리턴합니다. 해결방법 typealias Point = (r: Int, c: Int) let rc = readLine()!.split(separator: " ").map { Int(String($0))!..
-
백준 12865 평범한 배낭Algorithm/BOJ 2021. 3. 30. 13:09
출처: www.acmicpc.net/problem/12865 분류: DP 접근방식 디피로 해결할 수 있는 문제였습니다. 디피는 상황에 따른 최대 값을 기록해놓고 더 최적인 경우를 비교하면서 업데이트 해나가는 메모제이션 방식입니다. 이 문제에서는 특정 무게에 최대 가치가 얼마인지 기록해놓으면 되겠네요. 테이블에는 현재까지 찾은 최적의 가치가 들어있다고 할 때, 현재 무게 4짜리의 물품으로 테이블의 무게 7 칸을 채우려고 한다면 최적은 테이블의 무게 3짜리 칸 가치 + 현재 물품의 가치 (무게 4) vs 테이블의 무게 7짜리 칸의 가치 로 생각해볼 수 있습니다. 이런식으로 물품들을 입력받을 때마다 테이블을 업데이트 해나가면됩니다. 물품마다 현재 무게부터 테이블의 끝까지를 업데이트를 해나가야 하는데 테이블을 ..
-
백준 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 의 순열을 뽑아주고 주어진 대로 잘 구현하면 되는 문제였습니다. 아직 순열이 익숙하지 않으시다면 여기로 :) 완전탐색의 문제는 늘 그렇죠. 알겠는데 어케 구현하냐....... 머리가 안 돌아가서 배열 돌리는 데 한참이 걸렸습니다 😭 이건 뭐 다른 방법보다 직접 해보면서 익숙해지는 게 최선 같아요 저는 미리 회전할 부분을 카피해놓고 사이즈별로 위, 아래, 오른쪽, 왼쪽을 각각 포문돌면서 밀어주는 방식으로 구현했씁니다. 처음에 회전할 부분만 그 크기만큼의 배열로 복사해놓고, 그부분을 또 계산해서 하는 방식으로 했는데요... 그냥 굳이 다른 크기의 배열에 힘들게 복사해서 계산하지 말고 원복 배열을 그대로 카피해..