알고리즘

밀러라빈소수판별법

오일러 피 함수

분할 정복을 이용한 거듭제곱

수치해석

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다.하노이 탑은 세 개의 기둥과 크기가 다른 원반들로 이루어진 수학적 게임입니다. 게임의 목표는 한 기둥에 쌓여있는 원반들을 다음의 규칙에 따라 다른 기둥으로 옮기는 것입니다:한 번에 하나

이진 탐색은 정렬된 배열에서 중간값을 기준으로 절반씩 나눠가며 탐색하는 기법으로, $O(\\log_2 n)$의 시간 복잡도를 가집니다. 이진 탐색은 정렬된 배열에서만 사용 가능하고, 반복문과 재귀함수로 구현할 수 있습니다.위와 같은 배열에서 이진 탐색을 사용하여 7 이

어떤 수 $n$을 연속된 자연수의 합으로 표현할 수 있는 개수를 구하는 문제입니다. 예를 들어 15의 경우$$1 + 2 + 3 + 4 + 5\\7 + 8\\15$$로 나타낼 수 있습니다. 이 문제는 투 포인터로 풀 수 있습니다. $start$와 $end$를 증가시키거나

구간 합 알고리즘은 n차원 배열에서 구간 합을 구하는 알고리즘으로 누적 합 배열을 빌드할때는 $O(n)$, 구간 합을 구할때는 $O(1)$의 시간복잡도를 가집니다.예를 들어 다음과 같은 배열이 있다고 합시다.이때 2번~4번의 합을 구하면, 5 + 6 + 7 = 18 입

동적 계획법은 부분 문제들의 해를 결합하여 문제를 해결하는 최적화 방법으로, 문제를 서로 겹치지 않는 부분 문제들로 분할한 후에 재귀적으로 해결한 다음, 이 해들을 결합하여 원래의 문제를 해결하는 방법입니다. 분할 정복 알고리즘이 공유되는 부분 문제를 반복적으로 해결하

DFS는 노드와 간선으로 이루어진 그래프에서 깊이를 우선으로 탐색하는 알고리즘 기법으로, 재귀함수와 해시테이블을 통해 구현할 수 있습니다. 만약 노드가 1~6까지 있고 간선이 다음과 같이 존재한다고 하면,$$(1, 6)\\(1, 3)\\(1, 2)\\(3, 4)\\(4

위상 정렬은 방향 비순환 그래프에서 어떠한 노드가 탐색되려면 그 이전 노드가 모두 탐색되어야 할 때 탐색하는 순서를 알 수 있는 알고리즘입니다. 예를 들어 다음과 같은 상황에서 사용할 수 있습니다.E과목을 수강하기 위해 C과목, C과목을 수강하기 위해 A, B, D과목

다익스트라 알고리즘은 가중치 간선으로 연결된 그래프에서 최단 경로를 찾는 알고리즘으로, 그리디 알고리즘과 다이나믹 프로그래밍을 결합한 형태입니다. 시간 복잡도는 O(간선의 수 X log 노드의 수) 입니다. 다익스트라 알고리즘의 로직은 다음과 같습니다.costs 배열을

유니온 파인드 알고리즘은 같은 전체집합에 속하나, 원소가 겹치지 않는 서로소 집합(Disjoint-set)에서 집합을 합치거나, 같은 집합에 속하는지를 판별하는 것에 효율적인 알고리즘입니다. 유니온 파인드는 집합을 1차원 배열에서 인덱스를 통해 관리합니다. 처음은 모든

강한 연결 요소(SCC)는 자신을 출발하여 어떠한 경로를 통하여 자신으로 돌아올 수 있는 정점들의 집합입니다. 예를 들어 다음과 같은 그래프에서, SCC는 다음과 같습니다.노드 A, B, C에서는 어디서 출발하더라도 자신으로 돌아올 수 있습니다. F, E 도 마찬가지입

2-SAT 문제는 여러개의 절(Clause)로 이루어진 논리식이 성립할 수 있는지를 판별하는 문제로, 적어도 두개의 절이 주어졌을 때를 의미합니다. $$(a\\vee b)\\wedge (\\sim b \\vee a)\\wedge (b\\vee c)$$이 식에서, $a

이들은 모두 정렬 알고리즘 중에 최악의 경우 시간복잡도가 $O(n^2)$인 정렬 알고리즘입니다.버블 정렬은 앞의 값과 뒤의 값을 비교하여 교환하는 방식의 정렬 방식입니다. 버블 정렬의 특성상, 끝부터 정렬되기 때문에 비교 횟수는 $\\displaystyle\\frac{

계수 정렬은 데이터의 범위가 1000000 이하일 때 효율적으로 사용할 수 있는 알고리즘으로, 시간 복잡도는 O(데이터의 개수 + 데이터의 최대값)입니다. 계수 정렬의 로직은 다음과 같습니다.정렬된 인덱스의 배열을 만들고 0으로 초기화한다.데이터가 들어올 때, 데이터와

퀵 정렬은 분할정복법(divide & conquer) 알고리즘으로 일반적으로 $O(n\\log_2 n)$의 시간복잡도를 가지고, 최악의 상황(모두 정렬된 상태)에서 $O(n^2)$의 시간복잡도를 가집니다.퀵 정렬에서는 Pivot과 Low, High 라는 포인터를 사용하

병합 정렬은 분할 정복 기법으로 정렬하는 알고리즘으로, 하나의 배열을 중간을 기준으로 계속 나눠서 계속 합치면서 정렬하는 방법입니다. 퀵 정렬의 경우에는 최악의 경우(모두 정렬되어 있는 경우) $O(n^2)$의 시간복잡도를 가질 수 있지만 병합 정렬은 어떠한 배열에서도

세그먼트 트리는 Range Query (Update, Sum, Max, Etc…)를 처리하는데 효율적인 자료구조로, 완전 이진 트리이며 인덱스 트리이기 때문에 1차원 배열으로 표현되는 트리입니다. 인덱스는 1부터 시작하며 자식 노드는 2 n, 2 n + 1 번 인덱