문제 https://www.acmicpc.net/problem/2293 풀이 DP를 사용하는 문제이다. dp 테이블의 각 인덱스가 해당 인덱스 만큼의 가치를 만들 수 있는 경우의 수 라고 하면 쉽게 풀 수 있다. 동전의 가치를 value라고 하면 그 동전을 하나 추가해서 i만큼의 가치를 만들 수 있는 경우의 수는 dp[i] += dp[i - value] 라고 할 수 있다. 따라서 하나의 가치에 대해서 동전의 종류의 수 만큼 반복문을 돌려야 한다. 문제에서 주어진 또 다른 조건은 경우의 수가 2의 31제곱이 넘지 않는다는 것이다. 또한 스위프트에서는 오버플로우를 방지하기 위해 2의 31제곱이 넘어가는 수를 다 제거해줘야 한다. (최종적으로 출력할 결과가 2의 31제곱이 넘어가지 않으므로 중간에 2의 31제곱이 넘는 값은 자연스럽게 쓸모가 없는 값이 된다.) ...

문제 https://www.acmicpc.net/problem/17298 풀이 스택을 이용하는 문제이다. 2493번 문제와 사실상 같은 문제인데, 배열이 뒤집혀 있다는 것과 인덱스가 아닌 해당 인덱스에 대응하는 값을 사용하는 것이 다르다. 코드 Swift import Foundation let n = Int(readLine()!)! let a = Array(readLine()!.split(separator: " ").map { Int(String($0))! }.reversed()) var stack: [Int] = [] var answer: [Int] = [] for element in a { while !stack.isEmpty && stack.last! <= element { stack.removeLast() } if let last = stack.last { answer.append(last) } else { answer.append(-1) } stack.append(element) } print(answer.map { String($0) }.reversed().joined(separator: " ")) C++ #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> a; for(int i = 0; i < n; i++) { int temp; cin >> temp; a.push_back(temp); } vector<int> stack; vector<int> answer; reverse(a.begin(), a.end()); for(int element: a) { while(!stack.empty() && stack.back() <= element) { stack.pop_back(); } if(stack.empty()) { answer.push_back(-1); } else { answer.push_back(stack.back()); } stack.push_back(element); } for(int answerIndex = (int)answer.size() - 1; answerIndex >= 0; answerIndex--) { cout << answer[answerIndex] << " "; } }

문제 https://www.acmicpc.net/problem/1939 풀이 섬(노드)들과 다리(엣지)로 이루어진 그래프가 주어지고, 그 다리들 사이를 지나 목표 노드에 도착해야 한다. 다리에 웨이트가 존재하지 않고 (중량 제한은 엣지가 유효한지 판단하는 기준일 뿐 엣지의 웨이트랑 관련 없다) 최단 거리를 구하는 문제도 아니므로, 다익스트라 알고리즘이 아닌 BFS를 이용해 탐색할 수 있다. 중량이 늘어날수록 건널 수 있는 다리가 적어진다(엣지가 비활성화 된다). 우리는 이 때 주어진 두 섬 중 하나의 섬에서 다른 하나의 섬으로 갈 수 있는 최대의 중량을 구하면 된다. 리니어 서치로도 결과를 구할 수야 있겠지만 현실적으로 1 - 1,000,000,000 값을 다 탐색하는건 너무 비효율적이기 때문에 바이너리 서치를 하면 된다. ...

문제 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와 같은 배열이 없어도 이미 지나간 곳임을 알 수 있다. 알고리즘을 순서대로 나타내면 다음과 같다. ...

Protocol Extensions 프로토콜은 메소드, 이니셜라이저, 서브스크립트, 컴퓨티드 프로퍼티를 해당 프로퍼티를 준수하는 타입들에게 제공하도록 확장될 수 있다. 이는 각 타입의 개별 준수나 전역 함수가 아니라 프로토콜 스스로 동작을 정의할 수 있게 해준다. 예를 들어, RandomNumberGenerator 프로토콜은 random() 메소드 요구사항의 결과값을 사용하여 랜덤 Bool 값을 리턴하는 randomBool() 메소드를 제공하도록 확장될 수 있다. extension RandomNumberGenerator { func randomBool() -> Bool { return random() > 0.5 } } 프로토콜의 익스텐션을 만들면, 해당 프로토콜을 준수하는 모든 타입은 추가적인 수정 없이 모든 이러한 메소드 구현을 자동적으로 얻게 된다. ...

Protocol Composition 하나의 타입이 여러개의 프로토콜을 동시에 준수하도록 하는 것이 유용할 때가 있다. 프로토콜 구성(protocol composition) 을 통해 여러 개의 프로토콜을 하나의 프로토콜로 결합할 수 있다. 프로토콜 구성은 내부에 있는 모든 프로토콜의 요구사항을 결합한 임시 로컬 프로토콜을 정의한 것처럼 동작한다. 하지만 프로토콜 구성은 어떠한 새로운 프로토콜 타입도 정의하지 않는다. 프로토콜 구성은 SomeProtocol & AnotherProtocol의 형태를 가진다. 앰퍼샌드로 구분하여 필요한 수 만큼 프로토콜을 나열할 수 있다. 프로토콜 리스트에 추가로 프로토콜 구성은 필요로 하는 슈퍼클래스로 지정하기 위해 하나의 클래스 타입을 포함할 수도 있다.(주: 프로토콜 구성을 준수하려면 특정 클래스의 서브클래스이어야 할 때, 슈퍼클래스도 그 프로토콜 구성 내부에 포함시킨다.) ...

Adding Protocol Conformance with and Extension 새로운 프로토콜을 도입하고 준수하기 위해 이미 존재하는 타입을 확장할 수 있다. 그 타입의 원본 소스코드에 접근하지 못하더라도 가능하다. 익스텐션은 이미 존재하는 타입에 새로운 프로퍼티, 메소드, 서브스크립트를 추가할 수 있으므로, 프로토콜에서 요구하는 모든 요구사항들을 추가할 수 있다. Note 타입의 이미 존재하는 인스턴스는 인스턴스의 타입의 익스텐션에 프로토콜 준수가 추가되었을 때, 자동적으로 프로토콜을 준수하게 된다. 예를 들어, TextRespresentable 프로토콜은 텍스트로 표현할 수 있는 방법이 있는 모든 타입에서 구현 가능하다: ...