알고리즘 개요

검색 알고리즘

1. 순차 검색 (Linear Search)

배열의 첫 번째 인덱스부터 순서대로 원하는 값을 찾는 가장 기본적인 방법입니다.

public class LinearSearchExample {
    public static void main(String[] args) {
        int[] numbers = {131, 127, 147, 81, 103, 23, 7, 79};
        int target = 82;
        System.out.println(exists(numbers, target)); 
    }

    // 값 존재 여부 확인
    public static boolean exists(int[] arr, int value) {
        for (int num : arr) {
            if (num == value) {
                return true;
            }
        }
        return false;
    }
}

public class LinearSearchIndex {
    public static void main(String[] args) {
        int[] data = {131, 127, 147, 81, 103, 23, 7, 79};
        int key = 81;
        System.out.println(findFirstIndex(data, key)); // 중복 없음 가정
    }

    private static int findFirstIndex(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

import java.util.ArrayList;

public class LinearSearchDuplicates {
    public static void main(String[] args) {
        int[] values = {131, 127, 147, 81, 103, 23, 7, 79, 81};
        int searchKey = 81;
        System.out.println(findAllIndices(values, searchKey)); 
    }

    private static ArrayList<Integer> findAllIndices(int[] arr, int key) {
        ArrayList<Integer> indices = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                indices.add(i);
            }
        }
        return indices;
    }
}

2. 이진 검색 (Binary Search)

정렬된 배열에서만 사용 가능하며, 검색 범위를 절반씩 줄여가며 값을 찾습니다.

