백준
-
백준 1981 후위 표기식Algorithm/BOJ 2021. 4. 26. 23:46
출처: www.acmicpc.net/problem/1918 분류: 스택 접근방식 말 그대로 후위표기식 변환에 관한 문제였습니다. 설명은 따로 포스팅으로 대체하겠습니다 :) 해결방법 var str = readLine()! var result = "" var oper = "" for char in str { if char == "(" { oper.append("(") } else if char == ")" { while let opr = oper.popLast() { guard opr != "(" else { break } result.append(opr) } } else if char == "*" || char == "/" { guard !oper.isEmpty else { oper.append(char)..
-
백준 2493 탑Algorithm/BOJ 2021. 4. 22. 16:58
출처: www.acmicpc.net/problem/2493 분류: Stack 접근방식 인덱스와 탑의 높이를 스택에 담아두고, 현재 빌딩의 높이가 인덱스의 탑보다 크면 스택에 담겨있는 인덱스에 현재 빌딩의 인덱스를 저장해두는 방식으로 해결했습니다. 해결방법 let n = Int(readLine()!)! let building = readLine()!.split(separator: " ").map { Int(String($0))! } var received = [Int](repeating: 0, count: n) var stack = [(idx: Int, top: Int)]() for (idx, top) in building.enumerated().reversed() { while !stack.isEmpty..
-
백준 1958 LCS 3Algorithm/BOJ 2021. 4. 22. 12:30
출처: www.acmicpc.net/problem/1958 분류: LCS, 문자열, DP 접근방식 이번엔 3개 문자열의 LCS를 구하는 문제였습니다. 기존 LCS와 원리는 동일하고 이를 3차원 배열로 확장시키면 되는 문제였습니다. func lcs(_ strA: [Character], _ strB: [Character], strC: [Character]) -> Int { var table = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: strC.count+1), count: strB.count+1), count: strA.count+1) for a in 1...strA.count { for b in 1...strB.count { f..
-
백준 11049 행렬 곱셈 순서Algorithm/BOJ 2021. 4. 21. 14:08
출처: www.acmicpc.net/problem/11049 분류: DP 접근방식 전체 순서를 유지하면서 특정 연산을 해야할 때 연산 순서를 어떻게 해야 최소가 될까? 에 관한 문제였습니다. 11066 파일합치기 와 유사한 문제였다는 생각이 드네요. 핵심 아이디어는 X ~ Y까지 연산의 최소값을 DP에 계속 저장해나가는데, X ~ Y까지 연산의 최솟값은 (X~K) + (K~Y) 연산들 중 최소를 찾아나가는 것입니다. 문제의 예시를 가지고 생각해보겠습니다. 각 행렬이 배열에 들어있다고 생각하면, (5x3) - 0 (3x2) - 1 (2x6) - 2 0 ~ 1 까지의 최소값은 dp[0][1], 0 ~ 2 까지의 최소값은 dp[0][2] 에 담는 것입니다. 0 ~ 2 까지의 최솟값은 ( [0][1] 을 먼저 ..
-
백준 17070 파이프 옮기기 1Algorithm/BOJ 2021. 4. 20. 12:38
출처: www.acmicpc.net/problem/17070 분류: DP, 백트래킹 접근방식 주어진 요구사항 대로 파이프의 이동 가능 위치를 잘 계산하고 나면 백트래킹으로 도착한 경우의 수를 세주면 되는 문제였습니다. 파이프의 끝 점에서 출발한 경로는 역시 다시 방문해줄 필요가 없으므로 방향을 고려한 3차원 배열에 이를 기록해서 방문 횟수를 줄여줬습니다. 조금 귀찮긴 하지만 크게 어렵지는 않아서 풀이를 보시면 이해가 되실거에요 :) 해결방법 let n = Int(readLine()!)! var map = [[Int]]() for _ in 0.. Direction { if pipe.0.r == pipe.1.r, abs(pipe.0.c - pipe.1.c) == 1 { return .horizontal } ..
-
백준 2096 내려가기Algorithm/BOJ 2021. 4. 20. 09:54
출처: www.acmicpc.net/problem/2096 분류: DP 접근방식 간단한 DP 문제였습니다. 1, 2, 3 각 열에서 가장 최선인 경우를 계속 선택해나가면 됩니다. 행마다 갱신하고 나면 그 이전은 생각할 필요가 없으므로 디피는 각 열을 저장할 행 하나만 있으면 됩니다 :) 저는 맨 밑에서부터 올라왔는데 위에서부터 내려가도 상관은 없을듯 하네요! 해결방법 let n = Int(readLine()!)! var num = [[Int]]() for _ in 0..
-
백준 1915 가장 큰 정사각형Algorithm/BOJ 2021. 4. 19. 20:26
출처: www.acmicpc.net/problem/1915 분류: DP 접근방식 문제 이름처럼 만들 수 있는 가장 큰 정사각형을 찾는 문제입니다. 정사각형의 성질을 생각해보면 DP와 재귀를 활용해 정사각형의 크기를 쉽게 구해낼 수 있습니다. 정사각형은 다른 정사각형의 모음입니다. 3x3짜리 정사각형을 예로 들어볼까요? 각 칸에 정사각형의 크기를 적어보면 다음과 같습니다. 3 2 1 2 2 1 1 1 1 여기서 하나가 빠져서 아깝게 정사각형이 못되는 경우를 생각해보면 다음과 같습니다. 2 2 1 2 1 1 1 1 0 규칙이 보이시나요? 정사각형은 자신을 둘러싸고 있는 정사각형들의 크기 중 가장 작은 값 + 1 만큼이 자신의 크기입니다. 위 예처럼 하나만 빠져도 정사각형이 될 수 없기 때문이죠! 이 성질을 ..
-
백준 1937 욕심쟁이 판다Algorithm/BOJ 2021. 4. 19. 19:39
출처: www.acmicpc.net/problem/1937 분류: DP, DFS 접근방식 기본적인 DFS 접근 방식에 DP의 개념을 추가해서 풀 수 있는 문제였습니다. 한 점에서 갈 수 있는 최대 거리(판다의 생존 일 수)를 DFS를 통해 구해나가는 데, 어차피 그 점에서 시작한 결과는 어차피 어디서 와서 시작하든 같기 때문에 다시 탐색할 필요가 없다는 점을 이용합니다. 따라서 일 수를 기록하는 Map크기와 같은 DP를 채워나가면 해결할 수 있었습니다. 해결방법 import Foundation typealias Point = (r: Int, c: Int) let n = Int(readLine()!)! var map = [[Int]]() for _ in 0.. Int { guard dpMap[curr.r]..