[카테고리:] 자바 코딩테스트 강좌

문제 설명

N명의 도시를 가진 세일즈맨이 있고, 이 세일즈맨은 모든 도시를 한 번씩 방문하고 다시 출발 도시로 돌아와야 합니다.
세일즈맨은 각 도시 간의 거리 정보가 주어지며, 최단 경로를 찾는 것이 목표입니다.
이 문제를 해결하기 위해서는 백트래킹, 동적 프로그래밍 또는 비트마스크를 이용한 최단 경로 탐색 알고리즘을 사용할 수 있습니다.

입력 형식

첫째 줄에는 도시의 개수 N이 주어진다. 이어서 N x N 크기의 행렬이 주어지며,
matrix[i][j]는 도시 i에서 도시 j까지의 거리를 나타낸다.
단, matrix[i][i]는 항상 0이다.

출력 형식

세일즈맨이 모든 도시를 한 번씩 방문하고 출발지로 돌아오기 위한 최소 비용을 출력한다.

예제

    입력:
    4
    0 10 15 20
    10 0 35 25
    15 35 0 30
    20 25 30 0

    출력:
    80
    

문제 풀이 과정

본 문제는 전형적인 외판원 문제(TSP, Traveling Salesman Problem)로,
세일즈맨이 모든 도시를 방문한 뒤 출발지로 돌아오는 가장 짧은 경로를 찾는 문제이다.
이 문제는 NP-완전 문제로, 도시의 수가 많아질수록 해를 찾기 위한 계산량이 기하급수적으로 증가한다.
이에 따라 여러 가지 접근 방법을 고려할 수 있다.

1. 백트래킹(Backtracking)

백트래킹은 모든 경로를 탐색하는 방식으로, 재귀적으로 모든 가능한 경로를 탐색하며
최적의 경로를 찾는 방식이다. 하지만 도시의 수가 커질수록 계산 시간이 늘어난다.

2. 동적 프로그래밍(Dynamic Programming)

동적 프로그래밍을 이용한 방법은 메모이제이션 기법을 활용하여 이미 계산된 경로의 최단 거리 값을 저장
해 중복 계산을 방지하는 방법이다.
이 방법론에 따라 특정 도시 집합에 대한 최소 비용을 저장하고
서브 문제를 해결하여 전체 문제의 해결책을 구성한다.

3. 비트마스크(Bitmasking)

비트마스킹은 도시 각각을 비트로 표현하여 모든 방문 상태를 관리하는 기법이다.
이를 통해 세일즈맨이 어떤 도시를 방문했는지를 효율적으로 관리할 수 있다.
이 방법은 동적 프로그래밍과 조합하여 사용할 때 매우 효과적이다.

알고리즘 구현

1. 비트마스킹을 이용한 동적 프로그래밍

    
    import java.util.Arrays;

    public class TravelingSalesman {
        static final int INF = Integer.MAX_VALUE;
        static int[][] dist;
        static int[][] dp;
        static int n;

        public static void main(String[] args) {
            // 입력 예시
            n = 4; // 도시의 개수
            dist = new int[][] {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
            };

            // DP 배열 초기화
            dp = new int[n][1 << n];
            for (int[] row : dp) {
                Arrays.fill(row, -1);
            }

            // 최단 경로 계산
            int result = tsp(0, 1);
            System.out.println("최소 비용: " + result);
        }

        static int tsp(int pos, int mask) {
            if (mask == (1 << n) - 1) { // 모든 도시를 방문한 경우
                return dist[pos][0]; // 시작 도시로 돌아감
            }

            if (dp[pos][mask] != -1) {
                return dp[pos][mask]; // 메모이제이션된 값 반환
            }

            int ans = INF;

            // 모든 도시를 순회
            for (int city = 0; city < n; city++) {
                if ((mask & (1 << city)) == 0) { // 도시를 방문하지 않았다면
                    ans = Math.min(ans, dist[pos][city] + tsp(city, mask | (1 << city)));
                }
            }

            return dp[pos][mask] = ans; // 현재 상태 메모이제이션
        }
    }
    
    

결론

