알고리즘

개요 알고리즘 공부를 하면서 비트마스킹이라는 기법이 존재한다는 것을 알았고 자바를 통해서 비트를 어떤식으로 쓸 수 있는지 감을 좀 잡고 비트를 어떻게 사용하고 어떻게 쓸 수 있는지 알아보았다. 본론 비트 마스킹은 말그대로 비트를 사용한 연산들을 의미한다. 비트 연산은 low level 연산이기 때문에 기존의 연산들보다 속도가 높고 메모리 사용량도 훨씬 낮다. 집합 혹은 true/false 대신에 비트 마스킹을 사용할 수 있는 것으로 보이며 자바의 boolean 타입은 1Byte지만 사실 비트 연산으로 이것을 표현하면 1비트로 표현할 수 있다. 집합과 true false 비트 마스킹을 사용해서 집합을 표현할 수 있다. // 공집합 int x = 0; // x 집합에 y 추가 (y비트를 1로 세트한다.) x..

개요 백준 문제를 풀다가 6443번 애너그램 만들기 문제를 백트래킹으로 풀던 중 너무 많은 경우의 수가 존재해서 자바의 힙 메모리가 오바되서 문제를 해결하지 못했습니다. 그래서 어떻게 풀면 될까 고민하다가 Next Permutation 알고리즘이 존재한다는 것을 알았고 문자나 숫자를 나열하는 문제를 더 효율적으로 해결할 수 있을 것 같아서 공부하고 작성합니다. 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 본론 Next Permutation 알고리즘은 현재 나열된 숫자나 문자의 바로 다음 수열을 찾는 ..

트리 그래프에서 두 노드를 선택했을 때 두 노드가 거슬러 올라가면서 부모 노드를 탐색할 때, 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상 (LCA, lowest, coomon ancestor)이라고 합니다. 최소 공통 조상 구하기 최소 공통 조상을 구하는 아이디어는 각 노드의 깊이를 비교하고 두 노드의 깊이를 같도록 만듭니다. 만약 깊이가 같고 값이 다르다면 더 높은 곳으로 올라가야 하기 때문에 두 노드를 같이 부모 노드로 이동합니다. 위의 과정을 부모 노드가 같을 때 까지 반복합니다. 1. BFS, DFS를 통해서 각 노드의 부모 노드와 깊이를 담는 배열을 완성합니다. (인접 리스트) static void BFS(int a){ Queue q = new LinkedList(); q.add(a)..

HTML 삽입 미리보기할 수 없는 소스 세그먼트 트리는 주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태입니다. 핵심 이론 세그먼트 트리의 종류는 구간 합, 최대, 최소 구하기로 나눌 수 있습니다. 구현 단계에서 구현해야 하는 것은 트리를 초기화하기, 질의 값을 구하기, 데이터 업데이트 하기로 나눌 수 있습니다. 1. 트리 초기화 하기 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만듭니다. $2^k≥N$을 만족하는 k의 최솟값을 구하고 $2^{k+1}$ 크기의 트리 배열을 생성하면 됩니다. 또한 리프 노드의 시작 위치를 인덱스로 구해두어야 하는데, 리프 노드의 시작 위치는 $2^k$입니다. 예시 int[] data = {5, 8, 4, 3,..