→ Problems

문제 소개정말 정말 간단한 문제라서 10분도 안 걸릴 줄 알았지만 생각보다 시간을 쓴 문제... 너무 어려운 거에만 집중하지 말고 이런 단순한 문제에도 집중해야 한다는 것을 깨달았다. 문제 풀이정답 코드는 아래와 같이 단순하다.while let n = readLine(), let div = Int(n) { var num = 1, count = 1 while num % div != 0 { num = (num * 10 + 1) % div count += 1 } print(count) } 입력값여러개의 테스트 케이스로 이루어져 있기 때문에 while을 통해서 readLine()을 사용해 입력값을 계속 받도록 해야 했다.while let n = readLine(), let div = Int(n) { ... } ..

문제 소개주사위를 어떻게 굴릴것인지가 관건.문제 풀이이렇게 주사위가 동서남북으로 굴러간것을 표시하면 이렇게 된다. [위, 북, 동, 서, 남, 아래] 순으로 표시하면 위처럼 나타낼 수 있다. 나머지는 구현문제이다.import Foundation let nmxyk = readLine()!.components(separatedBy: " ").map { Int($0)! } let (n, m, x, y, k) = (nmxyk[0], nmxyk[1], nmxyk[2], nmxyk[3], nmxyk[4]) var map = Array(repeating: [Int](), count: n) for i in 0..

문제 소개 문제 풀이위상정렬을 활용하였다. 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..

문제 소개자연수 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..

문제 소개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..

문제 소개링크: 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..

문제 소개보자마자 최소 신장 트리 (MST, Minimum Spanning Tree) 문제구나! 왜냐하면 최소경로로 마을을 잇는 방법을 구하는 것이기 때문이다. 문제 풀이Union find 알고리즘을 사용하여 최소 신장 트리를 만들었다. 그리고 마을을 두개로 나눈다고 했으니 최소 신장 트리에서 가장 긴 경로를 끊었다. 아래의 포스팅에 Union-Find 알고리즘을 활용하였다. [Algorithm] Union-Find 알고리즘 (Swift)Union-Find 알고리즘 이란?서로소 집합(Disjoint Set)을 효율적으로 관리하는 알고리즘이다. 아래의 두 그래프는 서로소인 집합이라고 볼 수 있다. 아래의 그래프가 주어진다면 1과 6은 같은 그룹에 속swift-library.tistory.com import..

문제 소개 문제 풀이최소 신장 트리 (Minimum Spanning Tree)그래프 상에서 모든 노드가 사이클 없이 연결되어 있고, 정점이 최소 간선의 합으로 연결된 부분 그래프이다.이런 최소 신장 트리는 도로 건설 문제, 네트워크 라우팅 경로, 통신에서 전화선 길이에 사용되는 등 실제 자주 활용되는 자료구조라고 한다. 위 문제는 주어진 간선의 정보를 가지고 최소 신장 트리를 구하는 문제였다. 크루스칼 알고리즘최소 신장 트리를 찾는 알고리즘에 크루스칼 알고리즘이 있다. 주어진 간선을 오름차순 정렬 후 간선을 하나씩 확인하며 간선간 사이클이 발생하지 않을 경우 최소신장트리에 포함시키는 방법이다. 사이클 발생 여부는 union find 알고리즘을 활용한다.import Foundation let ve = re..