본 문제는 세일즈맨이 모든 도시를 한 번씩 방문하고 다시 출발 도시로 돌아오는 최단 경로를 찾는 대표적인
경로 최적화 문제로, 다양한 알고리즘으로 접근 가능하다.
비트마스킹과 동적 프로그래밍을 활용한 이번 구현은 도시 수가 적을 경우 빠른 계산이 가능하며,
다수의 도시를 처리하기 위한 다른 기법의 사용도 가능하다.
이와 같은 문제를 통해 알고리즘적 사고를 기르는 것이 중요하며,
코딩 면접 대비와 실제 프로젝트에서도 매우 유용하게 사용될 것이다.

참고 문헌

• Introduction to Algorithms, Thomas H. Cormen 등의 저서
• Online Resources on Dynamic Programming and Traveling Salesman Problem

문제 정의

주어진 범위 내에서 소수이면서 팰린드롬인 수들 중에서 최솟값을 찾는 문제입니다. 소수는 1과 자기 자신만을 약수로 갖는 자연수를 의미하며, 팰린드롬은 앞뒤가 똑같은 수를 의미합니다. 예를 들어, 121은 팰린드롬 수이고 131, 151, 181, 191도 소수이며 팰린드롬입니다.

문제 접근 방법

이 문제를 해결하기 위해 다음과 같은 단계를 거칠 것입니다:

1. 주어진 범위 내에서 소수를 찾는 방법을 구현합니다.
2. 찾은 소수들 중에서 팰린드롬 수를 확인하는 방법을 구현합니다.
3. 팰린드롬인 소수들 중에서 최솟값을 찾습니다.

1단계: 소수를 찾는 함수 구현

소수를 찾기 위해 간단한 소수 판별 알고리즘을 사용할 수 있습니다. 이 알고리즘은 어떤 숫자가 다른 숫자들로 나누어 떨어지지 않는지 확인함으로써 소수를 판별합니다. 아래는 Java로 구현한 소수 판별 코드입니다.

public class PrimeUtil {
        public static boolean isPrime(int number) {
            if (number <= 1) return false;
            for (int i = 2; i <= Math.sqrt(number); i++) {
                if (number % i == 0) return false;
            }
            return true;
        }
    }

2단계: 팰린드롬 확인 함수 구현

팰린드롬 수를 확인하기 위해 문자열로 변환하고, 원래 문자열과 반전 문자열이 같은지를 비교하는 방법을 사용할 수 있습니다. 이를 Java로 구현한 코드는 다음과 같습니다.

public class PalindromeUtil {
        public static boolean isPalindrome(int number) {
            String str = Integer.toString(number);
            String reversedStr = new StringBuilder(str).reverse().toString();
            return str.equals(reversedStr);
        }
    }

3단계: 최솟값 찾기

소수이면서 팰린드롬인 수들을 찾은 후, 이들 중에서 최솟값을 찾는 코드를 작성합니다. 이 부분의 코드 또한 Java로 구현하도록 하겠습니다.

import java.util.ArrayList;
    import java.util.List;

    public class MinPrimePalindromeFinder {
        public static int findMinPrimePalindrome(int start, int end) {
            List<Integer> primePalindromes = new ArrayList<>();
            for (int i = start; i <= end; i++) {
                if (PrimeUtil.isPrime(i) && PalindromeUtil.isPalindrome(i)) {
                    primePalindromes.add(i);
                }
            }
            if (primePalindromes.isEmpty()) {
                return -1; // 소수이면서 팰린드롬인 수 없음
            }
            return primePalindromes.stream().min(Integer::compare).get();
        }
    }

전체 코드

이제 우리가 구현한 모든 부분을 하나의 프로그램으로 통합해보겠습니다. 아래는 최종적으로 작성된 코드입니다.

public class Main {
        public static void main(String[] args) {
            int start = 10;
            int end = 200;
            int minPrimePalindrome = MinPrimePalindromeFinder.findMinPrimePalindrome(start, end);
            if (minPrimePalindrome != -1) {
                System.out.println("소수이면서 팰린드롬인 수들 중 최솟값: " + minPrimePalindrome);
            } else {
                System.out.println("주어진 범위 내에 소수이면서 팰린드롬인 수가 없습니다.");
            }
        }
    }
    

테스트 케이스

다음과 같은 범위를 테스트해 볼 수 있습니다:

• 범위: 10 ~ 200 (결과: 101)
• 범위: 1 ~ 1000 (결과: 101)
• 범위: 101 ~ 150 (결과: 131)
• 범위: 200 ~ 300 (결과: 없음)

결론

