시간 복잡도

알고리즘 분석 시 시간과 공간 복잡도를 우선 고려합니다. O(n³) 이상의 복잡도는 실제 환경에서 비효율적입니다. n은 데이터 규모를 나타내며, 로그 복잡도(log n)는 연산 횟수가 데이터 크기에 로그적으로 비례함을 의미합니다.

배열

이진 탐색

정렬된 배열에서 중복 없을 때 적용 가능합니다. 탐색 구간을 반으로 축소하며 대상 값을 검색합니다.

class BinarySearcher {
    int findTarget(int[] data, int target) {
        int low = 0;
        int high = data.length - 1;
        
        while (low <= high) {
            int pivot = low + (high - low) / 2;
            if (data[pivot] > target) {
                high = pivot - 1;
            } else if (data[pivot] < target) {
                low = pivot + 1;
            } else {
                return pivot;
            }
        }
        return -1;
    }
}

시간 복잡도: O(log n)

요소 제거

빠른 포인터와 느린 포인터를 활용해 효율적으로 요소를 제거합니다.

class ElementRemover {
    int filterValues(int[] data, int removeVal) {
        int slow = 0;
        for (int fast = 0; fast < data.length; fast++) {
            if (data[fast] != removeVal) {
                data[slow++] = data[fast];
            }
        }
        return slow;
    }
}

시간 복잡도: O(n), 공간 복잡도: O(1)

정렬된 배열 제곱

양끝 포인터로 최대 제곱값을 비교하며 새 배열에 역순으로 저장합니다.

class SquareSorter {
    int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] output = new int[nums.length];
        int idx = output.length - 1;
        
        while (left <= right) {
            int leftSq = nums[left] * nums[left];
            int rightSq = nums[right] * nums[right];
            if (leftSq >= rightSq) {
                output[idx--] = leftSq;
                left++;
            } else {
                output[idx--] = rightSq;
                right--;
            }
        }
        return output;
    }
}

시간 복잡도: O(n)

최소 길이 부분 배열

슬라이딩 윈도우 기법으로 목표 합을 만드는 최소 길이 구간을 탐색합니다.

class SubarrayFinder {
    int minSubArray(int target, int[] nums) {
        int start = 0, total = 0;
        int minLength = Integer.MAX_VALUE;
        
        for (int end = 0; end < nums.length; end++) {
            total += nums[end];
            while (total >= target) {
                minLength = Math.min(minLength, end - start + 1);
                total -= nums[start++];
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

시간 복잡도: O(n)

스파이럴 행렬

레이어별로 외곽부터 내부까지 시계방향으로 숫자를 채웁니다.

class SpiralGenerator {
    int[][] generateSpiral(int n) {
        int[][] grid = new int[n][n];
        int layer = 0, start = 0, counter = 1;
        
        while (layer++ < n / 2) {
            for (int col = start; col < n - layer; col++) 
                grid[start][col] = counter++;
            for (int row = start; row < n - layer; row++) 
                grid[row][n - layer] = counter++;
            for (int col = n - layer - 1; col >= layer; col--) 
                grid[n - layer][col] = counter++;
            for (int row = n - layer - 1; row >= layer; row--) 
                grid[row][start] = counter++;
            start++;
        }
        if (n % 2 == 1) grid[start][start] = counter;
        return grid;
    }
}

시간 복잡도: O(n²)

연결 리스트

노드가 데이터와 포인터로 구성된 선형 구조입니다. 단일/이중/순환 연결 리스트 유형이 존재합니다.

요소 제거

가상 헤드 노드를 활용해 경계 조건을 단순화합니다.

class ListCleaner {
    ListNode removeElements(ListNode head, int target) {
        if (head == null) return null;
        ListNode dummyHead = new ListNode(0, head);
        ListNode prev = dummyHead;
        ListNode curr = head;
        
        while (curr != null) {
            if (curr.val == target) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }
        return dummyHead.next;
    }
}