전체 글
-
백준 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..
-
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(..