Problem Solving

문제 https://www.acmicpc.net/problem/16234 풀이 그래프 각 원소를 전체 탐색하며, BFS를 수행하는 문제이다. 탐색할 수 있는 칸에 대한 제약조건이 문제에 제시되므로, 이에 따라 BFS를 수행하면 된다. 알고리즘은 다음과 같다. 그래프 전체를 순서대로 순회한다. 이 때 칸이 isVisited가 false인 칸에서 bfs를 수행한다. 따라서 isVisited는 전역 변수(혹은 call by reference)가 되어야 한다. bfs로 탐색한 칸은 서로 연합이 가능한 칸이다. bfs 탐색의 조건은 문제에 상세히 적혀있다. 그래프 전체를 순회하며 bfs 탐색을 실시하고 각 칸의 값을 조정하면, 이게 문제에서 말하는 ‘하루’가 지난 것이다. isVisited가 false인 칸만 연합을 수행하므로, 앞선 칸에서 수행한 bfs 탐색이 뒤에 있는 칸에 영향을 끼칠 일은 없다. 1회의 인구 이동이 끝났어도 또 인구 이동이 가능할 수 있다. 따라서 1.을 더 이상 인구이동이 불가능해 질 때까지 수행한다. 코드 import Foundation func bfs(root: (Int, Int)) -> Bool { struct Queue { private var queue = [(Int, Int)]() private var ptr = 0 var isEmpty: Bool { ptr >= queue.count } mutating func insert(v: (Int, Int)) { queue.append(v) } mutating func delete() -> (Int, Int) { let popped = queue[ptr] ptr += 1 return popped } } let moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] var queue = Queue() var union: [(Int, Int)] = [root] var unionPop = graph[root.0][root.1] queue.insert(v: root) isVisited[root.0][root.1] = true while !queue.isEmpty { let node = queue.delete() for move in moves { let newNode = (node.0 + move.0, node.1 + move.1) if newNode.0 < 0 || newNode.0 >= n || newNode.1 < 0 || newNode.1 >= n { continue } if isVisited[newNode.0][newNode.1] { continue } let differ = abs(graph[node.0][node.1] - graph[newNode.0][newNode.1]) if differ >= l && differ <= r { isVisited[newNode.0][newNode.1] = true queue.insert(v: newNode) union.append(newNode) unionPop += graph[newNode.0][newNode.1] } } } let dividedPop = unionPop / union.count for element in union { graph[element.0][element.1] = dividedPop } if union.count > 1 { return true } else { return false } } let nlr = readLine()!.split(separator: " ").map { Int(String($0))! } let (n, l, r) = (nlr[0], nlr[1], nlr[2]) var graph = [[Int]]() for _ in 0..<n { graph.append(readLine()!.split(separator: " ").map { Int(String($0))! }) } var isVisited = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n) var answer = 0 while true { var isEnd = true for row in 0..<n { for column in 0..<n { if !isVisited[row][column] && bfs(root: (row, column)){ isEnd = false } } } if isEnd { break } isVisited = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n) answer += 1 } print(answer)

문제 https://www.acmicpc.net/problem/1520 풀이 dfs를 이용하면 쉽게 풀 수 있는 문제일 것 같지만, 주어지는 그래프의 크기가 커서 시간초과가 나오는 문제이다. 하지만 이러한 문제들은 중첩되는 연산이 많으므로 DP를 이용하면 시간초과 없이 해결할 수 있는 경우가 흔하다. DP의 컨셉은 다음과 같다. 그래프의 특정 칸에서 목적지로 도착하는 경우의 수는 앞선 경로에 상관없이 항상 같다. 따라서 각 칸에서 목적지로 가는 경로의 수를 dp테이블에 메모이제이션 한다면 불필요한 연산을 하지 않아도 된다. 따라서 점화식을 dp[x][y] = dp[x - 1][y] + dp[x + 1][y] + dp[x][y - 1] + dp[x][y + 1]로 일반화 할 수 있다. 각 항에서 탐색이 불가능한 칸((x, y)보다 높은 칸, 존재하지 않는 칸) 에 대응되는 항은 제외해야하기 때문에 엄밀히 말해서는 틀리지만, 이해하는데는 충분하다. ...

