프로그래밍 이론/알고리즘

1.  다익스트라 알고리즘다익스트라 알고리즘은 그래프 상에서 한 정점으로부터 모든 다른 정점까지의 최단 경로를 계산하는 알고리즘이다. 매번 최단 경로를 가진 정점을 선택하여, 이를 반복적으로 탐색함으로써 출발 정점에서 나머지 모든 정점으로의 최단 경로를 찾는다. 단, 모든 링크의 가중치는 양의 값이어야 한다.최단 경로를 구하는 방법으로는 다익스트라 외에도 벨만-포드, 플로이드-워셜 알고리즘이 존재한다. 경로 계산 방식은 크게 세 가지가 있다.한 지점에서 다른 특정 지점까지의 경로를 찾는 방식(One-to-One).한 지점에서 모든 다른 지점까지의 경로를 구하는 방식(One-to-All).모든 지점에서 모든 지점까지의 경로를 찾는 방식(All-to-All)이다. 다익스트라 알고리즘은 이 중 두 번째 유형인..

1. 동적 계획법이란? 동적 계획법(Dynamic Programming)은 주어진 문제를 작은 부분 문제로 분할하고, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘 기법이다. 특히 부분 문제의 수가 기하급수적으로 증가할 때 유용하다. 분할 정복법과는 달리, 중복되는 부분 문제의 결과를 재활용하여 속도를 높인다.각 부분 문제가 서로 독립적일 때: 분할 정복법 사용.부분 문제가 중복될 때: 동적 계획법 사용.2. 메모이제이션이란?메모이제이션(Memoization)은 계산 결과를 저장해두고, 동일한 계산이 다시 필요할 때 저장된 값을 사용하는 최적화 기법이다. 이를 통해 중복 계산을 방지하고 속도를 향상시킬 수 있다. 메모리를 사용해 계산 시간을 줄이는 방식이다.3 - 1. 메모이제이션의 활용: 이항 계수..

정의 중국인의 나머지 정리(The Chinese Remainder Theorem, CRT)는 여러 개의 서로 다른 소수인 모듈러(moduli)에 대해 독립적으로 주어진 나머지들을 만족하는 정수를 찾는 문제를 해결하는 수학적 정리입니다. 이 정리는 시스템의 일련의 동시 합동식(congruences)을 하나의 합동식으로 표현할 수 있게 해 줍니다. 중국인의 나머지 정리는 서로 다른 모듈러 \( m_1, m_2, \ldots, m_n \)가 서로 소일 때 (즉, \( \gcd(m_i, m_j) = 1 \) 일 때, \( i \neq j \)) 아래와 같은 연립 합동식에 대하여 해를 찾는 정리입니다 \( x \equiv a_1 \mod m_1 \) \( x \equiv a_2 \mod m_2 \) \( x \e..

정수론은 수학의 한 분야로서, 정수와 관련된 다양한 수학적 성질을 연구합니다. 이 분야는 기본적인 정수의 나눗셈부터 시작하여, 소수, 이차 형식, 다항식의 정수 해, 그리고 숫자의 분할과 같은 복잡한 주제까지 포괄합니다. 정수론은 수학 이론뿐만 아니라 컴퓨터 과학, 암호학, 그리고 수많은 응용 과학 분야에서도 중요한 역할을 합니다. 소수의 패턴, 정수들 사이의 관계, 그리고 숫자들의 이론적 특성을 탐구함으로써, 이 분야는 근본적인 수학적 이해를 제공합니다. 1. 유클리드 호제법 유클리드 호제법은 두 양의 정수의 최대공약수를 찾는 알고리즘입니다. 간단하면서도 매우 빠르게 최대공약수를 구할 수 있기 때문에, 컴퓨터 과학에서도 널리 사용되는 알고리즘 중 하나입니다. 구현 방식 두 수 a와 b (a > b)가 ..

단어 검색 알고리즘 단어 검색 알고리즘은 대규모 문자열 데이터에서 특정 단어나 문장을 효율적으로 찾기 위해 필요합니다. 작은 데이터셋에서는 각 문자열을 순차적으로 검사하는 브루트 포스 방법으로 충분할 수 있으나, 수만 또는 수백만 개의 데이터가 있는 경우 이 방법은 비효율적입니다. 이런 상황에서 단어 검색 알고리즘은 필수적으로, 이는 문자열 데이터 처리의 효율성을 크게 향상시키는 데 중요한 역할을 합니다. 트라이(Trie) 알고리즘 트라이는 문자열 집합을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 트라이의 주요 특징은 다음과 같습니다. 효율적인 검색: 대규모 데이터셋에서도 문자열의 길이에 비례하여 빠른 검색이 가능합니다. 공간 최적화: 공통 접두사를 공유하는 문자열들이 경로를 공유함으..