세그먼트 트리(Segment Tree)란 세그먼트 트리(Segment Tree)는 효율적으로 배열 또는 리스트와 같은 순차적인 데이터 구조에서 구간 쿼리(구간 검색 또는 구간 연산)를 수행하기 위한 자료구조입니다. 주로 구간 합, 구간 최솟값, 구간 최댓 값 등을 빠르게 계산하는데 사용됩니다. 세그먼트 트리는 트리 구조로 표현되며, 각 노드는 배열의 일부 구간에 대한 정보를 저장합니다. 일반적으로 이진 트리 형태를 가지며, 아래와 같은 구성요소를 가집니다. 루트 노드 : 배열 전체 구간에 대한 정보를 저장합니다. 각 내부 노드 : 두 자식 노드의 구간 정보를 합친 결과를 저장합니다. 이를 통해 트리를 아래로 내려가면서 구간 정보를 계산할 수 있습니다. 리프 노드 : 배열의 개별 원소를 나타냅니다. 세그먼..
비트마스크 (BitMask) 란 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다. 비트(bit) 용어 그대로 비트와 관련된 내용이라고 생각하면 편하다. 비트는 0, 1값을 갖고 이를 false/true 또는 off/on 라는 상태를 나타내기도 한다. 이를 흔히 말하는 이진법을 사용하는 것을 의미한다. 비트마스크의 장점 1. 수행 시간이 빠르다. 비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다. 다만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없..
이전에 해쉬란 무엇인가에 대해서 정리를 하였지만, 또 정리를 더 자세하게 해보고 이번 포스팅에서는 직접 기능까지 구현해보자 https://superohinsung.tistory.com/113 [Algorithm] Hash(해시) 란 Hash 란? 해시란 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것이다. 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 superohinsung.tistory.com 해쉬 테이블 이란 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조이다. 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산할수 있으며, Key를 통해 바로 데이터가 저장되어 ..
소수(Prime Number) 소수란 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자의 곱(2×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 에라토스테네스의 체 소수를 빨리 찾을 수 있는 알고리즘이다. 과정 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 자기 자신을 제외한 2의 배수를 모두 지운다. 자기 자신을 제외한 3의 배수를 모두 지운다. 자기 자신을 제외한 5의 배수를 모두 지운다. 자기 자신을 제..
최대공약수(GCD, Greatest Common Divisor) 최대 공약수란 두 자연수의 공통된 약수 중 가장 큰 수 이다. 두 개 이상의 정수의 최대공약수는 해당 정수들의 공통된 약수 중 가장 큰 값이다. 예를 들어, 8과 12의 최대공약수는 4 이다. 최소 공배수(LCM, Least Common Multiple) 최소 공배수란 두 자연수의 공통된 배수 중 가장 작은 수이다. 두 개 이상의 정수의 최소공배수는 주어진 정수들 중에서 모든 정수가 동시에 나누어 떨어지는 가장 작은 정수이다. 예를 들어, 8과 12의 최소공배수는 24이다. 유클리드 알고리즘 유클리드 알고리즘은 두 정수의 최대공약수를 구하는데 사용되는 알고리즘이다. 두 정수 a와 b에 대해서, a를 b로 나눈 나머지를 구하고, 그 나머지를 ..
최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 주어진 수열에서 요소들이 증가하는 순서대로 선택되는 가장 긴 부분 수열을 말한다. 즉, 주어진 수열에서 원래 순서를 유지하면서 순서대로 증가하는 숫자들을 선택하여 만들 수 있는 가 장 긴부분 수열을 찾는 문제이다. 예를 들어 수열 {3, 1, 5, 2, 4}가 주어졌을 때, 이 수열의 최장 증가 부분 수열은 {1, 2, 4}가 된다. 이 부분 수열은 원래 수열의 순서를 유지하면서 각 요소가 증가하는 순서대로 선택되었기 때문에 최장 증가 수열 부분이라고 할 수 있다. 최장 증가 부분 수열은 다이나믹 프로그래밍(DP)와 이분탐색을 이..
동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming, DP)란 컴퓨터 프로그래밍 기법 중 하나로, 주로 최적화 문제나 중복되는 부분 문제를 효율적으로 해결하는 데 사용되는 알고리즘 설계 기법이다. 이는 큰 문제를 작은 부분 문제로 쪼개어 해결하는 분할 정복(Divide and Conquer)과 유사하지만, DP는 중복되는 부분 문제들을 한 번만 계산하고 이를 이용하여 전체 문제를 해결한다. 즉,한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘. -> 점화식을 요구하는 이유이기도 하다. DP의 핵심 아이디어는 "작은 문제들의 해를 저장하고 재활용함으로써 전체 문제의 해를 구하는 것"이다. 이를 통해 중복 계산을 피하고 실행 시간을 크게 줄일 수 있습니다..
이번에는 자바에서 큐를 사용해보자. 이전에 큐는 무엇인가에 대하여 공부했다. https://superohinsung.tistory.com/178 [DataStructure] 큐(Queue) feat. C, Java 자료구조 큐에 대해서 정리를 해보자. 큐(Queue)란 큐(Queue)는 컴퓨터 과학에서 사용되는 선형적 자료구조 중 하나이다. 큐는 데이터를 일시적으로 저장하거나 관리하는데 사용되며, 데이터를 먼 superohinsung.tistory.com Java Queue 클래스 java.util 패키지에서 Queue 클래스 제공 메서드 소개 boolean add(E e): 큐의 끝에 요소를 추가한다. 큐가 가득 찬 경우 예외(IllegalStateException)를 발생시킨다. boolean off..
