(24.08.28) 코딩테스트 알고리즘 정리(구현:누적합,유클리드,에라토스테네스의체, 구간탐색:이분탐색,슬라이딩윈도우, Greedy:동전교환 알고리즘)

 

이전까지는 거의 코드 카타를 맨땅에 헤딩하듯이 풀어서

다시 살펴보니, 간단하게 알고리즘으로 풀수 있는 로직을 굳이 O(N^2) 시간 복잡도로 하나씩 대조하거나 하는 식의 로직이 많았기 때문에,

필수 알고리즘 기초부터 다시 정리를 하기 시작했다.

 

검색을 통해 정리를 하고, 스스로 코드를 적으면서 정리를 한 뒤, 응용된 문제들을 푸는 방식으로 진행을 해야

여러 알고리즘이 섞인 코딩테스트 문제도 해결할 수 있을 것이라고 판단해서

 

블로그 TIL과 Notion에 정리를 하도록 한다. 

 

---

누적합 Prefix Sum

• 특정 배열 등의 자료 구조 구간의 누적된 합, 즉 계속 지속적으로 더하는 알고리즘
  • 배열의 여러 구간에 대해 부분합을 빠르게 계산
• “ 이전까지의 누적합을 다음 누적합에 사용한다” 라는 알고리즘이기 때문에 항상 누적합 배열에서는

누적합 Algorithm Flow

1. 전체 배열 A에 대한 index 0~i 까지 누적합 배열 P생성
   • 여기서, 배열 P는 배열 A의 index 0 ~ i 까지의 합들의 집합
   • ex) P[i] = A[0] + A[1] + ... + A[i-1]
   • 누적합 배열 P의 index 0은 아무 원소도 더하지 않는 합 0으로 설정
     • 구간 합을 구하려는 시도가 있을 때, 또는 로직을 구축을 할 때, 그 구간이 배열A의 index 0 까지일 경우도 있기 때문에 반드시 필요
     ex) 원본 배열 A가 [3, 2, 5, 1, 4]일 때, 누적합 배열 P
     • P[0] = 0 (빈 부분합)
     • P[1] = 3 (A[0])
     • P[2] = 3 + 2 = 5 (A[0] + A[1])
     • P[3] = 3 + 2 + 5 = 10 (A[0] + A[1] + A[2])
     • P[4] = 3 + 2 + 5 + 1 = 11 (A[0] + A[1] + A[2] + A[3])
     • P[5] = 3 + 2 + 5 + 1 + 4 = 15 (A[0] + A[1] + A[2] + A[3] + A[4])
2. 구하고자 하는 구간 합 계산
   • 시작 인덱스 **A[l]**도 포함을 시켜야 하기 때문에 P[l + 1]이 아님 위의 예제 확인
3. **배열 A의 index l ~ r까지의 구간 합 = P[r + 1] - P[l]**

누적합 Alorithm Step

누적합 배열 P 생성 만들기

public class PrefixSum {
    public static void main(String[] args) {
        int[] A = {3, 2, 5, 1, 4};
        int n = A.length;

        **// 누적합 배열 P 생성
        // P[0] = 0 이 있어야 하기 때문에 크기는 n+1
        int[] P = new int[n + 1];
        for (int i = 1; i <= n; i++) { // P[0] 설정 안해도 자동으로 0 초기화 이므로 0부터 시작 X
            P[i] = P[i - 1] + A[i - 1]; // 하나씩 계속 추가, i-1 이라는 거 항상 생각해야
        }**

        // 누적합 배열 출력
        System.out.println("누적합 배열: " + Arrays.toString(P));
    }
}

구간 합 계산

public class PrefixSum {
    public static void main(String[] args) {
			  
			  // 위 누적합 배열 P 생성 로직

        // 구간 합 계산 (예: 인덱스 2부터 4까지)
	      int l = 2; // 시작 인덱스
        int r = 4; // 끝 인덱스 
        **int sum = P[r + 1] - P[l];**
        System.out.println("구간 합: " + sum);
    }
}

 

---

유클리드 알고리즘 = 유클리드 호제법 Euclidean Algorithm

최대공약수 GCD, Greatest Common Divisor

GCD 유클리드 알고리즘 Flow

