전체 글

문제 소개문제 풀이깊이우선탐색(dfs)을 활용하여 최댓값을 출력하였다.import Foundation let n = Int(readLine()!)! let weights = readLine()!.split(separator: " ").map { Int($0)! } var maxValue = 0 func dfs(_ current: Int, _ weights: [Int]) { if weights.count == 2 { maxValue = max(maxValue, current) } for i in 1..

문제 소개 문제 풀이우선 queue를 사용하였는데 removeFirst()를 사용하지 않고 index를 조절하여 queue를 관리했다. bfs로 푼 이유는 dfs로 끝까지 하는 것보다 최솟값을 찾기에는 bfs가 효과적이다. 나머지는 구현의 문제였다.import Foundation let nm = readLine()!.split(separator: " ").map { Int($0)! } let (n, m) = (nm[0], nm[1]) var map = [[String]]() var coins = [[Int]]() for i in 0.. Bool { return o[0] >= 0 && o[0] = 0 && o[1] ..

문제 소개주어진 배열의 부분수열중 원하는 값을 만족하는 부분수열의 갯수를 구하는 문제이다.문제 풀이부분수열의 합을 저장하고 합이 s와 같다면 count를 올려준다. 고려 사항 1. 처음에 0으로 시작하기 때문에 start라는 변수를 넣어서 dfs함수가 최소 한번은 실행되어야 current == s 조건을 확인하도록 설정했다. 2. current == s 일 경우 바로 return 했는데, 만약 부분수열중에 -1, +1 처럼 0이 되는 요소들이 뒤에 있다면 그것도 고려해야하기 때문에 return을 없애주었다.import Foundation let ns = readLine()!.split(separator: " ").map { Int($0)! } let (n, s) = (ns[0], ns[1]) let in..

문제 소개숫자의 배열과 연산기호의 배열을 주면 이를 통해 가장 큰 값, 작은 값을 찾는 문제이다.문제 풀이순서대로 연산을 해주기 때문에 dfs로 앞에서부터 처리하면 되겠다라고 생각했고, 결과는 20ms 로 매우 빠르게 결과값을 얻을 수 있었다. 모든 경우의 수를 계산해준 뒤 maxValue, minValue 를 업데이트 시켰다.import Foundation let n = Int(readLine()!)! let nums = readLine()!.split(separator: " ").map { Int($0)! } let operation = readLine()!.split(separator: " ").map { Int($0)! } var maxValue = -1_000_000_000 var minValu..

문제 소개https://www.acmicpc.net/problem/1339예를 들면 GCF + ACDEB 일 때 A부터 G까지 숫자를 부여한뒤 GCF + ACDEB 의 최댓값을 구하면 되는 문제이다. 문제 풀이GCF + ACDEB 의 경우 각 번호에 1을 부여한다고 생각해 보면 아래와 같이 값이 나오게 되고, 높은 값부터 9를 부여해 주면 된다.dictionary 로 데이터를 쌓아주고, 이것을 nums에 넣어준 뒤 높은 숫자부터 9부터 순서대로 곱해주면서 더하면 최댓값을 구할 수 있다.import Foundation let n = Int(readLine()!)! var dict = [String: Int]() for _ in 0..) for i in nums.indices { answer += nums[..

문제 소개부등호가 주어지면 그 부등호에 맞는 숫자의 최소값, 최대값을 출력하는 문제이다. 문제 풀이모든 숫자의 배열을 구하는 dfs 함수와 해당 배열과 부등호가 잘 맞는지 check 함수를 구했다. dfs 함수에서 depth > 0 && !check(current) 조건을 두어 조건에 맞지 않으면 바로 함수를 종료하도록 했다.import Foundation let k = Int(readLine()!)! let input = readLine()!.split(separator: " ").map { String($0) } let nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] var visited = Array(repeating: false, count: 10) var answers = [..

문제 소개https://www.acmicpc.net/problem/1167 트리의 지름을 출력하는 문제이다.문제 풀이한 점에서 가장 먼 노드를 구한뒤, 그 노드에서 가장 먼 곳을 구하면 된다.import Foundation let n = Int(readLine()!)! var tree = [Int: [(node: Int, cost: Int)]]() for i in 1...n { let input = readLine()!.split(separator: " ").map { Int($0)! } tree[input[0]] = [] for j in 0.. maxCost { point = node maxCost = cost } } visited[point] = true dfs(point, maxCost) visit..

문제 소개https://www.acmicpc.net/problem/1967트리에서 가장 긴 거리의 두 노드를 구하는 문제이다. 문제 풀이아이디어는 다음과 같다. 한 노드에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드와의 거리를 구하면 된다.import Foundation let n = Int(readLine()!)! var graph = [Int: [(node: Int, distance: Int)]]() for i in 1...n { graph[i] = [] } for _ in 0..