이번 포스트에서는 자바를 사용하여 소수이면서 팰린드롬인 수들 중 최솟값을 찾는 문제를 해결하는 방법에 대해 알아보았습니다. 소수 판별 알고리즘과 팰린드롬 체크를 각각 구현한 후, 이를 결합하여 최종적으로 원하는 결과를 얻어냈습니다. 문제를 해결하기 위해 구현한 코드와 함께, 테스트 케이스를 통해 정확성을 검증해 보았습니다.

소수 및 팰린드롬 문제는 알고리즘 시험에서 종종 출제되는 주제이므로, 이러한 문제를 해결하는 방식은 다른 유사한 문제들에도 응용될 수 있습니다. 여러분도 이 글을 참고하여 문제를 해결하는 데 도움을 얻으시기 바랍니다.

참고 자료

• Prime Number – Wikipedia
• Palindrome – Wikipedia
• Java Program to Check if a Number is Prime
• Java Program to Check if a String is Palindrome

안녕하세요! 이번 글에서는 자바를 사용한 코딩테스트에서 유용하게 쓰일 수 있는 알고리즘 중 하나인 세그먼트 트리에 대해 알아보겠습니다. 세그먼트 트리는 주로 구간 쿼리와 구간 업데이트를 효율적으로 처리하기 위해 사용됩니다. 이 글에서는 세그먼트 트리의 기본 개념과 이에 대한 예제 문제, 그리고 그 문제의 해결 과정을 자세히 설명드리겠습니다.

세그먼트 트리란?

세그먼트 트리는 배열에서 특정 구간의 정보를 저장하고 쿼리를 효율적으로 처리하기 위한 데이터 구조입니다. 주로 다음과 같은 작업을 지원합니다:

• 지정한 구간의 합을 구하기
• 지정한 위치의 값을 업데이트 하기
• 구간의 최솟값, 최댓값을 구하기

세그먼트 트리는 O(log n) 시간에 쿼리를 처리할 수 있으며, 공간 복잡도는 O(n)입니다. 이를 통해 대규모의 데이터를 효과적으로 다룰 수 있습니다.

문제 소개

이제 ‘세그먼트 트리’를 활용한 문제를 하나 풀어보겠습니다.

문제 설명

주어진 정수 배열이 있을 때, 특정 구간의 합을 구하고, 특정 인덱스에 있는 값을 업데이트 하는 두 가지 기능을 제공하는 프로그램을 작성하세요.

구현해야 하는 기능은 다음과 같습니다:

1. 구간 합 쿼리: 두 인덱스 l과 r가 주어지면, l과 r 사이의 합을 반환합니다.
2. 업데이트 쿼리: 인덱스 index의 값을 value로 업데이트 합니다.

입력 형식

첫 번째 줄: 배열의 크기 n (1 ≤ n ≤ 10^5)
두 번째 줄: n개의 정수 (1 ≤ arr[i] ≤ 10^9)
세 번째 줄: 쿼리의 수 q
다음 q줄: 쿼리는 두 가지 형식 중 하나입니다:
    1. 1 l r (구간 합 쿼리)
    2. 2 index value (업데이트 쿼리)

출력 형식

구간 합 쿼리에 대한 결과를 한 줄씩 출력합니다.

문제 해결 과정

1. 세그먼트 트리 구현

먼저 세그먼트 트리를 구현해야 합니다. 세그먼트 트리는 비상위 노드로부터 리프 노드까지의 합을 저장하는 방식으로 구성됩니다. 이를 위한 배열 tree를 선언하고, 트리를 구축하는 메소드를 작성하겠습니다.

java
public class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[n * 4];
        buildTree(arr, 0, 0, n - 1);
    }

    private void buildTree(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            buildTree(arr, node * 2 + 1, start, mid);
            buildTree(arr, node * 2 + 2, mid + 1, end);
            tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
        }
    }

    // 구간 합 쿼리 메소드
    public int rangeSum(int l, int r) {
        return rangeSumHelper(0, 0, n - 1, l, r);
    }

    private int rangeSumHelper(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0; // 쿼리 범위가 노드 범위와 겹치지 않음
        }
        if (l <= start && end <= r) {
            return tree[node]; // 노드 범위가 쿼리 범위에 포함됨
        }
        int mid = (start + end) / 2;
        int leftSum = rangeSumHelper(node * 2 + 1, start, mid, l, r);
        int rightSum = rangeSumHelper(node * 2 + 2, mid + 1, end, l, r);
        return leftSum + rightSum;
    }

    // 업데이트 메소드
    public void update(int index, int value) {
        updateHelper(0, 0, n - 1, index, value);
    }

    private void updateHelper(int node, int start, int end, int index, int value) {
        if (start == end) {
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (start <= index && index <= mid) {
                updateHelper(node * 2 + 1, start, mid, index, value);
            } else {
                updateHelper(node * 2 + 2, mid + 1, end, index, value);
            }
            tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
        }
    }
}

