본문 바로가기
반응형

problemsolving5

[알고리즘/Algorithm] 유클리드 호제법 Euclidean Algorithm / BOJ 2609 최대공약수와 최소공배수 안녕하세요!이번에는 수학 알고리즘 중 최대공약수, 최소공배수를 구할 때 활용할 수 있는 '유클리드 호제법'에 대해서 정리해보려고 합니다 :)알고리즘이 수학과 관련이 높은 만큼 종종 접하는 문제 유형인 듯 합니다. 수학 알고리즘이 생각보다 정수론이나 특정 이론과 관련있는 경우가 많아서인지,수학 공부를 하지 않은 상태에서는 떠올리기가 쉽지 않은 경우도 종종 있습니다.이렇게 문제 풀면서 정리해보는 것도 좋을 듯 하여,수학 알고리즘 중 하나인 '유클리드 호제법'도 정리해봅니다 !! 유클리드 호제법 Euclidean Algorithm유클리드 호제법은두 수의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘 으로,나눗셈을 반복해 계산하며 최대공약수를 찾습니다. 두 수 a, b (단, a ≥ .. 2025. 4. 17.
[알고리즘/Algorithm] 동적계획법 Dynamic Programming / BOJ 9095 1, 2, 3 더하기 & BOJ 2839 설탕 배달 안녕하세요!이번에는 바로! 알고리즘 문제풀이(Algorithm Problem Solving)의 꽃이라고 불리는 동적 계획법에 대해서 정리해보려고 합니다 :0분할정복이나 수학 관련 알고리즘을 먼저 공부할까 했는데, 문제를 풀어나가다 보니 DP에 대해서 먼저 정리하고 싶어졌습니다 ㅎㅎ 난이도가 있는 문제가 꽤 많이 나와서, 이 김에 정리해두려고 합니다!ㅎㅎ동적계획법(Dynamic Programming) 이란?먼저 동적계획법(Dynamic Programming; 다이나믹 프로그래밍)이 무엇일까요?동적계획법은 복잡한 문제를 작은 부분으로 나누고, 이를 저장하여 중복 계산을 줄이는 기법입니다.즉, 분할정복과 비슷하지만 중복되는 부분의 결과값을 저장하고 재사용하는 과정이 추가된 것입니다. ■ DP를 사용하는 경우중.. 2025. 3. 26.
[알고리즘/Algorithm] 소수 판별 - 에라토스테네스의 체 / Sieve of Eratosthenes / BOJ 4948 베르트랑 공준 예제 풀이 안녕하세요,이번에는 소수 판별 알고리즘인 '에라토스테네스의 체'에 대해서 포스팅 해 보려고 합니다 !에라토스테네스의 체 (Sieve of Eratosthenes)에라토스테네스의 체는 여러 개의 수 중에서 소수를 빠르게 찾아내는 알고리즘입니다. 소수란?1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. 예를 들어, 2, 3, 5, 7, 11, 13, 17 등은 소수입니다. ◆ 기본 원리 1. 2부터 N까지의 모든 숫자를 소수라고 가정합니다.2. 가장 작은 소수(2)부터 배수를 제거하여 소수가 아닌 숫자를 지웁니다.3. 남아 있는 숫자들이 소수가 됩니다. 위와 같은 기본 원리를 바탕으로 소수 판별 알고리즘을 구현합니다. 예를 들어, N = 30까지의 소수를 찾는다고 하면, 아래와 같은 과정으로 소수를.. 2025. 2. 20.
[알고리즘/Algorithm] 이분 탐색(이진 탐색) / Binary Search Algorithm 이론 정리 및 예제 풀이 알고리즘 문제풀이를 공부하면서, 역시나 정리가 필수라는 생각이 계속 들었습니다!차근차근 정리해보겠습니다 :)이번에는 이분 탐색(이진 탐색) 인 Binary Search에 대해 정리해보겠습니다. 이분 탐색(이진 탐색) / 바이너리 서치(Binary Search) 알고리즘이란?이분 탐색은 '두 영역으로 나눠서 탐색'하는 탐색 방법 입니다.정렬된 데이터에서 원하는 값을 빠르게 찾는 알고리즘인데요,데이터를 반 씩 나눠서 탐색하기 때문에 검색 속도가 매우 빠르며 대규모 데이터 처리에 적합합니다.배열에서 특정 원소를 찾아야 할 때, 배열의 길이가 너무 길 경우 (원소 개수가 너무 많을 경우)에는배열의 모든 원소를 확인하는 작업이 굉장히 오래걸릴 수 있습니다.그럴 때, 두 영역을 비교해서 타겟 원소의 '영역'을 찾아.. 2025. 2. 4.
반응형

티스토리툴바