algorithm
-
백준 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 만큼이 자신의 크기입니다. 위 예처럼 하나만 빠져도 정사각형이 될 수 없기 때문이죠! 이 성질을 ..
-
백준 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]..
-
백준 1005 ACM CraftAlgorithm/BOJ 2021. 4. 19. 15:30
출처: www.acmicpc.net/problem/1005 분류: 위상정렬 접근방식 특정 순서가 있는 방향성 비순환 그래프(DAG)로 위상정렬의 개념으로 해결할 수 있는 문제였습니다. 위상정렬 개념 다시보기 다음 건물을 짓기 위해서는 그 전의 건물이 모두 다 지어져야 하므로 해당 건물을 짓기 위해 필요한 시간을 체크하는 배열을 하나 두고 연결을 끊으면서 가장 오래 걸리는 시간으로 업데이트를 해줍니다. for adj in adjacent[run] { adjCount[adj] -= 1 if totalTime[adj] < totalTime[run] + runTime[adj] { totalTime[adj] = totalTime[run] + runTime[adj] } if adjCount[adj] == 0 { r..
-
백준 1238 파티Algorithm/BOJ 2021. 4. 19. 14:00
출처: www.acmicpc.net/problem/1238 분류: 최단거리, 다익스트라 접근방식 단방향 그래프에서 목적지 X까지 갔다가 돌아오는 비용이 최대인 경우를 찾는 문제였습니다. 즉, (출발지 -> X)의 최단거리 + (X -> 출발지)의 최단거리를 구하는 게 목표였습니다. 저는 다익스트라 알고리즘으로 각 경우의 최단거리를 구해서 해결해줬습니다. 해결방법 import Foundation typealias Edge = (dest: Int, dist: Int) let nmx = readLine()!.split(separator: " ").map { Int(String($0))! } let (n, m, x) = (nmx[0], nmx[1], nmx[2]) var map = [[Edge]](repeati..
-
백준 16920 확장 게임Algorithm/BOJ 2021. 4. 9. 14:42
출처: www.acmicpc.net/problem/16920 분류: BFS 접근방식 문제 자체도 복잡하긴 한데 문제 설명이 좀 애매해서!!!!! 애를 좀 먹었던 문제였습니다. Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 문제를 보면 위와같이 써있는데요, 이렇게 되면 딱 Si 번째 칸만 칠하는 것(성으로 만드는 것)처럼 생각할 수 있는데 그게 아니라 Si번까지 이동하는 중에 있는 칸은 모두 칠해야 합니다. 반례는 예제 6번에 있는데요, 예제 6번을 살펴보면 처음 플레이어1 이 플레이 하고나면 ["1", "1", "1", "1"] ["1", "1", "1", "1"] [".", "1", "1", "."] ["1", ".", ".", "2"] 다음과 같이 되고 그 다음에 플레이어2 가 진행하고..
-
백준 2629 양팔저울Algorithm/BOJ 2021. 4. 8. 18:29
출처: www.acmicpc.net/problem/2629 분류: DP 접근방식 DFS 느낌으로 무게를 달 수 있는 경우들을 잘 세어야 하는 문제였습니다. 하나의 추를 놓고 3가지 경우를 생각해볼 수 있습니다. 1. 추를 추가하지 않았을 경우 2. 추를 구슬 반대쪽에 추가 ( weight + 추 ) 3. 추를 구슬 쪽에 추가 ( |weight - 추| ) 문제는 기저사례를 체크하는 부분이었는데, 단순히 무게만으로 확인했는지 체크하면 안 됩니다. 추를 몇 개를 사용했는지에 따라서 다음 무게들이 달라질 수 있기 때문에 몇 개의 추를 사용해 만든 무게인지 구분해줘야 합니다. 따라서 [현재 추][무게] 인 2차원 배열로 체크해줬네요! 추를 추가하지 않는 경우도 생각해줬기 때문에 마지막에 체크해줄 때는 추를 모두..