백준133 [백준 1509] 팰린드롬 분할 / 자바 / dp(팰린드롬) #문제 레벨: G1알고리즘: dp(팰린드롬)풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1509#문제 풀이 팰린드롬 문자열의 정의: 처음 ~ 끝으로 읽으나 끝 ~ 처음으로 읽으나 같은 문자열1. 팰린드롬 판별 배열palindrom[i][j](i ~ j까지 팰린드롬인지)을 저장한다. 2. 이중 for 문을 돌며 dp[i]값을 저장한다. dp[i] =1 ~ i까지 탐색했을 때 최소 팰린드롬 문자열의 조합 예시)초기화:dp[0] = 0, dp[1~4] = MAXend = 1 ("A" 까지):start = 1: "A"는 팰린드롬dp[1] = min(MAX, dp[0] + 1) = min(MAX, 0 + 1) = 1dp: [0, 1, MAX, .. 2025. 2. 6. [백준 17404] RGB거리 2 / 자바 / dp #문제 레벨: G4알고리즘: dp풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/17404#문제 풀이 dp에서 중요한 것은 아래와 같습니다.1. 상태의 정의2. 점화식의 정의bottom-up방식으로 점화식을 세워보겠습니다.현재 상태에서 가장 최솟값임을 보장하려면, 현재 색깔 + 이전색깔 중 최솟값이어야 합니다. 점화식으로 나타내면dp[i][0] = cost[i][0] + Math.min(dp[i-1][1],dp[i-1][2]);dp[i][1] = cost[i][1] + Math.min(dp[i-1][0],dp[i-1][2]); dp[i][2] = cost[i][2] + Math.min(dp[i-1][0],dp[i-1][1]); 입니다.dp[i.. 2025. 2. 5. [백준 1256] 사전 / 자바 / 조합 #문제 레벨: G2알고리즘: 조합, dp풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1256 #문제 풀이 이 문제에서 얻어갈 점은 두가지입니다.1. 조합을 계산하는 방법(일반 계산, dp로 표현)2. 문제 해결 아이디어문제 해결 아이디어부터 설명드리겠습니다. 문제를 보자마자 모든 알파벳 조합을 만들어 보는 것은 시간제한이 걸린다는 것을 직감할 수 있습니다. 그렇다면 저희가 해야 할 일은 앞에 놓을 수 있는 글자들을 놓아보는 것입니다. 앞에 a가 올려면 a~~~~에 문자열이 K번 째 문자열이 포함된다는 거고 앞에 z가 올려면 z~~~~에 k 번째 문자열이 포함된다는 겁니다.다르게 설명드리면, a~~~~에 놓을 수 있는 경우의 수가 .. 2025. 2. 1. [백준 2169] 로봇 조정하기 / 자바 / dp #문제 레벨: G5알고리즘: dp 풀이시간: 20분 힌트 참조 유무: 유https://www.acmicpc.net/problem/2169 #문제 풀이 Top-down DP (DFS + DP):재귀를 사용메모이제이션(기존에 계산한 값을 저장)큰 문제를 작은 문제로 나누어 해결주로 @(재귀 + 메모이제이션) 방식으로 구현Bottom-up DP:반복문을 사용작은 문제부터 차례대로 해결반복문으로 점화식 구현테이블을 채워나가는 방식// top-downint fibonacci(int n) { if (dp[n] != -1) return dp[n]; if (n #풀이 코드 import java.io.*;import java.util.*;public class Main .. 2025. 2. 1. [백준 2629] 양팔저울 / 자바 / dp #문제레벨: G3알고리즘: dp풀이시간: 1:20힌트 참조 유무: 유https://www.acmicpc.net/problem/2629#문제 풀이**첫 번째 접근: 실패처음 보자마자 **브루트 포스로 시간 복잡도가 통과되는지 확인했습니다. 구슬의 조합으로 해당 숫자를 잴 수 있는지 확인하려면, 숫자들의 플러스 마이너스의 조합입니다. 예를 들어 설명하겠습니다.아래 4개의 숫자 사이에 + 혹은 - 를 대입하고 합을 구하면 측정할 수 있는 무게가 됩니다. 만약 모두 -로 값이 음수라면 절대값을 씌우면 됩니다. 모두가 +인 값과 동일하기 때문입니다. 이 방식의 최악의 시간복잡도를 따져보면, 빈칸의 들어갈 조합의 경우의 수이기 때문에 2^30(N 최대값) 입니다. 1,024 x 1,024 x 1,024 = 1,00.. 2025. 1. 24. [백준 2098] 외판원 순회 / 자바 / TSP(dp + 비트마스킹 + dfs) #문제레벨: G1알고리즘: dp + 브루트 포스 + 비트 마스킹풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2098#문제 풀이TSP(Traveling Salesman Problem)시간 복잡도 O(n^2 * 2^n)이 문제는 전형적인 TSP 문제입니다. 한 노드에서 출발하여 모든 노드를 순회하고 다시 시작점으로 돌아오는데 최소값을 구하는 문제가 TSP입니다.TSP 문제를 가장 무식하게 푸는 방법은 모든 경우의 수를 다 탐색해보는 것입니다. 모든 경우의 수를 탐색해보는 것은 N!인데, 알고리즘에서 가장 나쁜 경우의 수가 N!입니다.저희는 DP를 사용해야 합니다. 큰 문제를 작은 문제로 쪼갠다. N = 3 일 때를 가정하면 아래와 같은 경우의 수가 있습니다.1.. 2025. 1. 23. [백준 2186] 문자판 / 자바 / dp + dfs #문제 레벨: G3알고리즘: dp + dfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/2186#문제 풀이 처음 문제를 봤을 때 별 생각없이 아래와 같이 dfs 코드를 짰다. 코드는 문제에 맞게 구현됐다. 단지, 시간 초과가 날 뿐이다...잠시 이 dfs 코드를 흝어봐주고 내려와주라.dfs코드import java.io.*;import java.util.*;public class Main { static int N, M, K; static char[][] board; static String word; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, .. 2025. 1. 22. [9663] N-Queen , 자바 , dfs(백트래킹) 1. 문제레벨: G4알고리즘: dfs(백트래킹)풀이시간: 30분힌트 참조 유무: 유https://www.acmicpc.net/problem/96632. 문제 풀이실패 시도:서로 공격하지 않는 경우의 수로 구하려고 하였으나 N^2 C N 의 시간 복잡도가 나왔습니다. 이는 한 눈에 봐도 큰 경우의 수 입니다. 아무리 백트래킹을 한다그래도 N = 15, 시간제한 = 10초 안에 불가능할 거라 판단하였습니다.전체 경우의 수 - 서로 공격하는 경우 로 구하려고 하였으나 서로 공격하는 경우에서 2 ~ N이 서로 공격하는 경우를 구할 때 중복이 발생함으로 중복을 해결하는 과정이 너무 복잡해보였습니다. 잘못된 방법인 냄새실패 원인: N^2 C N에 대한 오해N^2 C N은 "N^2개의 칸에서 N개의 퀸을 선택하여 .. 2025. 1. 19. [백준 1799] 비숍 / 자바 / 백트래킹 + 분할정복 #문제레벨: G1알고리즘: 백트래킹 + 분할정복풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1799#문제 풀이완전탐색을 할 경우 2의 100승으로 무조건 시간초과입니다. 그렇다 하면 조금 더 긍정적으로 생각해보겠습니다. 흰색칸 비숍과 검정칸 비숍은 서로 영향을 줄 수 없습니다. 그래서 우린 흰색칸 비숍과 검정칸 비숍을 나누어서 탐색하게 된다면2^50 + 2^50 으로 아까보다 나아졌습니다. 그래도 우린 시간초과에 걸립니다. 그렇다면 우리에겐 dp가 남아있습니다. 위 문제를 dp로 풀 경우를 생각하면 비트마스킹 dp을 생각해볼 수 있습니다. 이차원배열을 100자리의 비트마스킹으로 표현하는 것입니다. 그러나 대각선의 겹치는 비숍이 있는지 검사하기에는 까다로울 .. 2025. 1. 18. 이전 1 2 3 4 ··· 15 다음
