전체 글

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

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, _ ..

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

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

문제 소개https://www.acmicpc.net/problem/2467 문제 풀이정렬이 되어있으니 투포인터 알고리즘으로 풀면 된다.import Foundation let n = Int(readLine()!)! var solutions = readLine()!.split(separator: " ").map { Int($0)! } var value = 2_000_000_000 var left = 0 var right = n-1 var answer = (solutions[0], solutions[n-1]) while left < right { let sum = solutions[left] + solutions[right] if abs(sum) < value { value = abs(sum) answer =..

문제 소개다각형의 면적을 구하는 문제이다.문제 풀이CCW 알고리즘이 문제는 CCW(Count Clockwise) 알고리즘을 사용했다. 단순히 정답만 궁금하다면 아래 정답코드를 참고하면 된다. 기하학이 나와서 문제가 골드인데 사실 공식만 안다면 단순한 구현문제이다. 솔직히 벡터의 외적을 사용하지 않고 이 문제를 쉽게 푸는 방법을 모르겠다...두 백터의 외적을 통해 벡터가 시계방향인지, 반시계방향인지 판별할 수 있는데, 아래의 코드로 CCW 를 구현할 수 있다.func ccw(_ A: Point, _ B: Point, _ C: Point) -> Int { return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) } 이 벡터의 외적을 2로 나눈 후 절댓값이..