[Java] 코딩테스트용 주요 함수/알고리즘 모음 (2)

 

22. 그리디 (Greedy)

항상 가장 최선의 선택(국소 최적)이 전체 최적을 만든다고 가정

예: 거스름돈 문제

int[] coins = {500, 100, 50, 10};
int target = 1260;
int count = 0;

for (int coin : coins) {
    count += target / coin;
    target %= coin;
}
System.out.println(count); // 최소 동전 개수

📌 대표 문제: 동전 문제, 회의실 배정, 배낭 문제(단순), 줄 세우기, 최소 비용 선택

 

23. 누적합 (Prefix Sum)

구간 합을 빠르게 구하기 위해 전체 누적합을 미리 계산

int[] arr = {1, 2, 3, 4, 5};
int[] prefix = new int[arr.length + 1]; // prefix[0] = 0

for (int i = 0; i < arr.length; i++) {
    prefix[i+1] = prefix[i] + arr[i];
}

// [2, 4] 구간합 → prefix[5] - prefix[2]
int sum = prefix[4+1] - prefix[2];

📌 2차원 배열도 prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + A[i][j] 형태로 확장 가능

 

24. 슬라이딩 윈도우 (Two Pointer)

고정된 길이의 범위 또는 조건을 만족하는 구간을 효율적으로 찾을 때

예: 연속된 K개 합의 최대값

int[] arr = {1, 3, 2, 5, 4};
int k = 3;
int sum = 0;

for (int i = 0; i < k; i++) sum += arr[i];
int max = sum;

for (int i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i-k];
    max = Math.max(max, sum);
}

📌 대표 문제: 부분합, 최대 연속합, 문자열 윈도우, 투포인터

 

25. 에라토스테네스의 체 / 소수 판별

소수 판별 함수

boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

 

에라토스테네스의 체 (N 이하의 모든 소수)

boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i <= N; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= N; j += i) {
            isPrime[j] = false;
        }
    }
}

📌 시간복잡도: O(N log log N)

 

26. 최단 경로 (Dijkstra / Floyd / Bellman-Ford)

다익스트라 (우선순위 큐)

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
int[] dist = new int[N+1];
Arrays.fill(dist, INF);
dist[start] = 0;

pq.offer(new int[]{start, 0});

while (!pq.isEmpty()) {
    int[] now = pq.poll();
    int cur = now[0], cost = now[1];

    if (dist[cur] < cost) continue;

    for (int[] next : graph.get(cur)) {
        int nextNode = next[0], nextCost = cost + next[1];
        if (nextCost < dist[nextNode]) {
            dist[nextNode] = nextCost;
            pq.offer(new int[]{nextNode, nextCost});
        }
    }
}

플로이드 워셜 (모든 쌍 최단경로)

int[][] dist = new int[N][N];
for (int k = 0; k < N; k++)
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

📌 음의 간선 없음 → 다익스트라
📌 모든 쌍 경로 → 플로이드
📌 음수 사이클 감지 → 벨만포드

27. 트리 기초 / LCA (최소 공통 조상)

트리 입력 + DFS 구성 예시

List<List<Integer>> tree = new ArrayList<>();
for (int i = 0; i <= N; i++) tree.add(new ArrayList<>());

for (int i = 0; i < N-1; i++) {
    int u = sc.nextInt(), v = sc.nextInt();
    tree.get(u).add(v);
    tree.get(v).add(u);
}

부모 정보 + 깊이 저장

int[] parent = new int[N+1];
int[] depth = new int[N+1];

void dfs(int node, int par, int d) {
    parent[node] = par;
    depth[node] = d;
    for (int next : tree.get(node)) {
        if (next != par) dfs(next, node, d+1);
    }
}

LCA 구하기 (기초 방식)

int lca(int a, int b) {
    while (depth[a] > depth[b]) a = parent[a];
    while (depth[b] > depth[a]) b = parent[b];
    while (a != b) {
        a = parent[a];
        b = parent[b];
    }
    return a;
}

📌 LCA는 최대 O(log N) 으로 효율적으로 구할 수도 있음 (희소배열 이용)

 

