algorithm
-
백준 11000 강의실 배정Algorithm/BOJ 2021. 4. 8. 15:57
출처: www.acmicpc.net/problem/11000 분류: priority queue, greedy 접근방식 문제를 똑바로 안 읽어서 좀 헤맸던 문제입니다.. 문제를 잘 이해해야 하는데요, 강의실에 수업을 배정하는 것이 아니라, 강의를 소화할 수 있게 강의실을 몇 개나 만들어야 하는지 찾는 문제입니다. 따라서 수업을 시작시간을 기준으로 정렬해두고, 생성된 강의실들 중에서 가장 빨리 끝나는 강의실과 수업의 시작시간을 비교해서 시작이 가능하다면 그 강의실에 배정합니다. 우선순위 큐에서 하나 꺼내고 해당 강의실을 집어넣으면 같은 의미가 됩니다! 이렇게 진행하고 결과적으로 우선순위 큐에 남아있는 원소의 개수가 강의실의 개수가 됩니다. 간단하게만 대략적인 그림으로 살펴보면, 아래 그림과 같이 강의실 3개..
-
백준 2042 구간 합 구하기Algorithm/BOJ 2021. 4. 8. 13:50
출처: www.acmicpc.net/problem/2042 분류: 세그먼트 트리, 구간 합 접근방식 세그먼트 트리의 예제 같은 문제입니다. 세그먼트 트리를 공부했다면 쉽게 풀 수 있었습니다. 세그먼트 트리가 궁금하시다면 여기로 :) 해결방법 class SegmentTree { var value: T var function: (T, T) -> T var leftBounds: Int var rightBounds: Int var leftChild: SegmentTree? var rightChild: SegmentTree? init(array: [T], leftBounds: Int, rightBounds: Int, function: @escaping (T, T) -> T) { self.leftBounds = l..
-
SegmentTreeAlgorithm/Theory 2021. 4. 8. 13:47
구간별로 특정한 결과 값을 관리할 때 사용하는 자료구조. 이진트리로 재귀적 구현이 특징. - query (특정 구간의 결과) O(logN) - replace (특정 인덱스 교체) O(logN) 안녕하세요 :) 오늘은 SegementTree에 대해 알아보려고 합니다. 먼저 SegemetTree 는 언제, 왜 사용할까요? SegemtTree 라는 이름이 나타내듯이 구간별로 특정한 결과값을 관리하고 싶을 때 사용하는 자료구조 입니다. 주로 구간 합을 구할 때 많이 사용하죠! 세그먼트 트리는 이진트리로 leaf 노드가 해당 인덱스의 값을 가지고 있습니다. 아래 그림처럼 전체 구간부터 반씩 잘라서 구간을 나눠 놓은 자료구조에요! 세그먼트 트리의 핵심은 재귀적 반복에 있습니다. 생각보다 어렵지 않아요 :) Sege..
-
백준 16234 인구 이동Algorithm/BOJ 2021. 4. 8. 11:46
출처: www.acmicpc.net/problem/16234 분류: BFS, DFS 접근방식 BFS 또는 DFS로 해결할 수 있는 문제였습니다. 주어진 범위에 해당하는 칸들을 탐색하고 그룹짓고를 반복하면 됩니다. 저는 BFS를 사용했는데요, 탐색하면서 멤버들의 따로 저장해뒀다가 탐색이 끝나기 전에 tempMap에 결과를 기록해두고 전체를 다 돌고 temp와 map을 비교해서 다시 해야할지 말지를 결정해주면서 카운트했습니다. 해결방법 struct Point { var r: Int var c: Int init(_ r: Int, _ c: Int) { self.r = r self.c = c } var nexts: [Point] { return [ Point(r+1, c), Point(r-1, c), Point(..
-
백준 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..