|a - b| = |c - d| 절대값 차이가 같은 경우 활용하기

두 값의 차이의 절대값이 서로 같은 경우 수학에서는 |a - b| = |c - d| 와 같이 표현한다.

해당 개념을 잘 숙지하고 있으면 아래와 같이 다양한 상황에서 이 개념을 활용할 수 있다.

 

1. 기하학적 관계 파악

• 예: N-Queen 문제에서 대각선 관계 확인
• 응용: 격자 기반 게임, 경로 찾기 알고리즘

위의 그림과 같이 행간 차이와 열간 차이가 동일한 경우 점 A, 점 B는 동일 대각선상에 놓인다는 것을 알 수 있다.

해당 경우를 N-queen 문제에서 대각선상에 말이 놓이는 경우의 예외를 처리할 때 사용할 수 있다.

ex ) if(Math.abs(x2 - x1) == Math.abs(y2 - y1))

 

 

• A* 알고리즘에서 대각선 이동 비용 계산
• 로봇 내비게이션에서 장애물 회피 경로 계산

 

double calculateHeuristic(int x1, int y1, int x2, int y2) {

    int dx = Math.abs(x2 - x1); int dy = Math.abs(y2 - y1);

    int diagonalSteps = Math.min(dx, dy);

    int straightSteps = Math.max(dx, dy) - diagonalSteps;

    return diagonalSteps * Math.sqrt(2) + straightSteps;

}

 

2. 시간 간격 분석

• 예: 이벤트 간의 일정한 시간 간격 확인
• 응용: 스케줄링 알고리즘, 시계열 데이터 분석

이벤트 간의 시간 간격이 일정한지 확인을 확인하고 싶은 상황에서도 활용될 수 있다.

ex)

boolean isConstantInterval(long[] timestamps) {
    if (timestamps.length < 3) return true;
    long interval = Math.abs(timestamps[1] - timestamps[0]);
    for (int i = 2; i < timestamps.length; i++) {
        if (Math.abs(timestamps[i] - timestamps[i-1]) != interval) {
            return false;
        }
    }
    return true;
}

3. 패턴 인식

• 예: 문자열에서 반복되는 패턴 찾기
• 응용: 데이터 압축, 암호학

ex) "abcabcabcabc"와 같은 문자열에서 반복되는 가장 짧은 패턴 찾기 (|s[i] - s[i+k]| == 0 (여기서 k는 패턴의 길이))

String findPattern(String s) {
    for (int k = 1; k <= s.length() / 2; k++) {
        if (s.length() % k == 0) {
            boolean isPattern = true;
            for (int i = 0; i < s.length() - k; i++) {
                if (s.charAt(i) != s.charAt(i + k)) {
                    isPattern = false;
                    break;
                }
            }
            if (isPattern) {
                return s.substring(0, k);
            }
        }
    }
    return s;
}

 

4. 균형 잡힌 구조 확인

• 예: 이진 트리의 균형 상태 검사
• 응용: 데이터 구조 최적화, 네트워크 토폴로지 분석

ex) 트리가 균형을 이루는지 확인하기 (모든 리프 노드의 깊이 차이가 1 이하) 

깊이 차이의 절대값이 1이하인지 확인 : |depth(leftSubtree) - depth(rightSubtree)| <= 1

class TreeNode {
    TreeNode left, right;
    int val;
}

boolean isBalanced(TreeNode root) {
    return checkBalance(root) != -1;
}

int checkBalance(TreeNode node) {
    if (node == null) return 0;

    int leftHeight = checkBalance(node.left);
    if (leftHeight == -1) return -1;

    int rightHeight = checkBalance(node.right);
    if (rightHeight == -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) return -1;

    return Math.max(leftHeight, rightHeight) + 1;
}