분류 전체보기

문제 소개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로 나눈 후 절댓값이..

문제 소개문제 풀이bfs 를 두번 활용하여 구했다. 물이 퍼지는 것을 moveWater() 로 구현했고, 고슴도치가 움직이는 것도 bfs 를 활용하여 구현했다.import Foundation let rc = readLine()!.split(separator: " ").map { Int($0)! } let (r, c) = (rc[0], rc[1]) let ds = [(1, 0), (0, 1), (-1, 0), (0, -1)] var map = [[String]]() var queue: [(Int, Int, Int)] = [] var idx = 0 var widx = 0 var water: [(Int, Int, Int)] = [] var cave = (-1, -1) for i in 0.. time { bre..

문제 소개벽이 움직이는 미로를 탈출하는 문제이다.문제 풀이벽이 아래로 움직이기 때문에 i 와 j 를 바꿔서 배열에 넣어주고 round 마다 +1 을 해주어 갈 수 있는지 없는지를 판별했다.import Foundation let moves = [(1, -1), (1, 0), (0, -1), (0, 0), (-1, 0), (0, 1), (-1, -1), (-1, 1), (1, 1)] var walls = Array(repeating: [Int](), count: 8) for i in 0.. idx { let popped = queue[idx] idx += 1 if popped.0 == 0 && popped.1 == 7 { print(1) exit(0) } if visit.count == popped.2 { ..

Swift에서 스택과 큐Swift로 프로그래밍을 하다 보면 자료구조를 구현해줘야 하는 것들이 있다. 그중 하나가 큐이다. 스택의 경우 removeLast() 와 append(_:) 의 경우 complexity 가 O(1) 이기 때문에 배열에서 위와 같은 함수를 사용하여 그대로 구현할 수 있다.따라서 스택은 구현이랄 것도 없다. 원래 있는 메서드를 개념에 맞게 사용하면 그것이 스택 자료구조이다.var stack: [Int] = [1, 2, 3, 4, 5]stack.append(6)print(stack.removeLast()) // 6print(stack) // [1, 2, 3, 4, 5] 하지만 큐의 경우 FIFO 이기 때문에 removeFirst() 메소드를 사용해야 하는데 문제는 complexity 가..

문제 소개벽 부수기 시리즈! 이번에는 낮에만 블록을 깰 수 있다는 제약조건이 있다.문제 풀이시간 초과와 메모리 초과 때문에 좀 고생을 한 것 같다.시간 초과시간 초과의 경우 의외로 벽을 부시는 경우를 앞쪽에 둬서 해결이 되었다.메모리 초과최대한 요소를 늘리지 않으려고 했다. cost를 2로 나눈 나머지로 낮과 밤을 판별하니 메모리 초과가 나지 않았다. 큐를 구현하지 않고 풀이import Foundation let nmk = readLine()!.split(separator: " ").map { Int($0)! } let (n, m, k) = (nmk[0], nmk[1], nmk[2]) let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)] var..

문제 소개 문제 풀이벽 부수기 4 문제랑 비슷한데 벽을 부수는 횟수가 k 로 주어진다는 차이점이 있다.import Foundation let nmk = readLine()!.split(separator: " ").map { Int($0)! } let (n, m, k) = (nmk[0], nmk[1], nmk[2]) let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)] var map = [[Int]]() var visited = Array(repeating: Array(repeating: Array(repeating: false, count: m), count: n), count: k+1) for _ in 0.. idx { let poped = ..

문제 소개문제 풀이BFS, DFS 두가지 풀이 방법이 있다. 시간은 둘다 22ms, 24ms 로 별 차이 없는 듯 하다.BFSimport Foundation let s = readLine()! let t = readLine()! func bfs() { var queue = [s] var idx = 0 while queue.count > idx { let poped = queue[idx] idx += 1 if poped == t { print(1) exit(0) } if poped.count > 50 { break } if t.contains(poped) || t.contains(String(poped.reversed())) { queue.append(poped + "A") queue.append(Stri..