세그먼트 트리(Segment Tree)란 세그먼트 트리(Segment Tree)는 효율적으로 배열 또는 리스트와 같은 순차적인 데이터 구조에서 구간 쿼리(구간 검색 또는 구간 연산)를 수행하기 위한 자료구조입니다. 주로 구간 합, 구간 최솟값, 구간 최댓 값 등을 빠르게 계산하는데 사용됩니다. 세그먼트 트리는 트리 구조로 표현되며, 각 노드는 배열의 일부 구간에 대한 정보를 저장합니다. 일반적으로 이진 트리 형태를 가지며, 아래와 같은 구성요소를 가집니다. 루트 노드 : 배열 전체 구간에 대한 정보를 저장합니다. 각 내부 노드 : 두 자식 노드의 구간 정보를 합친 결과를 저장합니다. 이를 통해 트리를 아래로 내려가면서 구간 정보를 계산할 수 있습니다. 리프 노드 : 배열의 개별 원소를 나타냅니다. 세그먼..
비트마스크 (BitMask) 란 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다. 비트(bit) 용어 그대로 비트와 관련된 내용이라고 생각하면 편하다. 비트는 0, 1값을 갖고 이를 false/true 또는 off/on 라는 상태를 나타내기도 한다. 이를 흔히 말하는 이진법을 사용하는 것을 의미한다. 비트마스크의 장점 1. 수행 시간이 빠르다. 비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다. 다만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없..
소수(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의 핵심 아이디어는 "작은 문제들의 해를 저장하고 재활용함으로써 전체 문제의 해를 구하는 것"이다. 이를 통해 중복 계산을 피하고 실행 시간을 크게 줄일 수 있습니다..
배낭 문제(knapsack) 냅색 알고리즘이란 Knapsack Problem, 배낭문제는 다이나믹 프로그래밍에서 매우 유명한 문제이다. 조합 최적화(Combination Optimization) 문제 중 하나로, 주어진 공간(배낭)에 최대 가치를 가지는 물건들을 선택하는 문제이다. 일반적으로 배낭에 넣을 수 있는 총 무게(용량)가 주어지고, 물건의 무게와 해당 물건을 배낭에 넣을 때의 가치가 주어진다. 배낭 문제에는 크게 2가지의 유형이 있다. 0/1 배낭 문제(0/1 Knapscak Problem) 이 유형에서는 각 물건을 배낭에 넣을지(1) 또는 넣지 않을지(0)를 결정해야한다. 즉, 각 물건은 배낭에 한 번만 들어갈 수 있다. 이러한 제약 때문에 0/1 이라는 이름이 붙었다. 이 유형의 배낭 문제는..
오늘은 재귀에 대해서 알아보자. 재귀(Recursion) 란 사전적 의미 : 본디의 곳으로 다시 돌아오는 것. 즉, 재귀함수란 함수내에서 자기 자신을 호출하는 함수를 의미한다. 이미지 출처 : https://medium.com/@sunnkis/%EB%8D%B0%EC%9D%B4%ED%84%B0-%EA%B5%AC%EC%A1%B0-%EC%9E%AC%EA%B7%80-8d96633be4cd [데이터 구조] 재귀 재귀란 ? medium.com 재귀 함수를 호출하면 재귀 탈출 조건이 없다면 무한반복으로 함수를 호출한다. 예시) #include void Recusive(int num){ if(num
