최대공약수 및 확장 유클리드 알고리즘: ICPC 문제 풀이 및 개념 복습
최대공약수(GCD)의 원리
gcd(x, y)와 gcd(y, x % y)가 동일한 이유는 다음과 같습니다.
x와 y의 최대공약수를 d라고 가정합니다.
x = m * d, y = n * d라고 하면,
x % y = x - (x / y) * y가 됩니다.
이때 x / y는 정수 나눗셈 결과입니다.
x % y = m * d - (x / y) * n * d = (m - (x / y) * n) * d
따라서 x % y도 d의 배수입니다.
즉, x와 y의 공약수는 y와 x % y의 공 ...
7월 25일 04:37에 게시됨
알고리즘 문제 해결 전략 및 동적 계획법 심화
나무 심기 문제
문제 설명
일직선 위에 서로 다른 위치에 n 그루의 나무가 심어져 있습니다. 각 나무의 위치는 정수 ai로 주어집니다.
기존 나무의 위치를 변경할 수 없지만, 새로운 나무를 추가로 심어 모든 나무(기존 나무와 새로 심은 나무 모두 포함)의 위치를 정렬했을 때, 인접한 나무들 사이의 간격이 모두 동일하도록 만들고 싶습니다. 새로 심는 나무의 위치도 정 ...
7월 18일 01:44에 게시됨
Codeforces Round 991 (Div. 3) F - 구간 최대公约수와 차분 배열
문제 접근
이 문제는 구간 내에서의 최대公约수(GCD) 값을 구하는 문제이다. 핵심 아이디어는 차분(difference) 배열을 활용하는 것이다. 원래 배열에서 인접한 요소들의 차이를 구하면, 해당 구간의 GCD는 차분 배열의 특정 구간 GCD와 동일해진다.
따라서 우리는 구간 GCD를 효율적으로 구할 수 있는 자료구조를 사용하면 된다. 두 가지 대표적인 방법을 소개한다.
방 ...
7월 10일 06:27에 게시됨