algorithm
-
백준 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스럽게(?) 푼 것 같기는 합니다. 사과를 찾았으면 해당 사과를 지워줘야 하는데 이걸 빼먹어서 시간을 좀 잡아먹었네요 ;; 혹시나 저처럼 실수하시는 분들이 없기를 ㅠㅠ ..
-
선택문제 Quick SelectAlgorithm/Theory 2021. 1. 7. 15:44
- 선택문제: n개의 값 중에서 k번째로 크거나 작은 수를 찾는 문제 - Quick Select: pivot과 작은 값, 같은 값, 큰 값으로 나누어서 찾고자 하는 수가 어디에 속해있는지 찾아나가는 방법 1. pivot 고르기 2. 3부분으로 나누기 ( n-1번 수행 ) S = { P보다 작은 값 } L = { P보다 큰 값 } M = { P와 같은 값 } 3. k가 어디에 속해 있는지 찾기 |S| : 배열 S의 개수, (S에 속함) if |S| >= k { return 재귀(S, k) } (L에 속함) else if |S| + |M| < k { return 재귀(L, k - |S| - |M| } (M에 속함) else { return P } - 시간복잡도 최선의 경우 O(n), 최악의 경우 O(n^2)..
-
Programmers Lv4) [2020 카카오블라인드] 가사검색Algorithm/Programmers 2020. 8. 30. 11:57
출처: programmers.co.kr/learn/courses/30/lessons/60060 분류: Kakao Blind 2020, Lv4, Trie 접근방식 효율성 문제였습니다. 대부분 정확성까지는 어렵지 않게 푸셨을 것 같은데요, 효율성에서 상당히 애를 먹었습니다 ㅠㅠ 문자열을 얼마나 효율적으로 관리하고 탐색할 수 있을지가 키포인트였던 것 같습니다 :) 카카오 단골이죠 문자열 ... 😇 문제설명 가사검색은 주어진 words가 있을 때 query에 만족하는 단어가 몇 개인지 찾는 문제였습니다. 쿼리는 ?를 포함하고 있는데요, ?는 한 글자를 의미하며 어떤 글자가 와도 괜찮습니다. 예를 들어 다음과 같다면, words = ["frodo", "front", "frost", "frozen", "frame"..