Baekjoon

백준 프로필 : www.acmicpc.net/user/hjoon19
solved.ac : https://solved.ac/profile/hjoon19

알고리즘 목록

• 에라토스테네스의 체
  효율적인 소수 찾기 알고리즘, 2부터 n까지의 배수를 지우다보면, 마지막에는 소수만 남게 된다.
  특정 범위가 주어지고, 그 범위 내의 모든 소수를 찾아야하는 경우 효율적으로 범위를 줄일 수 있다.
  e.g.) 1 ~ 144의 범위인 경우, 2부터 Math.sqrt(144) 까지의 배수를 구하여 제거하면 된다. (0, 1은 소수가 아니기 때문에 선제적으로 제외)
  

• 그리디 알고리즘
  현재 상황에서 지금 당장 좋은 것만 고르는 방법
  매 순간 가장 최적의 답을 선택하여 적합한 결과를 도출하려는 것이다.
  

• 브루트 포스 알고리즘
  조합 가능한 모든 문자열을 하나씩 대입해 보는 방식, 흔히 암호학에서 연구 하지만 경우의 수가 늘어날 수록 매우 비효율적이다.
  

• 투포인터
  정렬된 배열에서 특정 조건을 만족하는 값을 빠르게 찾기 위해 사용하는 알고리즘
  포인터(Index)를 배열의 양쪽 끝 또는 특정 위치에서 시작하고 조건에 따라 이동하면서 탐색 범위를 줄여나가는 방식
  

• 최소공배수 (LCM), 최대공약수 (GCD)
  최대공약수를 (GCD) 빠르게 구할 수 있는 방법
  

  public static long getGCD(long a, long b) {
    if (b == 0) {
        return a;
    }
    return getGCD(b, a % b);
  }

  • 해당 방법으로 간단하게 구할 수 있으나 재귀 방식으로 구하기 때문에 숫자가 커지게 되면 오버플로우 등의 문제가 발생한다.

  public static int getGCD(int a, int b) {
    while (b != 0) {
      int temp = a % b;
      a = b;
      b = temp
    }
  
    return a;
  }

  • 그래서 while 반복문 형태로 구할 수 있다.
  • 재귀가 아니기 때문에 성능이 안정적이고 입력 수가 크거나 많은 경우 해당 방법을 사용. (long 형식으로 입력을 많이 받는 편.)

  최소공배수 (LCM)

  a * b / getGCD(a, b)
  

  • 두 수 a, b의 최소공배수는 두 수 a, b를 곱한 것에 최대공약수를 나누면 빠르게 최소공배수를 구할 수 있다.