분류 전체보기

· → Problems
문제 소개 문제 풀이위상정렬을 활용하였다. Kahn 알고리즘과 DFS를 활용한 위상정렬이 있다.Kahn 알고리즘Kahn 알고리즘은 진입차수를 계산하면서 진입차수가 0인 것을 queue에 차례로 넣는다. 진입차수라고 하면 아래와 같이 들어오는 화살표의 갯수이다.DFS 알고리즘dfs 탐색을 거꾸로 하면 위상정렬이 된다. dfs 탐색을 하는데 dfs 를 한 뒤 마지막 정점을 stack에 저장해둔뒤 마지막 요소부터 꺼내면 그것이 위상정렬이 되는 것이다.여기서 6 5 3 4 2 1 을 거꾸로 한 1 2 4 3 5 6 이 위상정렬을 한 결과가 된다. 문제 풀이 코드Kahn 알고리즘 활용import Foundation let nm = readLine()!.split(separator: " ").map { Int($0..
· → Problems
문제 소개자연수 N 이 주어지면 N 보다 작은 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제. 문제 풀이소수는 에라토스테네스의 체를 통해서 구했고, 연속된 소수의 합은 투포인터 알고리즘을 사용하였다.import Foundation let n = Int(readLine()!)! // 입력값이 1일경우 빠른 처리 if n == 1 { print(0) exit(0) } // 에라토스테네스의 체 var isPrimeNumber = Array(repeating: true, count: n+1) var primeNumber = [Int]() let sqrtN = Int(sqrt(Double(n))) for i in 2..
· → Problems
문제 소개https://www.acmicpc.net/problem/1806문제 풀이투포인터 알고리즘을 활용하였다. 가장짧은 배열을 구하는 것이므로 최댓값은 최대로 나올 수 있는 값보다 1 높은 100,001 로 두고 투포인터를 활용해 조건을 만족하는 배열의 크기의 최솟값을 업데이트 했다.import Foundation let ns = readLine()!.split(separator: " ").map { Int($0)! } let (n, s) = (ns[0], ns[1]) var nums = readLine()!.split(separator: " ").map { Int($0)! } var (low, high) = (0, 0) var sum = nums[0] var ans = 100_001 while hi..
· → Problems
문제 소개링크: https://www.acmicpc.net/problem/1005나에게 Swift 로 알고리즘을 푸는 것에 대한 깊은 고통...을 안겨준 문제이다... 이유는 문제 푸는 방법은 맞았지만... Swift 에서 입력량이 많은 경우 시간초과가 빈번하게 발생하기 때문에 최대한 방법을 찾았으나 결국 파일입력 코드를 사용해버렸다...! 문제 풀이파일 입출력라이노님의 클래스를 사용했다. (감사합니다) ps할 때 입력을 한꺼번에 받기 위한 유틸리티 클래스. fread의 swift 버전.ps할 때 입력을 한꺼번에 받기 위한 유틸리티 클래스. fread의 swift 버전. GitHub Gist: instantly share code, notes, and snippets.gist.github.comfinal..
· → Problems
문제 소개보자마자 최소 신장 트리 (MST, Minimum Spanning Tree) 문제구나! 왜냐하면 최소경로로 마을을 잇는 방법을 구하는 것이기 때문이다. 문제 풀이Union find 알고리즘을 사용하여 최소 신장 트리를 만들었다. 그리고 마을을 두개로 나눈다고 했으니 최소 신장 트리에서 가장 긴 경로를 끊었다. 아래의 포스팅에 Union-Find 알고리즘을 활용하였다. [Algorithm] Union-Find 알고리즘 (Swift)Union-Find 알고리즘 이란?서로소 집합(Disjoint Set)을 효율적으로 관리하는 알고리즘이다. 아래의 두 그래프는 서로소인 집합이라고 볼 수 있다. 아래의 그래프가 주어진다면 1과 6은 같은 그룹에 속swift-library.tistory.com import..
Union-Find 알고리즘 이란?서로소 집합(Disjoint Set)을 효율적으로 관리하는 알고리즘이다. 아래의 두 그래프는 서로소인 집합이라고 볼 수 있다. 아래의 그래프가 주어진다면 1과 6은 같은 그룹에 속해있는지 판별할 수 있는지, 어떻게 주어진 자료로 아래의 그룹을 만들지 결정하는 알고리즘이다.알고리즘 구현하기Find재귀함수를 활용하여 부모를 찾는다. 4의 경우에는 2를 타고 가서 1이 root 로 나오게 된다. func find(_ n: Int) -> Int { if roots[n] == n { return n } return find(roots[n])} Union아래의 노드들을 그래프로 묶는 roots 배열을 만드는 것이 union 이다.func union(_ a: Int, _ ..
· → Problems
문제 소개 문제 풀이최소 신장 트리 (Minimum Spanning Tree)그래프 상에서 모든 노드가 사이클 없이 연결되어 있고, 정점이 최소 간선의 합으로 연결된 부분 그래프이다.이런 최소 신장 트리는 도로 건설 문제, 네트워크 라우팅 경로, 통신에서 전화선 길이에 사용되는 등 실제 자주 활용되는 자료구조라고 한다. 위 문제는 주어진 간선의 정보를 가지고 최소 신장 트리를 구하는 문제였다. 크루스칼 알고리즘최소 신장 트리를 찾는 알고리즘에 크루스칼 알고리즘이 있다. 주어진 간선을 오름차순 정렬 후 간선을 하나씩 확인하며 간선간 사이클이 발생하지 않을 경우 최소신장트리에 포함시키는 방법이다. 사이클 발생 여부는 union find 알고리즘을 활용한다.import Foundation let ve = re..
· → Problems
문제 소개https://www.acmicpc.net/problem/27172약수면 +1 나누어 떨어졌다면 -1 점을 갖게 되는 게임에서 결과를 출력하는 문제이다.문제 풀이이중 for 문으로 풀게 된다면 시간초과가 나게 된다. 따라서 다른 방법으로 풀어야 했다. 우선 길이가 1000001 인 nums 배열을 만들고, 어떠한 수가 등장했는지를 판별한다. 그리고 주어진 숫자의 배수를 판별하여 등장했다면 주어진 숫자에 +1 을 해주고 배수의 숫자에는 -1 을 해주면 된다.import Foundation let n = Int(readLine()!)! let input = readLine()!.split(separator: " ").map { Int($0)! } var nums = Array(repeating: f..
Swift librarian
'분류 전체보기' 카테고리의 글 목록 (5 Page)