28. 코딩 테스트 대비 전략 & 패턴

✅ 필수 전략

• 입출력 빠르게 처리하기 (BufferedReader / Writer)
• 자료구조 정리 (Map, Set, List, Stack, Queue, PriorityQueue)
• 정렬 기준 커스터마이징 (Comparator, compareTo)
• 방문 여부는 boolean[], HashSet, visited[x][y] 다양하게 사용
• 문제 조건이 작으면 완전탐색 / 클 경우 그리디나 이분탐색 고려

✅ 패턴 예시

• for (int i = 0; i < N; i++) : 일반 루프
• While (!q.isEmpty()) : BFS
• dfs(…) : 백트래킹 / 그래프 탐색
• dp[i] = Math.min(...) : DP 점화식
• map.getOrDefault(x, 0) + 1 : 빈도수

 

29. 백트래킹 (Backtracking)

모든 경우의 수를 시도해보되, 불필요한 경우는 가지치기로 탐색을 줄이는 기법

순열 (Permutation)

void permute(List<Integer> result, boolean[] visited) {
    if (result.size() == N) {
        System.out.println(result);
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            result.add(arr[i]);
            permute(result, visited);
            result.remove(result.size() - 1);
            visited[i] = false;
        }
    }
}

조합 (Combination)

void combine(List<Integer> result, int start) {
    if (result.size() == R) {
        System.out.println(result);
        return;
    }

    for (int i = start; i < N; i++) {
        result.add(arr[i]);
        combine(result, i + 1);
        result.remove(result.size() - 1);
    }
}

 

30. 이진탐색 / 매개변수 탐색

정렬된 배열에서 빠르게 값을 찾거나, 특정 조건을 만족하는 최적의 값을 탐색

일반적인 이진 탐색

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

매개변수 탐색 (Parametric Search)

int low = 0, high = 1_000_000;
while (low <= high) {
    int mid = (low + high) / 2;
    if (조건을 만족한다면) {
        answer = mid;
        high = mid - 1;
    } else {
        low = mid + 1;
    }
}

 

31. 재귀 함수 최적화 팁

• 꼬리 재귀 최적화 (Tail Recursion) → Java는 지원하지 않음
• 재귀 깊이가 클 경우: StackOverflowError 발생
• Memoization 또는 반복문으로 전환 추천
• DFS 등은 visited 배열 필수

32. 문자열 알고리즘 (KMP)

문자열 안에서 부분 문자열을 빠르게 찾는 알고리즘 (O(N+M))

int[] getPi(String pattern) {
    int[] pi = new int[pattern.length()];
    int j = 0;
    for (int i = 1; i < pattern.length(); i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = pi[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            pi[i] = ++j;
        }
    }
    return pi;
}

 

33. 순열/조합 구현 + 비트마스크 조합

비트마스크로 부분 집합 탐색

for (int bit = 0; bit < (1 << N); bit++) {
    List<Integer> subset = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        if ((bit & (1 << i)) != 0) {
            subset.add(arr[i]);
        }
    }
    System.out.println(subset);
}

📌 2^N 가지의 모든 조합을 빠르게 탐색할 수 있음
📌 집합 크기가 20 이하일 때 적합

 

34. 고정밀 연산 (BigInteger / BigDecimal)

BigInteger

import java.math.*;

BigInteger a = new BigInteger("12345678901234567890");
BigInteger b = new BigInteger("98765432109876543210");

BigInteger sum = a.add(b);
BigInteger mul = a.multiply(b);

BigDecimal

BigDecimal d1 = new BigDecimal("123.456");
BigDecimal d2 = new BigDecimal("789.123");

BigDecimal result = d1.add(d2);
result = result.setScale(2, RoundingMode.HALF_UP); // 소수 둘째 자리 반올림

📌 오차 없는 소수 계산이나 아주 큰 수 연산이 필요한 문제에서 유용
📌 문자열로 초기화할 것 (new BigDecimal(double)은 부정확)

 

https://awesomepossum.tistory.com/932

[Java] 코딩테스트용 주요 함수/알고리즘 모음 (1)