2. 메인 프로그램

세그먼트 트리 클래스를 포함하여 입력을 받아 쿼리를 처리하는 메인 프로그램을 작성하겠습니다.

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        SegmentTree segmentTree = new SegmentTree(arr);
        
        int q = scanner.nextInt();
        for (int i = 0; i < q; i++) {
            int type = scanner.nextInt();
            if (type == 1) { // 구간 합 쿼리
                int l = scanner.nextInt();
                int r = scanner.nextInt();
                System.out.println(segmentTree.rangeSum(l, r)); 
            } else if (type == 2) { // 업데이트 쿼리
                int index = scanner.nextInt();
                int value = scanner.nextInt();
                segmentTree.update(index, value);
            }
        }
        
        scanner.close();
    }
}

3. 시간 복잡도 분석

세그먼트 트리의 시간 복잡도는 다음과 같습니다:

• 구간 합 쿼리: O(log n)
• 업데이트 쿼리: O(log n)

따라서, n개의 데이터를 가진 배열에서 q개의 쿼리를 처리하면 총 O(q log n) 시간 복잡도를 가집니다.

맺음말

이번 강좌에서는 세그먼트 트리에 대해 자세히 알아보았습니다. 세그먼트 트리는 다양한 문제를 효율적으로 해결할 수 있는 강력한 도구이며, 카운팅 문제나 최댓값/최솟값 문제 등 여러 분야에서 활용될 수 있습니다. 이 자료가 여러분의 코딩테스트 준비에 도움이 되기를 바랍니다! 추가적인 질문이 있으시면 댓글로 남겨주세요.

작성자: 조광형

작성일: 2024년 11월 26일

1. 선택 정렬(Selection Sort)란?

선택 정렬은 정렬 알고리즘 중 하나로, 주어진 배열에서 가장 작은(혹은 가장 큰) 원소를 선택하여
정렬을 수행하는 방식입니다. 이 알고리즘은 배열의 길이가 n일 때, n-1번의 비교 연산을 통해
정렬이 완료되기 때문에 O(n^2)의 시간복잡도를 가집니다.

선택 정렬의 주요 특징은 단순하고 직관적이며 메모리 사용이 효율적이라는 점입니다.
그러나 대량의 데이터에서 성능이 떨어지기 때문에 일반적으로는 복잡한 데이터에서
다른 정렬 알고리즘이 더욱 효율적입니다.

2. 선택 정렬의 방법론

선택 정렬은 다음 단계로 이루어져 있습니다:

1. 배열에서 최솟값을 찾는다.
2. 찾은 최솟값과 현재 위치의 원소를 교환한다.
3. 위 과정을 배열의 끝까지 반복한다.

이 과정을 좀 더 시각적으로 이해하기 위해, 5개의 숫자로 이루어진 배열을 예로 들어보겠습니다.
[64, 25, 12, 22, 11]라는 배열이 있을 때, 선택 정렬은 다음과 같이 동작합니다.

2.1. 예제: 배열 정렬 과정

초기 배열: [64, 25, 12, 22, 11]

1. 첫 번째 원소(64)와 나머지 원소 중 최솟값(11)을 교환:
   [11, 25, 12, 22, 64]
2. 두 번째 원소(25)와 나머지 원소 중 최솟값(12)을 교환:
   [11, 12, 25, 22, 64]
3. 세 번째 원소(25)와 나머지 원소 중 최솟값(22)을 교환:
   [11, 12, 22, 25, 64]
4. 네 번째 원소(25)와 마지막 원소(64)를 교환할 필요없이 두 원소는 이미 정렬된 상태이므로:
   [11, 12, 22, 25, 64]

최종적으로 정렬된 배열은 [11, 12, 22, 25, 64]입니다. 이처럼 선택 정렬은 매우 직관적이고
간단한 방법으로 정렬을 수행할 수 있습니다.

3. 자바로 구현하기

이제 자바 언어로 선택 정렬을 구현해보겠습니다.

                
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("정렬된 배열: " + java.util.Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;

            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}
                
            