• 두 수 중 큰 수를 작은 수로 나누고, 나머지를 다시 작은 수로 나누면서나머지가 0이 되면, 나누는 수가 GCD

1. a와 b가 주어졌다고 할 때, a를 b로 나눈 나머지를 r 로 지정
2. a를 b로 바꾸기 / b를 r로 바꾸기
3. 바꾼 후, b가 0이 될 때까지 반복 (while문 사용을 위해)
4. a가 GCD

GCD 유클리드 알고리즘

public class EuclideanAlgorithm {
  **public static int gcd(int a, int b) {
    int minValue = Math.min(a, b);
    int maxValue = Math.max(a, b);

    while (minValue != 0) {
      int remainder = maxValue % minValue;
      maxValue = minValue;
      minValue = remainder;
    }
    return maxValue;
  }**
		
    public static void main(String[] args) {
        int a = 48;
        int b = 18;

        int gcdValue = gcd(a, b);

        System.out.println("GCD(" + a + ", " + b + ") = " + gcdValue);
    }
}

최소공배수 LCM, Least Common Multiple

• 두 자연수의 곱에서 GCD를 나눈 값, 따라서 최소공배수를 쓰려면 유클리드 알고리즘을 통해서 최대 공약수를 구하면 됨
• 두 int 정수 값 중 음수가 하나있더라도 LCM은 양수여야 하기 때문에 절댓값을 사용해야함

public class GCDAndLCM {
  **public static int gcd(int a, int b) {
    int minValue = Math.min(a, b);
    int maxValue = Math.max(a, b);

    while (minValue != 0) {
      int remainder = maxValue % minValue;
      maxValue = minValue;
      minValue = remainder;
    }
    return maxValue;
  }**

    // GCD를 사용하여 LCM을 계산
    **public static int lcm(int a, int b) {
        return Math.abs(a * b) / gcd(a, b);
    }**

    public static void main(String[] args) {
        int a = 48;
        int b = 18;

        int gcdValue = gcd(a, b);
        int lcmValue = lcm(a, b);

        System.out.println("GCD(" + a + ", " + b + ") = " + gcdValue);
        System.out.println("LCM(" + a + ", " + b + ") = " + lcmValue);
    }
}

큰 수, 작은 수 판별하기

Math.max(int a, int b) 와 Math.min(int a, int b) 를 활용해서 큰 수 작은 수를 판별 할 수 있도록 해야함

 

---

에라토스테네스의 체 Sieve of Eratosthenes

• 주어진 수 n이하의 모든 소수를 다 찾아내는 알고리즘
• “소수의 배수는 전부 소수가 아니다” 를 기준으로 소수를 찾음
• n 의 제곱근 아래의 수만 소수인지 판별해도 모든 n이하의 소수를 거진 찾을 수 있다는 것을 가정
  • 동시에, 방복문은 소수로 판명된 i 에 대하여 i*i의 배수만 처리해도 된다고 판단

에라토스테네스의 체 Algorithm Flow

1. 배열 초기화:
   • n까지의 모든 수에 대해 소수 여부를 나타내는 배열 isPrime을 초기화
   • 초기에는 2부터 n까지 모든 수를 소수로 간주
2. 소수 찾기
   • 배열의 처음부터 시작하여, 현재 수가 소수(True)이면 그 수의 배수들을 모두 소수가 아니라고 표시 (굳이 다 할 필요가 없음)
3. 반복
   • 이 과정을 주어진 범위의 수들에 대해 반복하면, 최종적으로 배열에 남아 있는 True 값이 소수

에라토스테네스의 체 Algorithm

1. 초기화
   • isPrime 배열을 크기 n + 1로 생성하고, 2부터 n까지의 모든 값을 True로 설정
     • n+1인 이유는 Java 인덱스와 = 실제 수를 일치 시키기 위해
   • 인덱스 0 과 1은 소수가 아니므로 False로 설정
     • 수 0, 1은 소수가 아니기 때문에

—반복 시작

1. 첫 번째 소수 2의 배수 제거
   • 2는 소수이므로 2의 배수 = 짝수를 모두 False로 설정
2. 다음 소수 3의 배수 제거
   • 3은 소수이므로 3의 배수(6, 9, 12, ...)를 모두 False로 설정
   • 이미 2의 배수로 제거된 숫자는 다시 고려하지 X