문제 https://www.acmicpc.net/problem/6087 풀이 다익스트라 알고리즘을 사용하여 해결하는 문제이다. 각 인접한 노드가 연결되어있다고 생각하고, 전의 노드에서 현재 노드로 온 방향과 수직인 노드만 거리를 1로 설정해주면 된다. 일반적인 다익스트라 알고리즘 문제에서는 연결된 노드간의 거리가 주어지는데, 이 문제에서는 연결된 노드의 거리를 0으로 할지, 1로 할지 선택해야한다. 하지만 다익스트라 알고리즘과 BFS의 관계를 잘 생각해보면, 어렵지 않게 풀 수 있다(개인적으로 BFS는 일종의 다익스트라 특이 케이스라고 생각한다.) 알고리즘은 다음과 같다. 그래프에서 인접한 칸끼리는 서로 연결된 노드라고 가정함 (노드간 거리는 기본적으로 0으로 생각) 현재 있는 칸에서 내가 바라보고 있는 방향을 기준으로 수직인 노드는 거리가 1, 아닌 노드는 0으로 설정 2.를 반복하면서 다익스트라 수행 vertical은 가로 이동 horizontal은 세로 이동 neutral은 중립 방향인데, 시작 지점이나 아래에서 설명할 다른 Direction이지만 같은 거리에 있는 노드가 가지는 방향이다. none은 아직 탐색하지 않은 노드가 가지는 방향이다. ...

문제 https://www.acmicpc.net/problem/14502 풀이 dfs와 bfs가 합쳐진 문제이다. 벽을 꼭 3개를 세워야 하므로 dfs를 이용하여 벽을 세울 위치를 전체 탐색할 수 있다. 연구소의 크기가 최대 8 * 8 이므로 전체 탐색하는데 큰 문제가 발생하지 않는다. 벽을 세웠으면 bfs를 이용하여 바이러스가 퍼졌을 때의 연구소의 모습을 그린다. 이 때 바이러스가 지나간 자리는 2로 마킹되고, 벽은 바이러스가 지나가지 못하므로 isVisited와 같은 배열이 없어도 이미 지나간 곳임을 알 수 있다. 알고리즘을 순서대로 나타내면 다음과 같다. ...

문제 https://www.acmicpc.net/problem/11000 풀이 정렬 후 그리디를 수행하는 전형적인 그리디 알고리즘 문제이다. 강의가 시작하는 시간과 끝나는 시간이 주어져 있으므로 배열에 입력으로 주어진 시간들을 저장한 다음에 정렬해서, 강의가 가장 많은 시간의 강의 수를 출력하면 된다. 알고리즘을 글로 표현하면 다음과 같다. 수업이 시작하는 시간과 끝나는 시간을 배열 lecture에 저장한다. 이때 배열은 [(Int, Bool)] 타입이며, Int에는 시간, Bool에는 강의가 시작하는 시간일 경우 true, 끝나는 시간일 경우 false를 저장한다. 배열 lecture를 정렬한다. lecture를 for 반복문으로 전체 순회한다. 튜플의 두 번째 원소가 true인 경우 현재 진행 중인 강의 수를 저장하는 변수 current의 값을 1 더한다. false인 경우 강의가 끝난 것 이므로 변수 current의 값을 1 뺀다. 이때, 배열 lecture를 시간순으로만 정렬하게 되면 문제에서 다음과 같은 부분 때문에 문제가 생긴다. ...

문제 https://www.acmicpc.net/problem/1049 풀이 6개 묶음 패키지의 가격과 낱개의 가격이 각각 여러 개가 주어졌을 때, 가장 적은 비용으로 n개 이상의 수를 채워야 하는 문제이다. 문제의 알고리즘은 다음과 같다. 패키지의 가격과 낱개의 가격이 같이 들어오므로 현재 가장 싼 패키지와 낱개의 가격과, 입력으로 들어온 가격을 각각 비교해서 갱신한다. 패키지만 샀을때, 낱개만 샀을때, 패키지와 낱개를 동시에 샀을때 세가지 경우를 비교해서 가장 비용이 낮은 값을 출력한다. 이 문제에서 구매 수량에 제한을 두지 않았으므로, 굳이 배열을 만들고 정렬을 할 필요가 없다. 패키지든 낱개든 무조건 가장 싼 가격만 알고 있으면 된다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12946 풀이 이런 문제는 문제를 읽었을 때 어떻게 풀어야 할지 감이 잘 잡히지 않는다. 이러한 상황에서는 우선 문제를 시각화 해보자. 좌측은 n = 1일때, 우측은 n = 2일때의 이동을 시각화 한 것이다. 빨간색 숫자는 원판을 뜻하고 파란색 선은 이동루트를 뜻한다. n = 1 일 때는 당연한 이동 경로지만 n = 2일 때는 중간에 있는 기둥을 사용해야한다. 하지만 아직까진 규칙이 뚜렷하게 드러나지 않는다. n = 3 일때의 이동경로를 시각적으로 나타냈다. 사실 직접 손으로 그리지 않고 다른 사람이 그린 그림으로 봤을 땐 아직도 규칙이 아리송 할 수 있지만 손으로 직접 그렸을 땐 규칙을 바로 알아 챌 수 있다. ...

