본문 바로가기

비트마스크4

[알고리즘 문제풀이] 프로그래머스 - 2개 이하로 다른 비트 / JAVA(자바) https://programmers.co.kr/learn/courses/30/lessons/77885 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr /** 1. f(x) 는 x보다 큰 수 중 비트가 1~2개사이에서 다른 것 중 제일 작은 수 2. 현재 수의 비트 중에서 제일 작은 꺼져있는 비트 찾기 2-1) 전체 켜진 비트와 현재 비트를 xor연산 비트 만들고, 2-2) 만들어진 비트 중 가장 최소로 켜진 비트를 찾으면 그게 제일 작은 꺼져잇는 비트 3. 꺼져있는 비트를 키고, 이게 최소비트가 아니면 오른쪽꺼는 끈다. 3-1) 꺼져있는 비트를 키는건, 찾은 비트를 합집합하면 됨. 3-2) 바로 오른쪽꺼를 끄는건 2진수니까 /2로 하면 바로 한칸 옆 오른쪽임. ~를 통해 해당 .. 2022. 2. 27.
[알고리즘 개념] 펜윅 트리(Fenwick Tree,Binary Indexed Tree) / JAVA 펜윅트리는 세그먼트 트리를 변형한 버전이므로, 세그먼트 트리를 먼저 알아야 이해가 잘 됩니다! 2022.01.17 - [Algorithm/개념] - [알고리즘 개념] 세그먼트 트리(Segment Tree) / Java 그리고 비트 단위로 연산하기 때문에, 비트 연산자를 알아야합니다! 2022.01.14 - [Algorithm/개념] - [알고리즘 개념] 비트마스크(Bitmask) 펜윅트리란(Fenwick Tree, Binary Indexed Tree, BIT) 세그먼트 트리에서 메모리를 절약한 트리. 시간복잡도 O(MlogN) 데이터 변경: O(logN) 연산: O(logN) 공간복잡도 O(N) 펜윅트리는 세그먼트 트리에서 우측 노드를 지운 트리입니다. 만약 5~7까지의 합을 알고 싶다면, 1~7까지의 .. 2022. 1. 17.
[알고리즘 개념] 비트마스크(Bitmask) 비트 마스크를 설명하기 앞서, 비트를 알아야한다. 잘 알면 아래부터 보면 됨! 더보기 비트(Bit) 컴퓨터는 이진수를 통해서 모든 자료를 표현한다. 여기서 사용하는 이진수가 데이터의 최소 단위 Bit(binary Disit)이다. 비트는 0 또는 1의 값을 가지며, n개의 비트는 2^0~2^n-1까지 표현 가능하다. 1 = 2^0 = 1 10 = 2^1 = 2 100 = 2^2 = 4 111 = 2^2+2^1+2^0 = 7 3자리의 비트는 1~2^n-1 까지 표현가능 비트 연산자 및 용어 정리 최상위 비트(MSB): 2^n-1 비트 최하위 비트(LSB): 2^0 비트 비트가 켜져있다: 1 비트가 꺼져있다: 0 int는 4byte 총 32비트로 되어있다. ( 최상위 비트는 부호비트 1: -, 0:+) in.. 2022. 1. 14.
[알고리즘 문제풀이] 백준 13701 중복제거(JAVA) https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net /** * 입력값 500만 * 입력데이터 2^25 * * 실패함 ㅠ * * 비트마스크 풀이 * * 1. 비트셋 활용 풀이 * * 입력값을 받으면서, * 현재 데이터가 비트셋에 없었으면 비트셋 표기 및 출력 * 있었으면 패스 * * 2. 배열 + 비트 마스크 * * 배열을 비트셋같이 쓸거임 arr * * int 자료형은 2.. 2022. 1. 13.

티스토리툴바