위의 Java 코드는 선택 정렬을 구현한 예입니다. selectionSort 메서드는 주어진 배열의 길이를
확인한 후, 각 원소에 대해 다음 단계로 진행합니다. 첫 번째 중첩 루프는 현재 원소 이후의 원소들을 비교하여
최솟값의 인덱스를 결정하고, 그 후 두 원소를 교환합니다.

4. 선택 정렬의 시간복잡도

선택 정렬의 시간복잡도는 O(n^2)입니다. 이는 최악의 경우와 최선의 경우 모두 동일합니다. 왜냐하면
모든 원소를 한 번씩 비교해야 하기 때문입니다. 비록 선택 정렬이 탐색과 스왑만으로 수행되므로
추가적인 메모리 낭비는 없지만, 큰 데이터셋에서는 비효율적임을 알 수 있습니다.

선택 정렬의 공간 복잡도는 O(1)입니다. 이는 추가적인 메모리 공간을 사용하지 않고, 주어진
배열 내에서만 정렬 작업이 이루어지기 때문입니다. 이 점은 선택 정렬의 큰 장점 중 하나입니다.

5. 선택 정렬 사용 예시 및 장단점

5.1. 장점

• 구현이 간단하고 이해하기 쉽다.
• 추가적인 메모리 사용 없이 배열 내에서 정렬이 이루어진다.
• 데이터가 거의 정렬된 상태일 경우 효율적으로 동작할 수 있다.

5.2. 단점

• 대량의 데이터를 정렬할 경우 비효율적이다.
• 최악의 경우와 최선의 경우 시간복잡도가 동일하다.
• 일반적으로 다른 정렬 알고리즘에 비해 성능이 떨어진다.

6. 선택 정렬의 응용

선택 정렬은 단순성과 효율성 덕분에 교육적 목적으로 많이 사용됩니다.
알고리즘과 데이터 구조의 기본을 배우기 위한 입문 과정에서는 선택 정렬이
자주 활용됩니다. 또한 제한된 메모리 환경에서 스왑을 통한 정렬이 필요한 경우에
사용될 수 있습니다.

예를 들어, 실시간 데이터 스트림에서 간단한 정렬 로직이 필요할 때
선택 정렬을 사용할 수 있습니다. 하지만 대량의 데이터 처리에는
더 빠른 정렬 알고리즘을 사용하는 것이 더 적합합니다.

7. 마무리 및 참고 자료

선택 정렬은 가장 직관적인 정렬 알고리즘 중 하나로, 알고리즘을 배우는 데 매우 유용합니다.
그러나 실제 환경에서는 더 효율적인 알고리즘을 사용하는 것이 좋습니다.
이 강좌를 통해 선택 정렬의 개념과 구현 방법을 이해하고, 자바 코딩 테스트를 준비하는 데 도움이 되기를 바랍니다.

참고 자료:

• Geeks for Geeks – Selection Sort
• Wikipedia – Selection Sort
• TutorialsPoint – Selection Sort

문제 설명

두 선분이 주어질 때, 이 두 선분이 교차하는지 여부를 판별하는 알고리즘을 구현하시오.
선분 A는 점 A1(x1, y1)와 점 A2(x2, y2)로 주어지며, 선분 B는 점 B1(x3, y3)와 점 B2(x4, y4)로 주어진다.
교차 여부는 선분이 서로 교차하는 경우, 선분의 끝점이 다른 선분의 안쪽에 위치하는 경우, 혹은 선분이 일직선 상에 위치하는 경우를 고려하여 판단한다.

예제 입력

            A1: (1, 1)
            A2: (4, 4)
            B1: (1, 4)
            B2: (4, 1)
        

예제 출력

교차함

문제 풀이 과정

이 문제를 해결하기 위해 우리는 몇 가지 지리적 개념과 수학적 계산을 활용할 것입니다.
선분 교차 여부를 판단하기 위해 우선 두 선분의 방향을 파악하고, 그에 따라 교차 여부를 결정하는 방법을 사용합니다.

1단계: 방향 계산

