다이나믹 프로그래밍48 [백준] 12869번 - 뮤탈리스크 [Java] https://www.acmicpc.net/problem/12869 1. 아이디어 BFS, DFS, 다이나믹 프로그래밍 3가지 방법을 활용해서 해결했다.2. 문제풀이 SCV는 몇 개가 주어지든 3개로 맞춰서 배열에 담았다. 3개 미만으로 주어지면 체력 0의 유령 SCV라고 가정했다. 이는 이후 풀이에서 SCV가 파괴된 경우도 동일하다. 뮤탈리스크의 공격은 9-3-1로 들어오는데 이 공격이 SCV에게 들어오는 것은 순열로 6가지 경우가 있고 각 SCV 상태에 대해 6가지 공격 조합이 추가된다는 흐름으로 구현했다. 공통적으로 현재 상태와 조합을 통해 다음 체력 상태를 반환하는 hit 메서드와 공격 조합에 대한 탐색배열을 작성했고 SCV 체력이 음수가 되지 않게 하여 방문 체크를 진행했다. SCV의 체력은 .. 2025. 1. 21. [백준] 2631번 - 줄세우기 [Java] https://www.acmicpc.net/problem/2631 1. 아이디어 옮겨야하는 아이들의 수의 최솟값은 순서대로 있는 아이들의 번호에서 오름차순에 해당하지 않는 아이들만 옮기면 된다. 이때 오름차순은 가장 긴 오름차순에 해당하며 이는 LIS 알고리즘으로 구할 수 있다.2. 문제풀이 N이 최대 200이어서 다이나믹 프로그래밍을 활용한 LIS 알고리즘으로 구현했다. LIS의 길이를 구한 후 처음 아이들의 수에서 빼주면 옮겨야 하는 아이들의 수를 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Bu.. 2025. 1. 17. [백준] 2748번 - 피보나치 수 2 [Java] https://www.acmicpc.net/problem/2748 1. 아이디어 이전 피보나치 수 문제에서 N의 범위가 더 커진 문제로 int형으로 dp 배열을 선언하면 오버플로우가 발생할 수 있다는 점에 주의해야한다.([코딩테스트 준비/백준] - [백준] 2747번 - 피보나치 수 [Java])2. 문제풀이 기존 피보나치 수에서 배열만 long 타입으로 변경하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.i.. 2025. 1. 16. [백준] 1354번 - 무한 수열 2 [Java] https://www.acmicpc.net/problem/1354 1. 아이디어 이전 무한 수열 문제에서 수의 범위와 점화식의 모양만 약간 달라진 문제로 동일하게 Top-Down 다이나믹 프로그래밍으로 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 1351번 - 무한 수열 [Java])2. 문제풀이 HashMap으로 메모이제이션해서 동일하게 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final Map dp = new HashMap(); public static void main(String[] args) throws IOException { BufferedReader.. 2025. 1. 16. [백준] 22869번 - 징검다리 건너기 (small) [Java] https://www.acmicpc.net/problem/22869 1. 아이디어 BFS, DFS, 다이나믹 프로그래밍 3가지 방법으로 해결했다.2. 문제풀이 - BFS해당 문제는 각 돌을 노드로 이동할 수 있는 돌에는 간선을 연결한다 했을 때 1번 노드에서 N번 노드를 방문할 수 있는지 BFS 알고리즘으로 파악할 수 있다. 이때 항상 오른쪽으로만 이동해야 하므로 유방향 간선 그래프가 됨에 주의해야 한다. - DFS1번 돌부터 시작하며 재귀는 현재 돌보다 숫자가 큰 돌들을 비교하며 방문할 수 있는 돌이면 방문하는 과정을 반복하고 방문 체크를 해줬다. 이후 N번 돌이 방문 체크가 되어있는지 확인하면 간단하게 구현할 수 있다. - 다이나믹 프로그래밍dp 배열은 갈 수 있는 돌을 체크한다. 1번 돌부터 반복.. 2025. 1. 15. [백준] 17128번 - 소가 정보섬에 올라온 이유 [Java] https://www.acmicpc.net/problem/17128 1. 아이디어 다이나믹 프로그래밍을 활용해 합을 미리 구하고 변경하는 방식으로 해결했다.2. 문제풀이 주어진 소들에 대해 4마리의 스티커의 곱을 번호가 작은 소와 매핑시킨 dp 배열을 만든 후 dp 배열의 합을 구했다. 이후 변경할 소의 번호가 주어지면 dp 배열에서 변경해야하는 4마리 점수 4 그룹을 소의 번호로 바로 알 수 있다. 변경은 부호만 바꾸면 되며 부호 변경 후 이전에 구한 dp 배열의 합에서 변경치를 고려해서 수정해주면 된다. 이때 부호가 변경되는 실제 합은 2배 차이가 나게 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static .. 2025. 1. 15. [백준] 15482번 - 한글 LCS [Java] https://www.acmicpc.net/problem/15482 1. 아이디어 이전 LCS 문제에서 문자열이 한글로 주어진 문제로 자바에서는 char 타입으로 한글 문자도 다룰 수 있어서 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 9251번 - LCS [Java])2. 문제풀이 다이나믹 프로그래밍을 활용한 LCS 알고리즘으로 이전 문제와 동일하게 해결했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in.. 2025. 1. 14. [백준] 13711번 - LCS 4 [Java] https://www.acmicpc.net/problem/13711 1. 아이디어 이분 탐색을 활용한 LIS 알고리즘으로 해결할 수 있다.2. 문제풀이 문제 제목이나 설명과 달리 다이나믹 프로그래밍을 활용하는 일반적인 LCS 알고리즘으로 해결하기에는 수열의 크기가 너무 크다.문제 조건이 특이하게 1부터 N까지의 중복되지 않은 수로 이루어진 두 수열의 LCS를 구하라고 나왔는데 이를 LIS 알고리즘으로 치환해서 생각할 수 있다. 두 수열을 한 줄씩 나열한 후 같은 숫자끼리 선을 이으면 마치 전깃줄처럼 연결되어있는데 이때 이 선들이 교차하지 않게 몇 개를 지웠을 때 만들 수 있는 선의 최대 개수와 동일함을 알 수 있다. 선들은 두 수열의 같은 숫자로 이루어져 있으므로 한 수열을 기준으로 숫자를 앞에서부터 .. 2025. 1. 13. [백준] 1958번 - LCS 3 [Java] https://www.acmicpc.net/problem/1958 1. 아이디어 이전 LCS 문제에서 문자열의 개수가 3개가 된 문제로 3차원 dp 배열을 활용하면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 9251번 - LCS [Java])2. 문제풀이 문자열이 하나 추가된만큼 3중 for문과 max를 확인할 위치 하나만 추가하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2025. 1. 13. [백준] 9252번 - LCS 2 [Java] https://www.acmicpc.net/problem/9252 1. 아이디어 이전 LCS 문제에서 실제 문자열 출력이 추가된 문제로 LCS를 구했던 규칙을 통해 dp 배열을 거슬러가며 실제 문자열을 구할 수 있다.([코딩테스트 준비/백준] - [백준] 9251번 - LCS [Java])2. 문제풀이 기존 dp 배열에서 실제 LCS에 포함되는 문자열인 경우 dp[i-1][j-1] + 1로 dp 배열을 갱신했었다. 이를 활용해서 dp 배열의 끝에서 두 포인터를 r, c를 배치하고 출발시켜서 dp[r-1][c] 또는 dp[r][c-1]과 dp[r][c]가 같은 경우 해당 위치는 LCS를 이루지 못했던 경우이므로 해당 위치로 이동하고 dp[r-1][c] 와 dp[r][c-1] 와 다를 경우 해당 위치는 L.. 2025. 1. 13. [백준] 9251번 - LCS [Java] https://www.acmicpc.net/problem/9251 1. 아이디어 문제 이름처럼 다이다믹 프로그래밍을 활용한 LCS 알고리즘으로 해결할 수 있다.2. 문제풀이 두 문자열의 길이만큼 행과 열을 갖는 2차원 dp 배열을 만들어준다.2차원 배열의 두 인덱스는 각 문자열의 문자와 매핑시킬 수 있는데 두 문자가 서로 같을 경우 두 문자가 없었던 dp[i-1][j-1]일 때 LCS의 길이에서 +1 이 되고 두 문자가 서로 다르면 dp[i-1][j]와 dp[i][j-1] 중 큰 LCS를 갖는다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { Buff.. 2025. 1. 13. [백준] 2568번 - 전깃줄 - 2 [Java] https://www.acmicpc.net/problem/2568 1. 아이디어 이전 전깃줄 문제에서 전깃줄의 개수와 위치 번호가 늘어난 문제로 O(N^2) 시간복잡도의 다이나믹 프로그래밍으로는 해결할 수 없다. 이를 위해 이분 탐색을 활용한 LIS로 구현했고 해당 전깃줄을 포함하는 LIS의 길이를 저장하는 before 배열을 활용했다.([코딩테스트 준비/백준] - [백준] 2565번 - 전깃줄 [Java])2. 문제풀이 이전 전깃줄 문제에서 LIS 로직만 이분 탐색을 활용하도록 바꿨다. dp 배열에는 Lower Bound 이분 탐색으로 수열의 해당 수가 들어갈 수 있는 위치를 반환하게 해서 dp 배열을 해당 수로 갱신시켰다. dp 배열은 인덱스 숫자와 같은 길이의 LIS의 마지막 원소가 저장된다. 추.. 2025. 1. 13. 이전 1 2 3 4 다음
