Algorithm/BOJ
-
백준 1806 부분합Algorithm/BOJ 2021. 1. 22. 11:43
출처: https://www.acmicpc.net/problem/1806 분류: 투포인터 접근방식 앞선 투포인터 문제와 거의 비슷했습니다. 이 문제도 전형적인 투포인터 방식으로 풀었습니다 :) 해결방법 protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()! } func readSingleValue() -> Int { return Int(readLine()!)! } func readArray(with separator: Character..
-
백준 1967 트리의 지름Algorithm/BOJ 2021. 1. 21. 15:14
출처: https://www.acmicpc.net/problem/1967 분류: 트리 접근방식 문제의 서두에 트리는 무방향 그래프라고 알려주면서 힌트를 주고 있습니다. root가 있지만 방향성이 없기 때문에 트리를 돌려서 생각해보면 leaf 노드를 root로 한 트리의 형태를 생각해볼 수 있습니다. root를 포함한 끝 노드에서 다른 끝 노드로 가는 경로가 이 트리의 지름이 됩니다 :) 해결방법 dfs를 돌려서 루트에서 가장 먼 노드를 찾고, 그 노드를 루트로 다시 dfs를 돌려서 가장 먼 지름는 방식으로 해결했습니다. 그 노드의 인접 노드들을 배열로 하는 이중 배열을 만들어서 해결했습니다. 트리가 익숙하지 않아서 이 자료구조를 만드는 데 꽤나 시간이 걸렸네요... 이게 최선인지도 모르겠습니다. 😢 im..
-
백준 11725 트리의 부모 찾기Algorithm/BOJ 2021. 1. 14. 16:44
출처: https://www.acmicpc.net/problem/11725 분류: 트리, 그래프 탐색 접근방식 우선 주어진 대로 트리를 모두 연결하고 루트 노드부터 부모를 연결해나가면 되는 문제입니다! 연결된 노드를 우선 connects에 담아두고 부모가 결정되면 connects에서는 지워주는 방식으로 구현했어요! 처음엔 연결 할 때마다 체크하려고 했는데 다 연결하고 수정해나가는 건 쉬운데, 이건 만만치 않더라구요.. 해결방법 import Foundation protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func read..
-
백준 1991 트리 순회Algorithm/BOJ 2021. 1. 13. 18:35
출처: https://www.acmicpc.net/problem/1991 분류: 트리, 재귀 접근방식 기본적인 이진 트리 순회 문제입니다. 트리를 순회하는 방법은 대표적으로 preorder / inorder / postorder 방법이 있는데요, 이는 현재 노드를 언제 방문할건지가 기준이 됩니다. preorder 현재 노드를 먼저 방문하겠다는 뜻입니다. inorder 현재 노드를 중간에 방문하겠다는 뜻입니다. postorder 현재 노드를 나중에 방문하겠다는 뜻입니다. 이 문제는 이진 트리이므로 왼쪽, 오른쪽을 재귀적으로 순회해주면서 언제 방문할지(print or 별도의 체크)만 결정해주면 됩니다. 해결방법 class Graph { var nodes = [T: Node]() class Node { var..
-
백준 1976 여행가자Algorithm/BOJ 2021. 1. 12. 13:56
출처: https://www.acmicpc.net/problem/1976 분류: 자료구조, 분리 집합 접근방식 서로소 집합 문제였습니다. https://woongsios.tistory.com/200 와 같은 방식으로 해결했습니다. 연결되어 있는지만 확인하면 되기 때문에 같은 집합은 하나의 root로 바꿔주고 root가 같은지만 확인하면 되는 문제였습니다! 해결방법 import Foundation let n = Int(readLine()!)! let m = Int(readLine()!)! var cities = [Int](0.. Int { guard cities[n] != n else { return n } cities[n] = root(of: cities[n]) return cities[n] } func..
-
백준 1717 집합의 표현Algorithm/BOJ 2021. 1. 12. 12:44
출처: https://www.acmicpc.net/problem/1717 분류: 자료구조 접근방식 몰랐는데 disjoint-set(서로소 집합) 문제라고 하네요. 집합이 합쳐지는 걸 어떤 집합에 속하게 된다는 개념으로 접근하면 쉽게 해결할 수 있는 문제였습니다. 배열에는 부모를 저장하고 있고 재귀적으로 최상위 부모를 찾아서 비교하고, 합칠 때도 역시 최상위 부모로 합쳐주면 됩니다 :) 처음엔 문제 그대로 집합을 합쳐주고 원소들을 합쳐진 집합으로 다 바꿔주는 식으로.... 1차원적으로 풀었는데 당연히 시간초과였습니다 흡 * a와 b를 확인하기 전에 같은 경우를 걸러주면 시간을 많이 줄일 수 있습니다 :) 해결방법 import Foundation let input = readLine()!.split(sepa..
-
백준 1927, 11279 최소 최대 힙Algorithm/BOJ 2021. 1. 11. 10:49
출처: https://www.acmicpc.net/problem/1927 , https://www.acmicpc.net/problem/11279 분류: 자료구조, 힙 접근방식 최대 or 최소를 최상위에 두는 heap 을 사용하는 문제였습니다. 복습하는 느낌으로 필요한 부분만 직접 구현해봤습니다 :) 해결방법 heap 을 생성할 때 기준을 정해줘서 최대, 최소 힙을 만들 수 있습니다. heap(by: Bool init(by criteria: @escaping (T, T) -> Bool) { self.criteria = criteria } mutating func insert(_ value: T) { nodes.append(value) shiftUp(from: nodes.count-1) } mutating ..
-
백준 3190 뱀Algorithm/BOJ 2021. 1. 9. 13:10
출처: https://www.acmicpc.net/problem/3190 분류: 자료구조 접근방식 특별한 알고리즘이나 수학적 개념보다 주어진 상황에 충실히 구현하면 되는 문제였습니다. 2차원 배열 맵을 만들어두고 체크해도 되겠으나(많이들 그런 식으로 푸신 것 같더라구요) 저는 굳이 배열을 따로 만들진 않고 범위만 체크했습니다. 해결방법 뱀을 링크드리스트 형태로 구현해줬고 body set을 정의해서 자기 자신으로 가려고 하는지 확인했습니다. enum, class 등등으로 정의해서 좀 느리고 길게 풀어진 것 같긴 하지만 그래도 나름 swift스럽게(?) 푼 것 같기는 합니다. 사과를 찾았으면 해당 사과를 지워줘야 하는데 이걸 빼먹어서 시간을 좀 잡아먹었네요 ;; 혹시나 저처럼 실수하시는 분들이 없기를 ㅠㅠ ..