→ Problems

문제 소개https://www.acmicpc.net/problem/7576토마토가 다 익는 시간을 구하는 문제이다. 익은 토마토부터 번져나가는(?) 시간을 구하는 것이다. 문제 풀이bfs를 활용하여 풀었다. 문제는 queue를 활용하긴 했지만 removeFirst의 시간복잡도가 O(n)이였기 때문에 시간초과 문제가 났다. 그래서 removeFirst와 똑같은 효과가 나게 하여 index를 활용하여 문제를 풀었다.import Foundation let mn = readLine()!.split(separator: " ").map { Int($0)! } let (m, n) = (mn[0], mn[1]) var box = [[Int]]() var queue = [(Int, Int)]() for i in 0..=..

문제 소개https://www.acmicpc.net/problem/2178미로를 탐색하는 문제이다. 이러한 문제는 가장 최소의 칸수를 구해야 하는 문제이다. 문제 풀이BFS 풀이미로이기 때문에 한가지 길로 깊게 탐색하는 것보다 넓게 탐색하는 방법을 생각해 보았다.import Foundation let nm = readLine()!.split(separator: " ").map { Int($0)! } let (n, m) = (nm[0], nm[1]) var map = [[Int]]() var graph = Array(repeating: Array(repeating: 0, count: m), count: n) var visited = Array(repeating: Array(repeating: false, ..

문제 소개https://www.acmicpc.net/problem/2667DFS, BFS 로 모두 풀 수 있는 문제여서 두가지 방법을 사용해 보았다. 문제 풀이DFS 풀이우선 dfs를 활용한 풀이는 재귀함수를 사용했다.import Foundation let n = Int(readLine()!)! var visit = Array(repeating: Array(repeating: false, count: n), count: n) var graph = [[Int]]() for _ in 0..

문제 소개https://www.acmicpc.net/problem/11724연결 요소의 갯수를 출력하는 문제이다. 문제 풀이아래와 같이 그래프를 만들어서 dfs로 순회하는 식으로 문제를 풀었다.import Foundation let nm = readLine()!.split(separator: " ").map{ Int(String($0))! } let (n, m) = (nm[0], nm[1]) var graph = Array(repeating: Array(repeating: 0, count: n+1), count: n+1) var visited = Array(repeating: false, count: n+1) visited[0] = true for _ in 0..

문제 소개https://www.acmicpc.net/problem/1260문제에서 아예 솔직하게 DFS, BFS로 탐색해봐라 라는 문제이다. 문제 풀이BFS가 익숙하지 않아서 조금 어려움을 겪었다. 큐를 사용하여 BFS를 구현하였다.import Foundation let nmv = readLine()!.split(separator: " ").map{Int(String($0))!} let (n, m, v) = (nmv[0], nmv[1], nmv[2]) var graph = Array(repeating: Array(repeating: 0, count: n+1), count: n+1) for _ in 0..

문제 소개https://www.acmicpc.net/problem/13023 문제풀이문제를 보고 가장 먼저 연결리스트가 떠올랐다. 연결리스트로 쭉 따라가서 depth가 5가 되면 1을 출력하면 된다는 것을 생각했다.import Foundation let nm = readLine()!.split(separator: " ").map{Int(String($0))!} let (n, m) = (nm[0], nm[1]) var people = [Int: [Int]]() for i in 0..

문제 소개나무를 어떻게 잘라야 하는지 결정해야하는 이진탐색 문제이다.  문제풀이이 문제를 보고 이진탐색을 바로 생각할 수 있는 이유는 어떠한 값을 넣게 되면 true, false로 나오게 되고, 어떠한 값들의 집합이 오름차순으로 되어있는 것을 볼 수 있다. 예를 들면 [1, 2, 3, 4, 5] 의 경우가 있을 때, 어떠한 로직에 의해서 [True, True, False, False, False] 로 바꿔줄 수 있다면 이진탐색으로 풀수있는 문제이다.import Foundationlet nm = readLine()!.split(separator: " ").map { Int($0)! }let (n, m) = (nm[0], nm[1])let trees = readLine()!.split(separator: "..

문제 소개 6064번: 카잉 달력입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다.www.acmicpc.net진법과 아주 비슷한 개념인데 진법은 위로 쌓아가지만 위의 카잉 달력은 해당 숫자가 넘으면 다시 1로 시작한다는 차이점이 있다. 풀이 방법m, n, x, y가 주어지는데 아래와 같이 볼 수 있다. 결국 a와 b를 구하라는 뜻인데, 단순하게 a를 0부터 차례로 대입해나가면 된다. 그리고 최대 연도(종말 연도)는 m과 n의 최소공배수로 볼 수 있다.year % m = xyear % n = yyear = ma + xyear = nb + y 내가 작성한 코드는 아래와 ..