알고리즘 문제 해결: ACM 천재
수학적 분석
이 문제의 중요한 성질은 다음과 같습니다: 만약 \(0<a<b<c<d\)라면, \((a-d)^2+(b-c)^2 > (a-c)^2+(b-d)^2\)
증명:
두 식을 각각 1식과 2식으로 설정합니다.
\((a-d)^2+(b-c)^2 = a^2+b^2+c^2+d^2-2ad-2bc\), \((a-c)^2+(b-d)^2 = a^2+b^2+c^2+d^2-2ac-2bd\)
\(a*(c-d) > b*(c-d)\)이므로, \(-2ad-2bc > -2ac-2bd\)
따라서 \(a^2+b^2+c ...
9월 1일 05:07에 게시됨
2차원 편순 문제를 활용한 레몬의 행복도 계산
레몬 나무에 n개의 레몬이 매달려 있으며, 각각은 두 가지 속성인 시각적 아름다움(a_i)과 신맛 강도(b_i)를 가진다. 특정 레몬 i를 섭취했을 때 얻는 기쁨 값 e_i는 자기 자신을 제외하고, 아름다움과 신맛 모두가 자신 이하인 다른 레몬들의 개수로 정의된다.
즉, 다음 조건을 동시에 만족하는 인덱스 j의 수이다:
j ≠ i
a_j ≤ a_i
b_j ≤ b_i
모든 레몬에 대해 ...
8월 4일 07:24에 게시됨
정렬 알고리즘 시각화
1. 직접 삽입 정렬 (Direct Insertion Sort)
이미 정렬된 배열에 새 데이터를 삽입하는 방식으로 작동합니다. 첫 번째 두 수를 정렬한 후 순차적으로 추가하여 전체 배열을 정렬합니다.
핵심 아이디어: 이미 정렬된 n-1개의 요소에 대해 새로운 요소를 삽입하여 전체 배열을 정렬합니다.
코드 구현:
public void insertSort(int[] arr) {
int len = arr.length;
f ...
8월 3일 00:13에 게시됨