public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] sortedArray = {7, 23, 79, 81, 103, 127, 131, 147};
        System.out.println(findIndex(sortedArray, 81)); 
    }

    public static int findIndex(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

3. 블록 검색 (Block Search)

블록 내에서는 순서가 없지만, 블록 간에는 정렬된 상태를 유지합니다. 데이터 개수의 제곱근 정도로 블록을 나눕니다.

public class BlockSearch {
    public static void main(String[] args) {
        int[] dataset = {16, 5, 9, 12, 21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66};

        Block block1 = new Block(21, 0, 5);
        Block block2 = new Block(45, 6, 11);
        Block block3 = new Block(73, 12, 17);

        Block[] blockTable = {block1, block2, block3};
        int targetValue = 32;
        int resultIndex = searchByBlocks(blockTable, dataset, targetValue);

        System.out.println(resultIndex);
    }

    private static int searchByBlocks(Block[] blocks, int[] data, int target) {
        int blockIndex = findBlock(blocks, target);
        if (blockIndex == -1) {
            return -1;
        }

        int startPos = blocks[blockIndex].getStart();
        int endPos = blocks[blockIndex].getEnd();

        for (int i = startPos; i <= endPos; i++) {
            if (data[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static int findBlock(Block[] blocks, int target) {
        for (int i = 0; i < blocks.length; i++) {
            if (target <= blocks[i].getMaxValue()) {
                return i;
            }
        }
        return -1;
    }
}

class Block {
    private int maxValue;
    private int start;
    private int end;

    public Block(int max, int s, int e) {
        this.maxValue = max;
        this.start = s;
        this.end = e;
    }

    // getter/setter 생략 (필요시 추가)
    public int getMaxValue() { return maxValue; }
    public int getStart() { return start; }
    public int getEnd() { return end; }
}

블록 검색 확장 (비교적 블록)

public class BlockSearchV2 {
    public static void main(String[] args) {
        int[] data = {27, 22, 30, 40, 36, 13, 19, 16, 20, 7, 10, 43, 50, 48};

        EnhancedBlock b1 = new EnhancedBlock(22, 36, 0, 4);
        EnhancedBlock b2 = new EnhancedBlock(13, 20, 5, 8);
        EnhancedBlock b3 = new EnhancedBlock(7, 10, 9, 10);
        EnhancedBlock b4 = new EnhancedBlock(43, 50, 11, 13);

        EnhancedBlock[] blocks = {b1, b2, b3, b4};
        int searchKey = 10;
        int idx = enhancedSearch(blocks, data, searchKey);
        System.out.println(idx);
    }

    private static int enhancedSearch(EnhancedBlock[] blocks, int[] data, int target) {
        int blockIdx = locateBlock(blocks, target);
        if (blockIdx == -1) return -1;

        int sIdx = blocks[blockIdx].getStart();
        int eIdx = blocks[blockIdx].getEnd();

        for (int i = sIdx; i <= eIdx; i++) {
            if (data[i] == target) return i;
        }
        return -1;
    }

    public static int locateBlock(EnhancedBlock[] blocks, int target) {
        for (int i = 0; i < blocks.length; i++) {
            if (target >= blocks[i].getMinValue() && target <= blocks[i].getMaxValue()) {
                return i;
            }
        }
        return -1;
    }
}

class EnhancedBlock {
    private int minValue;
    private int maxValue;
    private int start;
    private int end;

    public EnhancedBlock(int min, int max, int s, int e) {
        this.minValue = min;
        this.maxValue = max;
        this.start = s;
        this.end = e;
    }
    // getter 생략
    public int getMinValue() { return minValue; }
    public int getMaxValue() { return maxValue; }
    public int getStart() { return start; }
    public int getEnd() { return end; }
}

정렬 알고리즘

1. 버블 정렬 (Bubble Sort)

인접한 두 요소를 비교하여 큰 값을 오른쪽으로 보냅니다. 각 라운드가 끝날 때마다 가장 큰 값이 확정됩니다.

2. 선택 정렬 (Selection Sort)

현재 위치(i)를 기준으로 나머지 요소들과 비교하여 더 작은 값이 있으면 교환합니다.

for (int i = 0; i < arr.length - 1; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[i]) {
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
}

3. 삽입 정렬 (Insertion Sort)

0번부터 N번 인덱스까지를 정렬된 부분, N+1번부터 끝까지를 정렬되지 않은 부분으로 간주합니다. 정렬되지 않은 요소를 하나씩 정렬된 부분의 올바른 위치에 삽입합니다.

public class InsertionSortDemo {
    public static void main(String[] args) {
        int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        
        // 정렬되지 않은 부분의 시작점 찾기
        int unsortedStart = -1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] < nums[i]) {
                unsortedStart = i + 1;
                break;
            }
        }

        // 삽입 정렬 수행
        for (int i = unsortedStart; i < nums.length; i++) {
            int current = i;
            while (current > 0 && nums[current] < nums[current - 1]) {
                int swapTemp = nums[current];
                nums[current] = nums[current - 1];
                nums[current - 1] = swapTemp;
                current--;
            }
        }
        
        // 결과 출력
        for (int value : nums) {
            System.out.print(value + " ");
        }
    }
}

4. 퀵 정렬 (Quick Sort)

재귀를 사용하여 기준값(pivot)을 정하고, 기준값보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치합니다.

// 재귀의 핵심: 메서드가 자신을 호출하는 것. 반드시 종료 조건(출구)이 필요합니다.
// 규칙: 큰 문제를 작은 문제로 나누어 해결합니다.
// 예제: 1~100 합 구하기 (getSum(100) = 100 + getSum(99))
// 예제: 팩토리얼 구하기 (getFactorial(5) = 5 * getFactorial(4))

import java.util.Random;

public class QuickSortExample {
    public static void main(String[] args) {
        int[] testArray = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        quickSort(testArray, 0, testArray.length - 1);
        
        for (int val : testArray) {
            System.out.print(val + " ");
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (right < left) return;

        int start = left;
        int end = right;
        int pivot = arr[left];

        while (start != end) {
            while (end > start && arr[end] >= pivot) end--;
            while (start < end && arr[start] <= pivot) start++;

            if (start < end) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        }

        arr[left] = arr[start];
        arr[start] = pivot;

        quickSort(arr, left, start - 1);
        quickSort(arr, start + 1, right);
    }
}

Arrays 유틸리티 클래스

배열을 다루는 다양한 정적 메서드를 제공합니다.

• toString(배열) : 배열을 문자열로 변환
• binarySearch(배열, 키) : 이진 탐색으로 인덱스 찾기
• copyOf(원본, 새길이) : 배열 복사
• copyOfRange(원본, 시작인덱스, 끝인덱스) : 범위 복사
• fill(배열, 값) : 배열을 특정 값으로 채우기
• sort(배열) : 기본 정렬 (오름차순)
• sort(배열, Comparator) : 사용자 정의 정렬 규칙 적용

import java.util.Arrays;
import java.util.Comparator;

public class ArraysMethodDemo {
    public static void main(String[] args) {
        Integer[] numbers = {2, 3, 1, 5, 6, 7, 8, 4, 9};

        // 사용자 정의 정렬 (Comparator 인터페이스 구현 - 익명 클래스)
        Arrays.sort(numbers, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                // o1 - o2: 오름차순, o2 - o1: 내림차순
                return o1 - o2;
            }
        });

        System.out.println(Arrays.toString(numbers));
    }
}

람다 표현식 (Lambda Expression)

1. 함수형 프로그래밍 개념

"무엇을 할 것인가"에 초점을 맞추며, 복잡한 객체 지향 문법을 생략할 수 있게 해줍니다. 람다는 이러한 사상을 구현한 Java 8의 새로운 문법입니다.

2. 람다 기본 문법

(매개변수) -> {
    // 실행할 코드
}

주의사항: 람다는 함수형 인터페이스(단 하나의 추상 메서드만 가진 인터페이스)의 익명 클래스만 간소화할 수 있습니다. @FunctionalInterface 어노테이션으로 명시할 수 있습니다.

@FunctionalInterface
interface Swimmer {
    void swim();
}

public class LambdaIntro {
    public static void main(String[] args) {
        // 익명 클래스 방식
        executeSwim(new Swimmer() {
            @Override
            public void swim() {
                System.out.println("수영 중~~");
            }
        });

        // 람다 방식
        executeSwim(() -> System.out.println("수영 중~~"));
    }

    public static void executeSwim(Swimmer swimmer) {
        swimmer.swim();
    }
}

3. 람다 생략 규칙

• 매개변수 타입 생략 가능
• 매개변수가 하나면 괄호 생략 가능
• 실행문이 하나면 중괄호, 세미콜론, return 키워드 생략 가능

import java.util.Arrays;

public class LambdaSimplify {
    public static void main(String[] args) {
        Integer[] values = {2, 3, 1, 5, 6, 7, 8, 4, 9};

        // 람다 생략 버전
        Arrays.sort(values, (o1, o2) -> o1 - o2);
        System.out.println(Arrays.toString(values));
    }
}

4. 실습: 문자열 길이 정렬

import java.util.Arrays;

public class LambdaPractice {
    public static void main(String[] args) {
        String[] words = {"a", "aaaa", "aaa", "aa"};

        // 문자열 길이 기준 오름차순 정렬
        Arrays.sort(words, (s1, s2) -> s1.length() - s2.length());
        
        System.out.println(Arrays.toString(words));
    }
}

종합 연습 문제

1. 객체 배열 정렬

import java.util.Arrays;

class BoyFriend {
    private String name;
    private int age;
    private double height;

    public BoyFriend(String name, int age, double height) {
        this.name = name;
        this.age = age;
        this.height = height;
    }

    // getter 생략
    public String getName() { return name; }
    public int getAge() { return age; }
    public double getHeight() { return height; }

    @Override
    public String toString() {
        return name + "(" + age + ", " + height + ")";
    }
}

public class ObjectSortTest {
    public static void main(String[] args) {
        BoyFriend[] friends = {
            new BoyFriend("lan", 18, 1.85),
            new BoyFriend("yu", 19, 1.80),
            new BoyFriend("ce", 19, 1.87)
        };

        // 나이 -> 키 -> 이름 순 정렬
        Arrays.sort(friends, (o1, o2) -> {
            double compareResult = o1.getAge() - o2.getAge();
            if (compareResult == 0) {
                compareResult = o1.getHeight() - o2.getHeight();
            }
            if (compareResult == 0) {
                return o1.getName().compareTo(o2.getName());
            }
            return compareResult > 0 ? 1 : -1;
        });

        System.out.println(Arrays.toString(friends));
    }
}

2. 피보나치 수열 (불사신 토끼)

첫 달에 토끼 한 쌍이 있고, 매월 성체가 된 토끼가 새끼 한 쌍을 낳는다고 가정할 때, 12개월 후 토끼 쌍의 수는?

public class RabbitProblem {
    public static void main(String[] args) {
        // 반복문 사용
        int[] months = new int[12];
        months[0] = 1;
        months[1] = 1;
        for (int i = 2; i < months.length; i++) {
            months[i] = months[i - 1] + months[i - 2];
        }
        System.out.println("12월 토끼 수: " + months[11]);

        // 재귀 사용
        System.out.println("재귀 결과: " + fib(12));
    }

    public static int fib(int n) {
        if (n == 1 || n == 2) return 1;
        return fib(n - 1) + fib(n - 2);
    }
}

3. 원숭이 복숭아 문제

원숭이가 매일 남은 복숭아의 절반에 하나를 더 먹습니다. 10일째 아침에 하나 남았을 때, 처음 복숭아 개수는?

public class PeachProblem {
    public static void main(String[] args) {
        System.out.println("초기 복숭아: " + countPeaches(1));
    }

    public static int countPeaches(int day) {
        if (day == 10) return 1;
        return (countPeaches(day + 1) + 1) * 2;
    }
}

4. 계단 오르기 (기본)

한 번에 1칸 또는 2칸씩 오를 수 있을 때, 20칸 계단을 오르는 방법의 수는?

public class StairClimbing {
    public static void main(String[] args) {
        System.out.println("방법의 수: " + climbStairs(20));
    }

    public static int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

5. 계단 오르기 (확장)

한 번에 1, 2, 또는 3칸을 오를 수 있을 때, 20칸 계단을 오르는 방법의 수는?

public class StairClimbingV2 {
    public static void main(String[] args) {
        System.out.println("방법의 수: " + climbAny(20));
    }

    public static int climbAny(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        return climbAny(n - 1) + climbAny(n - 2) + climbAny(n - 3);
    }
}