전체 글270 Bitset 자료구조란 Bitset이란BitSet은 비트를 효율적으로 저장하고 조작할 수 있는 자료구조입니다.Bitset 사용 이유1. 메모리 효율boolean[]은 실제로는 한 요소당 1바이트 이상 사용되지만,BitSet은 64개의 비트를 long 1개에 담아 8바이트로 처리합니다.👉 즉, 대량의 true/false 값을 다룰 때 훨씬 가볍습니다.2. 성능비트 연산 (|, &, ^)을 통해 대량의 boolean 값을 한 번에 계산할 수 있어 빠릅니다.예: bitset1.and(bitset2) → 배열 전체를 순회하면서 동시에 AND 처리3. 개발자 실수 줄여줌Java는 정수 타입을 이용한 직접적인 비트 연산보다 BitSet을 사용할 때 더 읽기 쉽고 안전한 코드를 작성할 수 있게 해줍니다.컴파일러가 bitIndex 음수 체.. 2025. 4. 4. [백준 1949] 우수 마을 / 자바 / dp #문제레벨: G4알고리즘: dp풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/1949#문제 풀이3개의 노드를 부모노드 - 자식노드 관점에서 보면 케이스는 위와 같이 4가지로 나누어집니다. 우린 dp를 자신의 노드가 우수마을인지 아닌지 나눠서 생각해봐야 합니다.dp[N][2] = 자식 노드 포함해서 현재 노드의 최고의 인원 수dp[i][0] = 자신이 우수노드가 아닐 때dp[i][1] = 자신이 우수노드일 때케이스2를 보면 자식 노드 2와 3은 서로가 우수마을이든지 아니든지 상관이 없습니다.즉, 옆 자식노드는 상관하지 않아도 된다는 것입니다.dp[i][1]은 자신이 우수노드인 경우이므로 케이스 1과 같이 자식들이 모두 우수노드가 아닌 경우의 수를 더해줘야합니다.. 2025. 2. 11. [백준 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. [백준 1562] 계단 수 / 자바 / dp + 비트마스킹 #문제레벨: G2알고리즘: dp + 비트마스킹풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1562#문제 풀이dfs를 풀어야 한다는 건 어렴풋 짐작할 수 있다. 그러나 N= 100일 때, 100 자리에 10개(0 ~ 9)를 넣는다고 생각하면10 ^ 100 의 작업 수가 필요하다. 당연히 이렇게 해서는 안된다. dfs 풀이가 확고할 때는 dp 도입을 생각해본다.위 그림을 보면 뒤에 들어갈 정답인 숫자들이 중복되는 것을 확인할 수 있다. 이미 왼쪽 숫자로 빈칸에 숫자를 구했다면 오른쪽 숫자를 구할 때 또 빈칸을 구할 필요가 있겠는가? 없다. 전에 구한 경우의 수를 사용하면 된다.https://jsw5913.tistory.com/169이 문제에 들어가서 상태 저장.. 2025. 1. 23. [백준 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. 이전 1 2 3 4 ··· 30 다음
