비트마스킹8 [백준] 13701: 중복 제거 - JAVA https://www.acmicpc.net/problem/13701 풀이정수를 입력받으면서 부른적이 없는 정수만 출력하는 문제이다. set자료구조를 생각했지만 메모리 제한때문에 비트마스킹으로 풀어야한다. N의 범위는 2^25로 주어져있다. int범위는 32bit까지 담을 수 있기 때문에 32개의 숫자를 중복검사할 수 있다. 따라서, 2^25개의 수를 중복검사하려면 2^20크기의 배열을 만들어 배열의 원소 한 개가 32개의 숫자를 중복검사하도록 구현해야 한다. `int[] number = new int[1 메모리: 350208KB시간: 1388ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void.. 2024. 5. 18. [백준] 1497: 기타콘서트 - JAVA https://www.acmicpc.net/problem/1497 풀이처음에는 기타마다 연주할 수 있는 곡을 비트마스킹으로 체크하려고 했으나 곡의 개수가 최대 50까지 되기 때문에 int범위에서 비트마스킹을 할 수 없었다. 따라서 boolean 이차원 배열을 만들어 체크했다. N개의 기타로 만들 수 있는 조합을 모두 만들어 연주할 수 있는 곡을 체크해줬다. 비트마스킹을 사용하려고 했던 것이 아쉬워 조합을 만들 때 비트마스킹을 이용했다.for (int i = 1; i 1부터 2의 N제곱까지의 자연수 중 비트의 자리수가 1인 것이 선택된 기타이다. 메모리: 14548KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { .. 2024. 5. 18. [백준] 1062: 가르침 - JAVA https://www.acmicpc.net/problem/1062 풀이배운 알파벳을 체크하기 위해 비트마스킹을 이용했다. 알파벳은 26자인데 int자료형은 2의 31제곱까지 표현이 가능하므로 비트마스킹을 적용할 수 있다. a, n, t, i, c 5개 문자를 -97 해서 숫자로 바꾼 뒤 체크해주었다. K개의 글자를 배울 수 있으므로 조합을 통해 K개를 채워주었다. K개가 되었다면 주어진 단어 중 읽을 수 있는 단어를 카운트해줬다. 메모리: 15216KB시간: 300ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int N, K, ans; static String[] arr; public static .. 2024. 5. 18. [백준] 5638: 수문 - JAVA https://www.acmicpc.net/problem/5638 풀이수문의 유량과 비용이 주어지고 일정 시간 안에 일정 양을 비워야 하는 문제이다. 물 500을 30시간 안에 비우려면 유량 5, 비용 60인 수문을 29시간, 유량 13, 비용 50인 수문을 28시간 열어놓으면 되고, 비용은 110이 된다. 수문의 최대 개수가 20으로 주어져있어서 조합으로 만들어 체크하기로 했다. combination 메서드에 인자로 (수문의 유량 * 주어진 시간)을 더한값을 넘겨서 그 값이 목표 양보다 크면 비용을 비교해주었다. 문제 분류를 열어보니 dp가 써있었는데 이건 어떻게 해야할지 모르겠다... 메모리: 14464KB시간: 140ms언어: Java 11import java.util.*;import java.i.. 2024. 5. 17. [백준] 25688: 빠른 무작위 숫자 탐색 - JAVA https://www.acmicpc.net/problem/25688 풀이1부터 6까지의 숫자를 모두 방문해야하는 문제였다. 비트연산을 이용해 방문한 숫자를 저장했다. 현재 마주친 숫자의 정보와 새로 만난 숫자를 or연산을 통해 하나라도 1이면 1로 되게 했다. 해당 정보를 들고 다음 칸으로 이동한다. 방문처리는 삼차원배열로하여 마주친 숫자까지 고려하여 처리했다. 메모리: 14236KB시간: 132ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int r; int c; int move; int key; public Node(int.. 2024. 5. 17. [백준] 9527: 1의 개수 세기 - JAVA https://www.acmicpc.net/problem/9527 풀이자연수 A부터 B까지 모든 수에 대해 이진수로 표현했을 때 1의 개수를 구해야한다. 자연수의 범위는 10의 16제곱까지였다. 2의 54제곱이 10의 16제곱을 넘어서 이진수로 54자리수까지 담는 배열을 만들었다.dp[i] = (dp[i - 1] 배열의 점화식은 위와 같다. i자리수는 i-1자리수의 모든 경우의 앞에 1을 붙이면 되기 때문이다. B까지의 개수에서 A-1까지의 개수를 빼주면 정답이다. 하지만 예를 들어 자연수 14가 주어지면 3자리까지의 개수를 더하고 나머지를 더 구해줘야 한다. 이진수들을 써본 결과 규칙을 찾았고 다음과 같은 식으로 계산할 수 있었다.return dp[digit - 1] + diff + count(n - .. 2024. 5. 12. [백준] 2800: 괄호 제거 - JAVA https://www.acmicpc.net/problem/2800 풀이브루트포스 문제. 괄호의 쌍을 매칭하여 출력하거나 출력 안 하거나 하면 되는 문제였다. 서로의 짝을 매칭 시킬 방법으로 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택의 제일 위에 있는 괄호와 짝을 맺는다. 서로의 짝의 번호를 배열에 저장했다. 짝을 모두 저장한 후 dfs 탐색을 통해 해당 괄호를 boolean 배열에 true, false로 체크하여 출력할지 안 할지를 저장했다. 중복 식을 제거하기 위해, 사전 순으로 정렬하기 위해 TreeSet을 이용했다. 메모리: 24900KB시간: 280ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12. [백준] 16938: 캠프 준비 - JAVA https://www.acmicpc.net/problem/16938 풀이비트마스크를 이용해 조합을 만드는 문제였다. 조합을 만들어 문제의 조건들을 비교해주었다. 비트마스크 조합int N = 3;int[] arr = {1, 2, 3}for(int i = 1; i 공집합을 제외하고 1~7까지 탐색한다. 예를 들어 6을 탐색하면 2진수로 6은 110이므로 배열에서 1번, 2번 인덱스의 값을 꺼낸다. 메모리: 14288KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader b.. 2024. 5. 11. 이전 1 다음