분류 전체보기
-
백준 1202 보석 도둑Algorithm/BOJ 2021. 4. 7. 13:56
출처: www.acmicpc.net/problem/1202 분류: 우선순위 큐, 그리디 접근방식 진짜 어마무시하게 틀렸던 문제입니다... 보석과 가방을 모두 오름차순으로 정렬해두고 가방에 담을 수 있는 보석들을 우선순위 큐에 담아서 가장 비싼 보석을 넣어주면 되는 문제였습니다. 핵심이 되는 코드 부분만 보시면 이해하실 수 있을거에요 :) var jamIdx = 0 for back in backs { while jamIdx Bool) { // 최대 힙인지 최소 힙인지 기준을 잡는다. self.orderCriteria = sort } public init(array: [T], so..
-
백준 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..
-
RingBufferAlgorithm/Theory 2021. 4. 7. 10:48
안녕하세요! deque 관련된 문제를 풀다가 간만에 자료구조를 하나 정리해볼까 합니다. 아시다시피 array에서는 뒤에 추가하거나 빼는 작업은 O(1) 이지만, 앞 또는 중간에 추가하거나 빼는 작업은 O(n)의 시간 복잡도가 소요됩니다. 배열의 크기는 고정되어 있기 때문에 앞이나 중간에 작업을 하려면 그 뒤의 나머지 원소들을 모두 옮겨주는 작업이 필요하기 때문이에요. 그럼 원소들을 옮기지 않고 인덱스만 조절하면 되지 않을까? 하는 데서 시작된 아이디어가 RingBuffer가 아닐까 싶어요. RingBuffer는 read / write 포인터를 둬서 배열의 원소들을 움직이지 않고 인덱스만 조절해 덮어쓰는 방식을 사용합니다. 예시를 보면서 살펴볼게요. 처음엔 Read, Write 모두 0번째 인덱스에서 출발..
-
백준 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 } 참고로 ..