Swift
-
백준 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..
-
백준 2003 수들의 합2카테고리 없음 2021. 1. 22. 10:53
출처: https://www.acmicpc.net/problem/2003 분류: 두 포인터 접근방식 수열의 특정 구간의 합이 특정한 수가 되는 경우의 수를 구하는, 대표적인 투 포인터 문제입니다. 2개의 포인터를 둬서 하나는 합이 원하는 수보다 크거나 같으면, 다른 하나는 합이 원하는 수보다 작으면 움직여주면서 합을 계산해주면 됩니다:) 해결방법 protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()! } func readSingleVa..
-
백준 1967 트리의 지름Algorithm/BOJ 2021. 1. 21. 15:14
출처: https://www.acmicpc.net/problem/1967 분류: 트리 접근방식 문제의 서두에 트리는 무방향 그래프라고 알려주면서 힌트를 주고 있습니다. root가 있지만 방향성이 없기 때문에 트리를 돌려서 생각해보면 leaf 노드를 root로 한 트리의 형태를 생각해볼 수 있습니다. root를 포함한 끝 노드에서 다른 끝 노드로 가는 경로가 이 트리의 지름이 됩니다 :) 해결방법 dfs를 돌려서 루트에서 가장 먼 노드를 찾고, 그 노드를 루트로 다시 dfs를 돌려서 가장 먼 지름는 방식으로 해결했습니다. 그 노드의 인접 노드들을 배열로 하는 이중 배열을 만들어서 해결했습니다. 트리가 익숙하지 않아서 이 자료구조를 만드는 데 꽤나 시간이 걸렸네요... 이게 최선인지도 모르겠습니다. 😢 im..
-
TreeComputer Science/DataStructure 2021. 1. 14. 18:00
- 객체간의 계층적인 관계를 나타낸다 - 빠르고 효율적으로 탐색할 수 있다 - 데이터의 정렬된 형태를 보여준다 - 사이클이 없는 그래프 - 텍스트의 prefix 매칭을 빠르게 할 수 있다. ex) - 회사나 정부의 조직 구조 - 나라, 지방, 시•군별 등 계층적인 데이터 - 인덱스 오늘은 기본적이지만 아주 중요한 Tree에 대해 알아보겠습니다. Tree 자체보다도 여기서 파생된 트리들이 더 중요하지만 그래도 기본부터 정리해보려고 해요 :) 자료구조란 데이터들을 잘 관리하게 생겨났을텐데요, 트리는 왜, 언제 필요할까요? 트리는 계층적인 관계를 나타내기 위해 사용합니다. 계층 관계는 우리 일상 생활과 아주 많이 밀접해있습니다. 먼저 우리 가족의 관계도를 그려본다고 생각해봅시다. 부모님 형제 자매가 있고, 다..
-
백준 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..