icodesiuuuu 님의 블로그

유클리드 호제법은 두 수의 최대공약수(Greatest Common Divisor, GCD)를 계산하는 가장 효율적인 알고리즘입니다. 이를 활용하면 두 숫자의 최소공배수(Least Common Multiple, LCM)도 쉽게 구할 수 있습니다. 유클리드 호제법의 원리유클리드 호제법은 다음 성질을 이용합니다:두 수 A와 B의 최대공약수는, A와 B를 나눈 나머지(A%B)의 최대공약수와 같습니다.즉, GCD(A , B) = GCD(B , A%B)이 과정을 반복하여 나머지가 0이 되었을 때, 그 나누는 값이 최대공약수입니다.예시: A=24, B=3624%36=24, 따라서 GCD(24,36) = GCD(36,24)36%24=12, 따라서 GCD(36,24) = GCD(24,12)24%12=0, 따라서 GCD(..

투 포인터 (Two Pointers) 알고리즘이란?투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 특정 조건을 만족하는 부분 구간을 빠르게 탐색하기 위해 사용하는 효율적인 알고리즘 기법입니다. 주로 정렬된 배열이나 리스트에서 연속된 부분 수열을 찾거나 특정 합을 구하는 문제에서 자주 활용됩니다. 이 방법은 두 개의 포인터를 사용하여 탐색을 진행하며, O(n)의 시간 복잡도를 제공하여 대량의 데이터를 효율적으로 처리할 수 있습니다. 투 포인터의 동작 원리투 포인터 알고리즘은 보통 두 가지 포인터를 사용하여 배열의 시작점과 끝점 또는 배열의 특정 부분을 탐색합니다. 이 두 포인터는 보통 다음과 같이 동작합니다:포인터의 초기화:하나의 포인터는 배열의 시작 위치(start)에, 다른 포인터는 ..

이진탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾기 위해 사용하는 효율적인 알고리즘입니다. 시간 복잡도가 O(logn)이기 때문에 데이터가 많아질수록 유리합니다. 이진탐색은 배열의 중간 요소와 목표 값을 비교하고, 범위를 절반씩 줄여가며 검색을 반복합니다.이진탐색 동작 과정중간값 선택: 배열의 중간에 위치한 값을 선택합니다.비교: 선택된 중간값과 찾고자 하는 값을 비교합니다.만약 값이 같으면 찾기 성공.값이 작으면 중간값 기준 왼쪽 절반만 확인.값이 크면 중간값 기준 오른쪽 절반만 확인.반복: 범위를 좁혀가며 중간값을 반복적으로 선택하고 비교합니다. public class BinarySearchExample { public static void main(String[] args) ..

Kadane 알고리즘은 주어진 배열에서 연속된 부분 배열의 합이 가장 큰 값을 효율적으로 찾는 알고리즘. 이 알고리즘은 동적 프로그래밍(Dynamic Programming)의 일종으로, 선형 시간 복잡도 O(n)을 가지기 때문에 큰 배열에서도 빠르게 최대 합을 구할 수 있다.배열의 두 번째 요소부터 마지막 요소까지 반복하면서, 각 요소에서 maxCurrent를 현재 요소와 maxCurrent + 현재 요소 중 더 큰 값으로 갱신maxGlobal을 maxCurrent와 비교하여 더 큰 값으로 업데이트예시public class KadaneAlgorithm { public static int main(String[] args) { int[] example = {-2, 1, -3, 4, -1,..