백준
-
백준 1005 ACM CraftAlgorithm/BOJ 2021. 4. 19. 15:30
출처: www.acmicpc.net/problem/1005 분류: 위상정렬 접근방식 특정 순서가 있는 방향성 비순환 그래프(DAG)로 위상정렬의 개념으로 해결할 수 있는 문제였습니다. 위상정렬 개념 다시보기 다음 건물을 짓기 위해서는 그 전의 건물이 모두 다 지어져야 하므로 해당 건물을 짓기 위해 필요한 시간을 체크하는 배열을 하나 두고 연결을 끊으면서 가장 오래 걸리는 시간으로 업데이트를 해줍니다. for adj in adjacent[run] { adjCount[adj] -= 1 if totalTime[adj] < totalTime[run] + runTime[adj] { totalTime[adj] = totalTime[run] + runTime[adj] } if adjCount[adj] == 0 { r..
-
백준 1238 파티Algorithm/BOJ 2021. 4. 19. 14:00
출처: www.acmicpc.net/problem/1238 분류: 최단거리, 다익스트라 접근방식 단방향 그래프에서 목적지 X까지 갔다가 돌아오는 비용이 최대인 경우를 찾는 문제였습니다. 즉, (출발지 -> X)의 최단거리 + (X -> 출발지)의 최단거리를 구하는 게 목표였습니다. 저는 다익스트라 알고리즘으로 각 경우의 최단거리를 구해서 해결해줬습니다. 해결방법 import Foundation typealias Edge = (dest: Int, dist: Int) let nmx = readLine()!.split(separator: " ").map { Int(String($0))! } let (n, m, x) = (nmx[0], nmx[1], nmx[2]) var map = [[Edge]](repeati..
-
백준 16920 확장 게임Algorithm/BOJ 2021. 4. 9. 14:42
출처: www.acmicpc.net/problem/16920 분류: BFS 접근방식 문제 자체도 복잡하긴 한데 문제 설명이 좀 애매해서!!!!! 애를 좀 먹었던 문제였습니다. Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 문제를 보면 위와같이 써있는데요, 이렇게 되면 딱 Si 번째 칸만 칠하는 것(성으로 만드는 것)처럼 생각할 수 있는데 그게 아니라 Si번까지 이동하는 중에 있는 칸은 모두 칠해야 합니다. 반례는 예제 6번에 있는데요, 예제 6번을 살펴보면 처음 플레이어1 이 플레이 하고나면 ["1", "1", "1", "1"] ["1", "1", "1", "1"] [".", "1", "1", "."] ["1", ".", ".", "2"] 다음과 같이 되고 그 다음에 플레이어2 가 진행하고..
-
백준 2629 양팔저울Algorithm/BOJ 2021. 4. 8. 18:29
출처: www.acmicpc.net/problem/2629 분류: DP 접근방식 DFS 느낌으로 무게를 달 수 있는 경우들을 잘 세어야 하는 문제였습니다. 하나의 추를 놓고 3가지 경우를 생각해볼 수 있습니다. 1. 추를 추가하지 않았을 경우 2. 추를 구슬 반대쪽에 추가 ( weight + 추 ) 3. 추를 구슬 쪽에 추가 ( |weight - 추| ) 문제는 기저사례를 체크하는 부분이었는데, 단순히 무게만으로 확인했는지 체크하면 안 됩니다. 추를 몇 개를 사용했는지에 따라서 다음 무게들이 달라질 수 있기 때문에 몇 개의 추를 사용해 만든 무게인지 구분해줘야 합니다. 따라서 [현재 추][무게] 인 2차원 배열로 체크해줬네요! 추를 추가하지 않는 경우도 생각해줬기 때문에 마지막에 체크해줄 때는 추를 모두..
-
백준 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..
-
백준 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..