DP
-
백준 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]..
-
백준 2629 양팔저울Algorithm/BOJ 2021. 4. 8. 18:29
출처: www.acmicpc.net/problem/2629 분류: DP 접근방식 DFS 느낌으로 무게를 달 수 있는 경우들을 잘 세어야 하는 문제였습니다. 하나의 추를 놓고 3가지 경우를 생각해볼 수 있습니다. 1. 추를 추가하지 않았을 경우 2. 추를 구슬 반대쪽에 추가 ( weight + 추 ) 3. 추를 구슬 쪽에 추가 ( |weight - 추| ) 문제는 기저사례를 체크하는 부분이었는데, 단순히 무게만으로 확인했는지 체크하면 안 됩니다. 추를 몇 개를 사용했는지에 따라서 다음 무게들이 달라질 수 있기 때문에 몇 개의 추를 사용해 만든 무게인지 구분해줘야 합니다. 따라서 [현재 추][무게] 인 2차원 배열로 체크해줬네요! 추를 추가하지 않는 경우도 생각해줬기 때문에 마지막에 체크해줄 때는 추를 모두..
-
백준 1520 내리막 길Algorithm/BOJ 2021. 3. 30. 14:00
출처: www.acmicpc.net/problem/1520 분류: DP, DFS 접근방식 DFS 방식으로 원하는 칸에 도달하는 경로를 찾아나갈 수 있습니다. 대신 모든 경우를 탐색하면 시간제한에 걸리게 되므로 DP를 활용해야 합니다. 현재 칸에서 가능한 경우의 수는 이미 모두 탐색을 했기 때문에 방문한 칸을 다시 방문할 필요는 없고 저장된 방문 횟수만 가져옵니다. 구체적으로는 처음에 DP 배열에 -1을 넣어두고 방문하면 0으로 초기화하고 값을 더해줍니다. DP가 -1일 경우에만 탐색하고 아니면 DP의 값만 리턴합니다. 해결방법 typealias Point = (r: Int, c: Int) let rc = readLine()!.split(separator: " ").map { Int(String($0))!..
-
백준 12865 평범한 배낭Algorithm/BOJ 2021. 3. 30. 13:09
출처: www.acmicpc.net/problem/12865 분류: DP 접근방식 디피로 해결할 수 있는 문제였습니다. 디피는 상황에 따른 최대 값을 기록해놓고 더 최적인 경우를 비교하면서 업데이트 해나가는 메모제이션 방식입니다. 이 문제에서는 특정 무게에 최대 가치가 얼마인지 기록해놓으면 되겠네요. 테이블에는 현재까지 찾은 최적의 가치가 들어있다고 할 때, 현재 무게 4짜리의 물품으로 테이블의 무게 7 칸을 채우려고 한다면 최적은 테이블의 무게 3짜리 칸 가치 + 현재 물품의 가치 (무게 4) vs 테이블의 무게 7짜리 칸의 가치 로 생각해볼 수 있습니다. 이런식으로 물품들을 입력받을 때마다 테이블을 업데이트 해나가면됩니다. 물품마다 현재 무게부터 테이블의 끝까지를 업데이트를 해나가야 하는데 테이블을 ..