3. 그 다음 소수
   • 다음 소수는 5 이므로, 5의 배수(10, 15, 20, ...)를 모두 False로 설정
   • 4는 이미 제거된 숫자(2번에서 False) 이므로 고려하지 X

—반복 종료

1. 최종 배열
   • isPrime 배열에서 True로 남아 있는 인덱스는 모두 소수가 되는 법

import java.util.Arrays;

public class SieveOfEratosthenes {

    **public static boolean[] sieve(int n) {
        // n까지의 모든 수를 소수로 간주하여 배열 초기화
        boolean[] isPrime = new boolean[n + 1];
        
        Arrays.fill(isPrime, true); // fill 메서드를 사용해서 모두 true
        
        isPrime[0] = false; // 0은 소수가 아님
        isPrime[1] = false; // 1도 소수가 아님

        // 2부터 시작하여 소수들의 배수를 제거
        // (중요) 이 경우 주어진 수 n의 제곱근 만 실시를 해도 소수를 거진 구할 수 있다고 판단
        // (중오) 동시에 배수르 전부 처리하는 것이 아닌, 한번 더 고려할 필요없이 i*i 수 부터 배수로 생각해주는 것
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) { // j에 계속
                    isPrime[j] = false; // i의 배수들은 소수가 아님
                }
            }
        }
        return isPrime;
    }**

		// Method 실행 main
    public static void main(String[] args) {
        int n = 30;
        boolean[] isPrime = sieve(n);

        System.out.println("Primes up to " + n + ":");
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

---

이분탐색 Binary Search

• 정렬된 배열에서 특정 값을 효율적으로 찾기 위한 알고리즘
• 배열을 반씩 줄여가면서 검색 범위를 줄여나가는 방식
  • 시간 복잡도가 O(log n) 으로 엄청 빠름

이분탐색 Binary Search Flow

1. 시작과 끝 인덱스 설정
   • 배열의 시작 인덱스와 끝 인덱스를 설정
   • 인덱스 이기 때문에 length로 지정하면 당연히 예외발생
2. 중간 인덱스 계산
   • 배열의 중간 인덱스를 계산
3. 비교
   • 중간 값이 찾고자 하는 값과 일치 → 값을 찾은 것이므로 인덱스를 반환
   • 중간 값이 찾고자 하는 값보다 작으면 → 찾고자 하는 값이 오른쪽 절반에 있을 것이므로 왼쪽 인덱스 = 중간 인덱스 + 1
   • 중간 값이 찾고자 하는 값보다 크면 → 찾고자 하는 값이 왼쪽 절반에 있을 것이므로 오른쪽 인덱스 = 중간 인덱스 - 1
4. 반복
   • 배열의 시작 인덱스가 끝 인덱스보다 클 때까지 위의 과정을 반복
     • 반복에 조건이 있기 때문에 while문을 사용
   • mid 값이 target일 경우
     • mid (index값) 반환
   • 값을 찾지 못한 경우
     • 배열에 값이 존재하지 않으면 -1 또는 특정 값을 반환하여 값이 존재하지 않음 반환

특정 값이 어느 index에 있는지 확인하는

public class BinarySearch {

    // 반복적 방식
    public static int binarySearch(int[] arr, int target) {
        int left = 0; // 계속 중간 mid가 정해져야하기 때문에 0이더라도 무시하지 않고 지정해줘야함
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 자동 캐스팅으로 내림

            if (arr[mid] == target) {
                return mid; // 값을 찾은 경우 인덱스 반환
            } else if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 절반으로 이동
            } else {
                right = mid - 1; // 왼쪽 절반으로 이동
            }
        }

        return -1; // 값을 찾지 못한 경우 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 7;

        int result = binarySearch(arr, target);
        System.out.println("Iterative Binary Search Result: " + result); // 출력: 3

}

---

슬라이딩 윈도우

• Array, List 선형 자료구조에서 연속적인 구간/부분에서의 합, 곱, 최댓값, 최솟값 등 특정 값을 효율적으로 계산하는 알고리즘
  • 구간에서 딱 한번만 계산 → 시작/끝 조절을 통한 새로운 구간에서 다음값
