🔗 3 x n 타일링🔎 점화식$f(n) = f(n-2) * f(2) + f(n-4) * 2 + f(n-6) * 2 + ... + f(2) * 2 + 2$class Solution { static int MOD=1000000007; public int solution(int n) { long [] dp = new long [n+1]; // 초기 값 dp[2] = 3; for(int i = 4; i
🔗 등굣길🔎 Dynamic Programming작은 문제를 통해 큰 문제 해결 가능(i, j)의 값을 구하려면 이전 칸들의 값(dp[i-1][j], dp[i][j-1])을 이용하여 구할 수 있음중복계산 많음dp[i][j]에 최단 경로의 개수를 저장해 재사용최적 부분 구조문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있음(i, j)로 가는 경로의 개수는 (i-1, j)와 (i, j-1)에서의 경로 개수만 알면 구할 수 있음점화식 기반의 계산웅덩이인 경우 dp[i][j]=0나머지 dp[i][j]=dp[i-1][j]+dp[i][j-1]class Solution { static int MOD=1000000007; static int[][]dp; public int solution(in..
🔗2 x n 타일링class Solution { // Dynamic Programming public int solution(int n) { // 모듈러 값 int MOD = 1000000007; // dp 배열 초기화 if (n == 1) return 1; if (n == 2) return 2; // 동적 계획법 배열 초기화 int[] dp = new int[n + 1]; dp[1] = 1; // n = 1 dp[2] = 2; // n = 2 // 점화식에 따라 dp 계산 for (int i = 3; i
재귀적으로 문제를 해결하되 상태가 제한조건에 위반되는지 판단확인 중인 상태가 제한 조건에 위배된다면 그 상태 이후의 탐색을 하지 않고 다음 단계로 탐색을 진행함🔍 백트래킹 vs. DFS(Depth First Search)공통점원하는 값을 찾기 위해서 탐색하는 알고리즘차이점백트래킹 : 불필요한 탐색을 하지 않고 조건에 맞지 않으면 더 이상 탐색을 진행하지 않음, 확인해야하는 경우의 수 줄일 수 있음DFS : 모든 경우의 수를 탐색[ 프로그래머스 ] #1835 : 단체사진 찍기 - JAVA
🔗단체사진 찍기import java.util.ArrayList;import java.util.List;class Solution { static char[]friends={'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'}; static int count =0; public int solution(int n, String[] data) { //{조건을 제시한 프렌즈}~{상대방}{=,}{두 프렌즈 사이 사른 프렌즈의 수} //모든 조건을 만족할 수 있도록 서는 경우의 수를 계산 count =0; boolean[]visited=new boolean[friends.length]; List arrange=new ..
🔗카카오 프렌즈 컬러링북import java.util.*;class Solution { public int[] solution(int m, int n, int[][] picture) { // 방문 체크 배열 boolean[][] visited = new boolean[m][n]; int[] result = new int[2]; // 결과 저장 [영역 수, 최대 영역 크기] // 모든 좌표 탐색 for (int i = 0; i queue = new LinkedList(); queue.offer(new int[]{cx, cy}); visited[cx][cy] = true; int[] dx = {1, ..
