백준
-
백준 1715 카드 정렬하기Algorithm/BOJ 2021. 4. 7. 12:57
출처: www.acmicpc.net/problem/1715 분류: 우선순위 큐, 힙 접근방식 가장 최소인 값 두 개를 계속 더해가면 되는 문제입니다. 문제는 어떻게 최소 두 개를 찾을지가 관건이네요. 역시 최대, 최소 하면 제일 먼저 떠오르는 건 힙이겠죠? 힙으로 풀어봤습니다. Heap 에 대해 궁금하시다면 여기로 다른 분들 풀이를 보니 이분탐색으로 풀어도 아슬아슬하게 통과는 되는 것 같더라구요. 해결방법 public struct Heap { private var nodes = [T]() private var orderCriteria: (T, T) -> Bool public init(sort: @escaping (T, T) -> Bool) { // 최대 힙인지 최소 힙인지 기준을 잡는다. self.ord..
-
백준 11404 플로이드Algorithm/BOJ 2021. 4. 7. 11:59
출처: www.acmicpc.net/problem/11404 분류: 플로이드 와샬 접근방식 이름처럼 전형적인 플로이드 와샬 문제였습니다. 플로이드 와샬 알고리즘을 알면 쉽게 풀 수 있었던 문제였네요! 플로이드 와샬이 익숙하지 않으시다면 여기로 :] 해결방법 let n = Int(readLine()!)! var values = [[Int?]](repeating: [Int?](repeating: nil, count: n+1), count: n+1) for i in 1...n { values[i][i] = 0 } for _ in 0..
-
백준 13549 숨바꼭질 3Algorithm/BOJ 2021. 4. 7. 11:20
출처: www.acmicpc.net/problem/13549 분류: BFS, Deque 접근방식 현재 위치에서 이동할 수 있는 위치를 담으면서 BFS 탐색을 해서 해결할 수 있습니다. 단, 그냥 앞뒤 이동 보다 jump가 비용이 더 적게 들기 때문에 jump를 우선적으로 처리해줘야 합니다. 이때 사용할 수 있는 방법은 여러가지인 것 같은데요, 저는 jump는 queue의 앞에 추가하고 나머지는 뒤에 추가하는 방식으로 jump를 우선적으로 처리해줬습니다. 시간은 널널해서 그냥 배열로도 처리할 수 있는데, deque를 사용하면 효율을 훨씬 높일 수 있습니다. 해결방법 그냥 배열 let nk = readLine()!.split(separator: " ").map { Int(String($0))! } var v..
-
백준 1916 최소비용 구하기Algorithm/BOJ 2021. 4. 6. 22:11
출처: www.acmicpc.net/problem/1916 분류: 다익스트라 접근방식 전형적인 최단경로 문제였습니다. 다익스트라 알고리즘으로 해결할 수 있었습니다. 다익스트라 알고리즘을 알면 별도의 설명은 필요 없을듯 하네요. 다익스트라 포스팅을 한 번 해야겠습니다.. 해결방법 let n = Int(readLine()!)! var cities = [[(end: Int, value: Int)]](repeating: [], count: n+1) for _ in 0..
-
백준 17298 오큰수Algorithm/BOJ 2021. 4. 6. 18:20
출처: www.acmicpc.net/problem/17298 분류: 스택 접근방식 스택을 이용해서 풀 수 있었는데, 처음에 접근을 떠올리지 못해서 다른 분들의 풀이를 참고해서 겨우 풀었습니다. 아직 오큰수를 찾지 못한 수들을 스택에 담아줍니다. 현재 a[i]가 스택의 top 보다 크다면 top의 오큰수는 a[i]가 됩니다. 스택의 있는 수들은 아직 오큰수를 찾지 못한 수들이기 때문에 오른쪽에 있으면서 가장 큰 수가 바로 a[i] 입니다. 따라서 스택에는 오큰수를 찾지 못한 인덱스를 넣어주면서 a[i] 보다 크다면 빼서 해당 인덱스의 오큰수를 a[i]로 기록해주고, 다음으로 a[i]의 오큰수를 또 찾아야 하기 때문에 stack에 a[i]의 인덱스 i 를 넣어주고 넘어가줍니다. for i in 0..
-
백준 1450 냅색문제Algorithm/BOJ 2021. 4. 6. 14:48
출처: www.acmicpc.net/problem/1450 분류: 이분탐색 접근방식 n이 30으로 크기 때문에 그대로 부분합을 구하면 2^30 시간제한을 통과하기 어렵습니다. 따라서 반반 나눈 뒤 이분탐색으로 접근하는 방법으로 접근합니다. 부분합은 재귀적으로 구해줬습니다. func partition(_ idx: Int, _ to: Int, _ array: inout [Int], _ sum: Int) { guard sum Int { var low = 0 var high = sumB.count while low < high { let mid = (low + high)/2 if target < sumB[mid] { high = mid } else { low = mid+1 } } return low } 참고로 ..
-
백준 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..