주어진 두 선분의 끝점들을 이용하여, 각 선분이 위치하는 방향을 계산합니다.
두 선분 A(A1, A2)와 B(B1, B2)가 있을 때, 우리는 다음과 같은 방법으로 방향을 계산할 수 있습니다:

            def 방향(a1, a2, b1, b2):
                # 방향 판단을 위한 함수
                차 = (a2[0] - a1[0]) * (b1[1] - a1[1]) - (a2[1] - a1[1]) * (b1[0] - a1[0])
                if 차 == 0:
                    return 0  # 같은 방향
                return 1 if 차 > 0 else -1  # 왼쪽(+) 또는 오른쪽(-)
        

2단계: 교차 조건

두 선분이 서로 교차하는지 여부는 다음과 같은 조건에 따라 판단할 수 있습니다:

1. 선분 A의 방향이 B1, B2에 대한 지점에서 일치하지 않으며, 선분 B의 방향이 A1, A2에 대한 지점에서 일치하지 않을 경우, 두 선분은 서로 교차합니다.
2. 선분 A의 점들이 선분 B의 연장선에 존재할 경우, 즉 선의 끝점 중 하나가 다른 선의 내부에 포함되는 경우에도 교차으로 판단합니다.
3. 모든 점이 동일한 직선 상에 존재하면서 끝점이 서로 겹치는 경우, 즉 중복 발생시에는 교차로 간주합니다.

3단계: 구현

이제 이 조건을 바탕으로 자바에서 구현해 보겠습니다.

            public class LineIntersection {
                static class Point {
                    int x, y;
                    Point(int x, int y) { this.x = x; this.y = y; }
                }

                static int direction(Point a1, Point a2, Point b) {
                    int 차 = (a2.x - a1.x) * (b.y - a1.y) - (a2.y - a1.y) * (b.x - a1.x);
                    return (차 == 0) ? 0 : (차 > 0) ? 1 : -1; 
                }

                static boolean isIntersect(Point a1, Point a2, Point b1, Point b2) {
                    int d1 = direction(a1, a2, b1);
                    int d2 = direction(a1, a2, b2);
                    int d3 = direction(b1, b2, a1);
                    int d4 = direction(b1, b2, a2);

                    // Cross case
                    if(d1 != d2 && d3 != d4) return true;

                    // Collinear case
                    if(d1 == 0 && onSegment(a1, a2, b1)) return true;
                    if(d2 == 0 && onSegment(a1, a2, b2)) return true;
                    if(d3 == 0 && onSegment(b1, b2, a1)) return true;
                    if(d4 == 0 && onSegment(b1, b2, a2)) return true;

                    return false; 
                }

                static boolean onSegment(Point a, Point b, Point p) {
                    return (p.x <= Math.max(a.x, b.x) && p.x >= Math.min(a.x, b.x) &&
                            p.y <= Math.max(a.y, b.y) && p.y >= Math.min(a.y, b.y));
                }

                public static void main(String[] args) {
                    Point A1 = new Point(1, 1);
                    Point A2 = new Point(4, 4);
                    Point B1 = new Point(1, 4);
                    Point B2 = new Point(4, 1);

                    if (isIntersect(A1, A2, B1, B2)) {
                        System.out.println("교차함");
                    } else {
                        System.out.println("교차하지 않음");
                    }
                }
            }
        

위의 코드를 실행하면 두 선분 간의 교차 여부를 파악할 수 있습니다.

4단계: 테스트

다양한 테스트 케이스를 시도하여 올바른 코드 작동 여부를 확인합니다.

            // Test Case 1
            A1: (1, 1)
            A2: (4, 4)
            B1: (1, 4)
            B2: (4, 1)  // Output: 교차함

            // Test Case 2
            A1: (1, 1)
            A2: (1, 3)
            B1: (1, 2)
            B2: (1, 4)  // Output: 교차함

            // Test Case 3
            A1: (1, 1)
            A2: (2, 2)
            B1: (3, 3)
            B2: (4, 4)  // Output: 교차하지 않음
        

이처럼 다양한 사례를 통해 알고리즘이 잘 작동하는지 검증할 수 있습니다.

결론

이번 강좌를 통해 선분의 교차 여부를 판단하는 알고리즘을 구현하는 방법을 배웠습니다.
문제 해결을 위해 기하학적 사고와 코드 구현을 통해 교차 조건을 이해하고 적용하는 과정이었습니다.
이 지식은 다양한 응용 분야에서 사용되므로, 알고리즘과 자료구조에 대한 이해도를 높이는 데 큰 도움이 될 것입니다.
함께한 여러분들이 여러 문제를 풀고 더 나아가 기본기를 다지는 데에 이 강좌가 도움이 되기를 바랍니다.