boj
-
백준 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 } ..
-
백준 9252 LCS 2Algorithm/BOJ 2021. 4. 20. 11:25
출처: www.acmicpc.net/problem/9252 분류: LCS 접근방식 최장 증가 수열을 찾는 전통적인 LCS 문제입니다. 문자열을 그대로 사용하면 시간초과가 나서 길이 테이블을 완성하고 백트래킹을 통해 문자열을 찾아주는 방식으로 해결했습니다. LCS는 다음과 같이 두 문자열로 이차원 행렬을 완성시켜 나가는 방식으로 찾아줄 수 있습니다. 현재 칸의 두 문자열의 문자가 같다면 왼쪽 대각선 위의 문자열에 현재 문자를 붙여나갑니다. 다르다면 위나 왼쪽 중에서 더 큰 문자열을 가져옵니다. 같다면 모두 가능한 문자열이겠죠? 이 원리를 이용해 저희 예제로 만들어보면 가로 CAPCAK 세로 ACAYKP 로 두면 다음과 같은 LCS 테이블을 만들 수 있습니다. 이제 마지막으로 마지막부터 백트래킹으로 문자열을..
-
백준 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 만큼이 자신의 크기입니다. 위 예처럼 하나만 빠져도 정사각형이 될 수 없기 때문이죠! 이 성질을 ..