비트마스킹5 [프로그래머스] 150367번 - 표현 가능한 이진트리 [Java] https://school.programmers.co.kr/learn/courses/30/lessons/150367 문제 설명 당신은 이진트리를 수로 표현하는 것을 좋아합니다. 이진트리를 수로 표현하는 방법은 다음과 같습니다. 이진수를 저장할 빈 문자열을 생성합니다.주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.문자열에 저장된 이진수를 십진수로 변환합니다.이진트리에서 .. 2025. 2. 22. [소프티어] 6251번 - 업무 처리 [Java] https://softeer.ai/practice/6251 1. 아이디어 각 직원에 대해 왼쪽 직원한테 받은 업무와 오른쪽 직원한테 받은 업무를 구분해야 한다. 이를 위해 두 개의 Queue를 갖는 노드 클래스를 활용했고 주어진 트리의 루트를 1로 설정한 후 비트마스킹을 활용했다. 업무의 전달은 부서장부터 말단 직원 순으로 진행된다는 점에 주의해야한다.2. 문제풀이 완전이진트리인데 말단 직원과 부서장까지의 올라가는 거리가 같으면 포화이진트리가 된다. 이를 통해 가장 왼쪽 말단 직원의 번호와 가장 오른쪽 말단 직원의 번호를 비트마스킹으로 구해서 변수로 저장했다. 이후 말단 직원에게 업무들을 부여했다. R일까지의 반복은 부서장 일처리 -> 중간 직원 일처리 -> 말단 직원 일처리 순서로 진행되며 역시 비트.. 2025. 2. 6. [백준] 1094번 - 막대기 [Java] https://www.acmicpc.net/problem/1094 1. 아이디어 이 문제는 1부터 64 사이의 2의 제곱수로 X를 만드는 문제와 동일한 문제가 된다. 64부터 1까지 반복문을 통해 제곱수의 개수를 세는 방식으로 간단하게 해결할 수 있고 비트마스킹을 활용해 X를 2진수로 나타냈을 때 1의 개수를 세는 방식으로도 해결할 수 있다.2. 문제풀이 기본 구현은 for문의 인덱스를 2로 나눠가며 1의 개수를 세도록 구현했고, 비트마스킹의 경우 bitCount 메서드로 1인 비트의 개수를 간단하게 셀 수 있다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 2. 4. [백준] 1987번 - 알파벳 [Java] https://www.acmicpc.net/problem/1987 1. 아이디어 DFS 알고리즘과 Set을 활용한 방문체크로 간단하게 해결할 수 있고 칸이 알파벳으로만 이루어져있어서 비트마스킹을 활용한 방문체크로도 해결할 수 있다.2. 문제풀이 DFS 탐색 과정에서 다른 노드 가지 탐색을 위해 방문 체크를 해제하는 점만 주의해서 구현하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main_DFS { private static final int[] dr = {-1, 0, 1, 0}; private static final int[] dc = {0, 1, 0, -1}; private static int R; private s.. 2025. 2. 2. [백준] 11723번 - 집합 [Java] https://www.acmicpc.net/problem/11723 1. 아이디어 집합을 구현하는 문제로 Set 자료구조를 활용한 구현과 비트마스킹을 활용한 구현 두가지 방식을 활용했다.2. 문제풀이 switch 문으로 연산 종류에 맞게 연산을 수행하도록 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWrit.. 2025. 2. 2. 이전 1 다음
