https://www.acmicpc.net/problem/2579 계단의 점화식 문제.특정 계단에서 얻을 수 있는 점수는 다음과 같다.n-1, n 이렇게 연속적으로 접근n-2, n 이렇게 떨어져서 접근따라서 다음과 같은 점화식이 세워짐dp[i-3]+stair[i-1]+stait[i] (연속적으로 계단에 접근한 경우)dp[i-2]+stair[i] (비연속적으로 계단에 접근한 경우)import Foundationlet n = Int(readLine()!)!var stairtArr: [Int] = []for _ in 0..
https://www.acmicpc.net/problem/2805 이분 탐색을 이용하여 자르는 부분의 범위를 구하는 문제. import Foundationlet nm = readLine()!.split(separator: " ").map{Int($0)!}let treeArr = readLine()!.split(separator: " ").map{ Int($0)! }var start = 1var end = treeArr.max()!while start mid { count += tree-mid } } if count >= nm[1] { start = mid+1 } else { end = mid-1 }}print(end)
https://www.acmicpc.net/problem/1697 문제 풀이bfs로 최단 경로를 탐색하는 방식으로 풀이. 각 점마다 +1, -1, *2씩 해주므로 한번 방문한 점은 다시 방문할 필요가 없으므로 방문처리를 하여 문제를 해결. import Foundationstruct Node { let count: Int let location: Int}let nk = readLine()!.split(separator: " ").map{ Int($0)! }var visited = Array(repeating: false, count: 100001)func solution() { var queue: [Node] = [.init(count: 0, location: nk[0])] if nk..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 풀이: 위상정렬을 이용하여 풀이했다. 유의해야할 점은 노드를 큐에 추가하지 않더라도, 시간을 갱신 해야만 한다는 점이다. import Foundation final class FileIO { private var buffer:[UInt8] private var index: Int init(fileHandle: FileHandle = FileHandle.standardInput) { bu..
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 풀이: 1초 안에 풀어야 하기에 O(n^2)으로는 풀 수 없으므로 재귀를 이용하여 문제를 풀었다. 투포인터 알고리즘에 일치하지 않는 문자열이 나올 시 다시 해당 함수를 호출하여 일치하지 않는 곳은 건너뛰고 다시 회문인지를 판단하는 방식으로 문제를 해결. 회문이라면 유사회문이고, 다시 유사회문이 나온다면 그 외의 것이기 때문이다. import Foundation let t = Int(readLine()!)! func sol..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 풀이: 기존 최단경로 찾기 문제와 비슷하지만, 다른 점이 있다면 물이 시간이 지남에 따라 확장된다는 점이다. 따라서 Queue에서 어느 시점을 꺼내지만, 해당 시점이 2의 시간이 지난 후일수도, 3의 시간이 지난 후 일수 있다. 이에 시간에 지남에 따라 물이 번진 지도를 3차원 배열로 만들어서 큐에서 꺼낸 시간의 지도 상태값을 가지고 올 수 있도록 구현했다. import Foundation enum Bl..
