Algorithm

파스칼의 삼각형이란 ❓ 파스칼의 삼각형(Pascal's Triangle)은 수학에서 사용되는 삼각형 배열로, 각 행은 이항 계수(binomial coefficients)로 구성됩니다. 파스칼의 삼각형은 다음과 같은 규칙이 있습니다. 모든 행은 1로 시작하고 1로 끝납니다각 숫자는 위 양쪽의 숫자를 더한 값입니다n번째 행의 숫자들의 합은 2^n입니다각 행의 숫자들은 해당 행 번호의 조합(nCr)을 나타냅니다 수학적 표현n : 행 번호 (0부터 시작)k : 해당 행에서의 위치 (0부터 시작)파스칼의 삼각형 구현하기 Javaimport java.util.Arrays;public class PascalTriangleDP { public static int[][] generate(int numRows) { ..

백트래킹(Backtracking) 알고리즘이란 ❓백트래킹(Backtracking)은 문제 해결을 위한 탐색 기법 중 하나로, 재귀적 탐색과 되돌리기(backtrack)를 활용하여 최적의 해를 찾는 방법입니다. 많은 최적화 문제, 조합 문제, 순열 문제  등에서 널리 사용되며, 가능한 해를 하나씩 시도하면서 해가 될 것 같지 않으면 더 이상 탐색하지 않고 되돌아갑니다. 여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 합니다. 백트래킹(Backtracking)의 기본 개념백트래킹은 탐색 트리에서 깊이 우선 탐색(DFS) 방식으로 진행되며, 각 노드에서 가능한 모든 선택을 해본 후, 그 선택이 잘못된 경로일 경우에는 다시 되돌아가서 다른 선택을 시도하는 방식입니다.  이..

개요알고리즘 풀이를 하다 보면 소수를 구할 때가 많습니다. 이때, 소수를 구하는 방식은 여러 가지가 있으며, 각각의 방식에 따라 시간 복잡도가 다르게 나타납니다. 가장 기본적인 방법은 O(N)의 시간 복잡도를 가진 소수 판별 함수를 사용하는 것입니다. 이 외에도 제곱근을 활용한 최적화 방법, 그리고 에라토스테네스의 체를 이용한 효율적인 소수 구하는 방법이 있습니다. 본 글에서는 이 세 가지 방법을 차례대로 살펴보겠습니다. 소수(Prime Number)란❓먼저 소수란 1과 자기 자신으로만 나누어 떨어지는 수로  "양의 약수를 두 개만 가지는 자연수"를 의미하며, 2, 3, 5, 7, 11 ... 등이 존재합니다. 기본 소수 판별 함수 (O(N))가장 간단한 방법은 주어진 숫자에 대해 1부터 그 숫자까지의 ..

개요문자열 검색 알고리즘은 두 문자열을 비교하여 특정 패턴이 주어진 텍스트에서 처음 등장하는 위치를 찾거나, 특정 조건을 만족하는 서브스트링을 효율적으로 찾는 데 사용됩니다.  일반적인 문자열 검색은 O(N * M) 복잡도를 가지며, 이는 텍스트의 길이 N과 패턴의 길이 M에 비례하여 비교를 수행하기 때문에 긴 문자열을 다룰 때 비효율적입니다. 이를 개선하기 위해 KMP(Knuth-Morris-Pratt) 알고리즘이 고안되었습니다. 이번 포스팅에서는 KMP(Knuth-Morris-Pratt) 알고리즘에 대해서 정리하고자 합니다. KMP(Knuth-Morris-Pratt) 알고리즘이란❓KMP 알고리즘의 핵심은 pi 배열을 사용해, 패턴 내에서 중복된 접두사와 접미사 정보를 미리 계산하고 이를 활용하여 텍스..