문제 https://www.acmicpc.net/problem/1753 풀이 다익스트라 입문 문제이다. 단, 스위프트로 풀려면 힙을 직접 구현해야 한다. 입력으로 주어지는 엣지의 웨이트가 모두 같다는 조건이 없으므로, BFS가 아닌 다익스트라로 탐색해야 한다. 코드 import Foundation struct Heap { var heap: [(Int, Int)] = [] func isEmpty() -> Bool { return heap.isEmpty ? true : false } mutating func insert(_ value: (Int, Int)) { heap.append(value) var currentIndex = heap.count - 1 while currentIndex > 0 { let parentIndex = (currentIndex - 1) / 2 if heap[currentIndex].1 < heap[parentIndex].1 { heap.swapAt(currentIndex, parentIndex) currentIndex = parentIndex } else { break } } } mutating func deleteMin() -> (Int, Int) { if heap.isEmpty{ return (0, 0) } let min = heap[0] heap[0] = heap[heap.count - 1] heap.removeLast() var currentIndex = 0 while true { let leftChildIndex = 2 * currentIndex + 1 let rightChildIndex = 2 * currentIndex + 2 if leftChildIndex >= heap.count { break } var minChildIndex = leftChildIndex if rightChildIndex < heap.count && heap[rightChildIndex].1 < heap[leftChildIndex].1 { minChildIndex = rightChildIndex } if heap[minChildIndex].1 < heap[currentIndex].1 { heap.swapAt(currentIndex, minChildIndex) currentIndex = minChildIndex } else { break } } return min } } func dijkstra(k: Int) { var heap = Heap() heap.insert((k, 0)) distanceTable[k] = 0 while !heap.isEmpty() { let edge = heap.deleteMin() if distanceTable[edge.0] < edge.1 { continue } for node in graph[edge.0] { let cost = edge.1 + node.1 if cost < distanceTable[node.0] { distanceTable[node.0] = cost heap.insert((node.0, cost)) } } } } let ve = readLine()!.split(separator: " ").map { Int(String($0))! } let k = Int(readLine()!)! var graph = [[(Int, Int)]](repeating: [], count: ve[0] + 1) for _ in 0..<ve[1] { let uvw = readLine()!.split(separator: " ").map { Int(String($0))! } graph[uvw[0]].append((uvw[1], uvw[2])) } var distanceTable = [Int](repeating: 300_001, count: ve[0] + 1) dijkstra(k: k) for i in 1...ve[0] { if distanceTable[i] == 300_001 { print("INF") } else { print(distanceTable[i]) } }

문제 https://www.acmicpc.net/problem/14003 풀이 LIS(Longest Increasing Subsequence)라고 하는 유명한 DP 문제이다. 이 문제 외에도 연계된 문제들이 많으니 1번(BOJ 11053)부터 차례대로 풀면 어느새 여기까지 풀게 된다. 이 문제들은 총 2가지 기준으로 분류된다. 첫 번째 기준은 O(n²), O(nlogn) 두 번째는 LIS 출력 여부이다. 이 중에 O(nlogn) 알고리즘을 사용하고 LIS를 직접 출력해야 하는 문제가 이 문제이다. 원래는 Swift로 작성하려 했지만, 백준의 입력시간 문제 때문에 Swift론 입력 횟수가 적은 O(n²)문제를 풀고 O(nlogn) 문제는 C++로 작성하였다. 기본적인 알고리즘 콘셉트는 다음과 같다. ...

문제 https://www.acmicpc.net/problem/16398 풀이 모든 행성을 연결해야 하고, 그 비용을 최소로 하려면 최소 스패닝 트리(MST)를 찾아야 한다. 따라서 알고리즘의 흐름은 다음과 같아진다. 2차원 배열로 입력받은 플로우 관리비용을 정렬한다. Kruskal 알고리즘을 이용해 최소 스패닝 트리를 구한다. 여기서 에지(플로우 관리비용)의 정보가 2차원 배열로 입력되므로 배열을 순회하여 (노드, 노드, 비용)꼴의 튜플 배열로 만들어 정렬했다. 2차원 배열의 각 인덱스가 노드를 특정하므로 이렇게 하는 것이 최선이라 생각했다. 코드 func find(_ a: Int) -> Int { if parent[a] != a { parent[a] = find(parent[a]) } return parent[a] } func union(_ a: Int, _ b: Int) { let pa = find(a) let pb = find(b) if pa < pb { parent[pb] = pa } else { parent[pa] = pb } } import Foundation let n = Int(readLine()!)! var graph: [[Int]] = [] var edges: [(Int, Int, Int)] = [] var parent = Array(0..<n) var answer: Int = 0 for _ in 0..<n { graph.append(readLine()!.split(separator: " ").map { Int(String($0))! }) } for row in 0..<n { for column in 0..<row { edges.append((row, column, graph[row][column])) } } edges.sort(by: { $0.2 < $1.2 } ) for edge in edges { if find(edge.0) != find(edge.1) { union(edge.0, edge.1) answer += edge.2 } } print(answer)