• O(n)의 시간 복잡도
  • 윈도우 크기 상관없이 요소를 한번씩만 넣었다 빼면서 처리하기 때문에

윈도우

• 구간 내에서 고정된 크기 또는 가변 크기의 연속된 요소
• 구간 내에서 한 요소씩 이동시키면서 필요한 값을 계산

슬라이딩 윈도우 Algorithm Flow

1. 초기 계산
   • 배열의 처음 k개의 요소로 초기 윈도우의 값을 계산
2. 윈도우 이동
   • 윈도우를 한 칸 오른쪽으로 이동시키면서 새로운 요소를 추가하고, 이전 윈도우에서 빠져나가는 요소를 제거하여 새로운 값을 계산

윈도우의 최대 합을 구하는 예제

public class SlidingWindow {

    public static int maxSum(int[] arr, int k) {
    
		    // 윈도우 크기 검증
        int n = arr.length;
        if (n < k) {
            System.out.println("윈도우 크기가 배열보다 큽니다.");
            return -1; // int 는 null이 안되기 때문에
        }

        // 첫 윈도우의 합을 계산
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        int maxSum = windowSum;

        // 슬라이딩 윈도우로 배열 탐색
        for (int i = k; i < n; i++) {
            windowSum += arr[i] - arr[i - k]; // 새로 들어온 요소를 더하고, 이전 윈도우의 첫 요소를 뺌
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println("최대 구간 합: " + maxSum(arr, k)); // 출력: 9
    }
}

배열 [2, 1, 5, 1, 3, 2] 와 k = 3 일 때:

• 초기 합: 2 + 1 + 5 = 8
• 다음 윈도우: 1 + 5 + 1 = 7
• 다음 윈도우: 5 + 1 + 3 = 9 (최대 합 갱신)
• 다음 윈도우: 1 + 3 + 2 = 6

---

동전 교환 알고리즘 Coin Change Problem

1. 동전 사용
   • 가장 큰 단위의 동전부터 시작하여, 해당 동전으로 교환 가능한 최대 개수를 계산
   • 현재 동전 단위로 교환 가능한 개수
   • java코드 복사 int coinCount = amount / coin;
   • 해당 동전의 개수를 카운터에 추가
   • java코드 복사 count += coinCount;
   • 교환 후 남은 금액을 업데이트
     • %= 해당 값에 몫을 다시 지정하는 것 직관적으로 생각

     java코드 복사
     amount %= coin;
     

2. 다음 동전 단위로 이동:
   • 다음 작은 단위의 동전으로 이동하여 3단계를 반복
   • 이 과정은 동전 단위 배열의 끝까지 진행
3. 결과 출력:
   • 동전 교환이 완료된 후, 최종 동전 개수를 출력

package Algorithm;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class Greedy_CoinChange {

  public static void main(String[] args) {
    int[] coins = {500, 100, 50, 10};
    int amount = 170;

    // 동전 별 사용 갯수 저장 map
    Map<Integer, Integer> coinUsage = new HashMap<>();

    // 전체 사용 코인 갯수 출력
    int totalCoin = getMinimumCoins(coins, amount, coinUsage);
    System.out.println("전체 동전 숫자 : " + totalCoin);

    // 코인 별 가지고 갯수 출력
    for (int coin : coins) {
      System.out.println(coin + "원 사용 갯수 : " + coinUsage.get(coin));
    }
  }

  public static int getMinimumCoins(int[] coins, int amount, Map<Integer, Integer> coinUsage) {

    int count = 0;

    // coins 내림차순으로 정렬
    Integer[] coinsInteger = Arrays.stream(coins)
        .boxed()
        .toArray(Integer[]::new);

    Arrays.sort(coinsInteger, Comparator.reverseOrder());

    // 큰 숫자 coin 부터 계산
    for (Integer coin : coinsInteger) {
      // 동전 별 갯수 구하기
      int numCoins = amount / coin;
      // 동전 별 갯수 등록
      coinUsage.put(coin, numCoins);
      // 총 숫자 세기
      count += numCoins;
      // 남은 돈 계산
      amount %= coin;
    }

    return count;
  }
}

 

---

모든 코드를 스스로 적으면서 정리를 하다보니 조금 시간이 초과가 되었지만 그래도 꾸준히 계속 공부할 수 있도록