OneMoreEnergyDrink OneMoreEnergyDrink

이 알고리즘은 배열에서 연속된 부분 배열의 구간 합 중 가장 큰 값을 찾는 알고리즘이다.보통 배열에서 최대 연속 구간합을 찾을 때에는 정렬 후 투포인터를 사용하게 되는데,위 알고리즘은 정렬할 수 없는 경우에 유용하게 사용할 수 있다.시간 복잡도는 O(n)이다.카데인 알고리즘의 기본 아이디어현재부분합, 최대부분합 두개의 변수를 사용한다.배열의 각 요소를 순회하면서 현재까지의 최대 부분합을 추적한다.현재 요소를 포함하는 것이 유리한지, 아니면 새로운 부분 배열을 시작하는 것이 더 유리한지를 비교하여 현재 부분합을 업데이트한다.전체 배열을 순회하면서 최대 부분합을 갱신합니다.카데인 알고리즘 구현 (C++)#include #include #include // std::maxint maxSubArraySum(c..

Trie(트라이)는 문자열을 저장하고 효율적으로 검색하기 위한 트리 기반 자료구조이다.트라이 자료구조는 특히 문자열 집합에서 특정 문자열을 빠르게 검색하거나 공통 접두사(prefix)를 찾는 데 효율적이다. 1. Trie의 기본 구조Trie는 트리와 유사한 구조를 가지며, 각 노드는 하나의 문자 또는 값을 나타낸다. 루트 노드(Root Node): Trie의 시작점으로, 비어 있는 상태로 시작한다.자식 노드(Children Nodes): 각 노드는 자식 노드를 가질 수 있으며, 자식 노드는 해당 문자로 이어지는 문자열을 나타낸다.말단 노드(Terminal Node): 특정 문자열의 끝을 표시하는 노드이다. 보통 플래그나 특수한 값을 사용하여 말단 노드를 표시한다.2. Trie의 주요 연산삽입(Insert..

에라토스테네스의 체(Sieve of Eratosthenes)에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 고안한 소수 판별 알고리즘이다.이 알고리즘은 2부터 시작하여 특정 숫자의 배수를 지워 나가는 방식으로 소수를 찾는다.작동 원리 2부터 N까지의 모든 정수를 나열한다. 나열된 정수 중 남아 있는 가장 작은 숫자를 찾고, 이를 소수로 마킹한다.이 숫자의 배수들을 모두 리스트에서 제거한다.리스트에 남아 있는 숫자 중 가장 작은 수를 찾아 위의 과정을 반복한다.리스트에 더 이상 제거할 수가 없을 때까지 반복한다.구현 in C++#include using namespace std;//2~1000까지 소수를 찾아 테이블에 마킹한다#define MAX 1000bool table[MAX+1];int m..

과반수 찾기 알고리즘:n크기의 배열이 주어지고 그 안에는 n/2보다 많이 중복되는 수 x가 존재한다면,그 수를 찾는 알고리즘이다.입력: 정수의 배열 A[n]을 입력으로 받는다ex: {1, 1, 2, 5, 3, 5, 1, 3}출력:A[n]에서 n/2번 이상 나오는 원소가 있다면 그 원소를 출력한다.더보기Brute Force:각 원소마다 자기 뒤에 나오는 횟수를 세어본다.worst case: O(n2)Sorting Method:예시: 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2배열을 정렬함 (시간복잡도 = O(n log n))1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3하나씩 읽고 바로 직전 원소와 같다면 count해서 n/2보다 큰 경우 return. (시간복잡도 = O(n))맨 마..

DFS와 BFS는 그래프를 탐색하는 알고리즘이다.DFS(Depth-First Search)DFS는 그래프를 깊이 우선으로 탐색한다. 즉, 시작 노드에서 시작하여 한 갈래를 끝까지 탐색한 후에 다른 갈래를 탐색한다.구현 방법스택이나 재귀함수로 구현한다.동작 과정시작 노드를 스택에 넣는다.예를 들어, 시작 노드가 A라고 하자. 처음에는 스택에 A만 들어 있다.스택: [A]스택에서 노드를 하나 꺼내어 방문한다.스택에서 A를 꺼내어 방문한다.방문한 노드: A스택: []방문한 노드의 인접 노드 중 방문하지 않은 노드를 스택에 넣는다.예를 들어, A의 인접 노드가 B와 C라면, 이들을 스택에 넣는다.스택: [B, C]스택이 빌 때까지 2-3 단계를 반복한다.다음으로, 스택에서 C를 꺼내어 방문한다.방문한 노드: A..

Knapsack 알고리즘:Knapsack 알고리즘이란 n개의 물건을 배낭에 최대 가치로 넣는 문제이다.배낭에는 무게 수용치가 정해져있다. (ex: 15kg)n개의 물건은 각각 다른 가치와 다른 무게가 정해져있다.위 문제는 물건을 쪼갤 수 있는 경우와 아닌 경우로 나뉜다. (Fraction Knaspack Problem & 0-1 knapSack Problem)0-1 knapSack Problem(쪼갤 수 없는 배낭문제):위 문제는 대표적인 DP 알고리즘 문제이다. (동적계획법)DP 알고리즘이란 큰 하나의 문제를 작은 여러개의 문제로 쪼개어 순차적으로 풀어나가는 방식이다. 위와 같은 경우를 보자.배낭: 최대 15kg물건: ($4, 12kg), ($2, 1kg), ($10, 4kg), ($2, 2kg), (..

Convex Hull:차원 평면에 여러개의 점이 있을 때, 그 점 중 일부를 이어서 나머지 점을 내부에 포함할 수 있는 볼록 다각형을 만드는 알고리즘.볼록 다각형이란 다각형 내부의 두 점을 잇는 어떤 선분도 다각형 외부로 나가지 않는 단순 다각형사전지식:위 문제를 이해하기 위해서는 우선 CCW 알고리즘을 알아야한다.https://qktjwl123.tistory.com/95 알고리즘: CCW(Counter Clock Wise)CCW 알고리즘: 3개의 점 A, B, C가  있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하 알고리즘. 세 점 A(x1, y1), B(x2, y2), C(x3, y3)이 주어졌을 때두 벡터 (x2-x1, y2-y1), (x3-x1, y3-y1)의 외qktjwl1..

우선 유클리드 호제법을 먼저 공부하고 보자!!https://qktjwl123.tistory.com/97 알고리즘: 유클리드 호제법(최대공약수, gcd)유클리드 호제법유클리드 호제법은 두 수 A,B의 최대공약수를 구하는 알고리즘이다.  방법A=0이면 GCD(0,B)=B이므로 GCD(A,B)=B이고 멈춤.B=0이면 GCD(A,0)=A이므로 GCD(A,B)=A이고 멈. A를 A = B⋅Q + R의 형qktjwl123.tistory.com모듈러 역수란?확장 유클리드 알고리즘은 모듈러 역수를 구하는 알고리즘이다.모듈러 역수란 A*B (mod C) = 1이 되게하는 B를 뜻한다. (A와 C는 주어지고 B를 구해야한다.)*모듈러 역수는 A와 C가 서로소일 경우에만 존재한다.*GCD(A, C) = 1인 경우 A (m..