algorithm
-
백준 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 의 순열을 뽑아주고 주어진 대로 잘 구현하면 되는 문제였습니다. 아직 순열이 익숙하지 않으시다면 여기로 :) 완전탐색의 문제는 늘 그렇죠. 알겠는데 어케 구현하냐....... 머리가 안 돌아가서 배열 돌리는 데 한참이 걸렸습니다 😭 이건 뭐 다른 방법보다 직접 해보면서 익숙해지는 게 최선 같아요 저는 미리 회전할 부분을 카피해놓고 사이즈별로 위, 아래, 오른쪽, 왼쪽을 각각 포문돌면서 밀어주는 방식으로 구현했씁니다. 처음에 회전할 부분만 그 크기만큼의 배열로 복사해놓고, 그부분을 또 계산해서 하는 방식으로 했는데요... 그냥 굳이 다른 크기의 배열에 힘들게 복사해서 계산하지 말고 원복 배열을 그대로 카피해..
-
백준 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..
-
백준 1038 감소하는 수Algorithm/BOJ 2021. 3. 28. 16:47
출처: www.acmicpc.net/problem/1038 분류: 완전탐색 접근방식 n번째 감소하는 수를 찾는 문제였습니다. 한 자리 수는 모두 감소하는 수이며, 작은 수부터 찾아줘야 합니다. 감소하는 수는 이런 식으로 진행됩니다. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43, 50, ... ] 규칙을 생각해보면 마지막 수는 마지막 앞자리 수보다 작아야 하니 앞자리 수가 4라면 마지막에 올 수 있는 수는 0, 1, 2, 3 이 됩니다. 그리고 마지막 자리를 제외한 수도 무조건 감소하는 수가 되어야 합니다. 감소하는 수 54 다음에 540, 541, 542, 543 이 올 수 있지만 44는 감소하는 수가 아니기 때문에 440,..