[코딩 테스트] 22일차: 수학 문제

수학 문제

수학 문제는 알고리즘 문제에서 자주 출제되며, 수학적 사고를 요구합니다. 이번 글에서는 소수 찾기, 최대 공약수와 최소 공배수, 수열 문제에 대해 알아보겠습니다.

소수 찾기 (Prime Number)

소수는 1과 자기 자신 외에 약수가 없는 자연수입니다. 소수 찾기 알고리즘으로는 에라토스테네스의 체가 자주 사용됩니다.

예제: 소수 찾기 구현 (에라토스테네스의 체)

JavaScript

function sieveOfEratosthenes(n) {
  const primes = Array(n + 1).fill(true);
  primes[0] = primes[1] = false;

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes.reduce((acc, prime, index) => {
    if (prime) acc.push(index);
    return acc;
  }, []);
}

console.log(sieveOfEratosthenes(30)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Python

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False

    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False

    return [i for i, prime in enumerate(primes) if prime]

print(sieve_of_eratosthenes(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

최대 공약수와 최소 공배수 (GCD and LCM)

최대 공약수(GCD)는 두 수의 공통 약수 중 가장 큰 수이며, 최소 공배수(LCM)는 두 수의 공통 배수 중 가장 작은 수입니다. 유클리드 호제법을 이용하여 GCD를 구할 수 있으며, LCM은 GCD를 이용하여 구할 수 있습니다.

예제: 최대 공약수와 최소 공배수 구현

JavaScript

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

console.log(gcd(12, 18)); // 6
console.log(lcm(12, 18)); // 36

Python

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(12, 18)) # 6
print(lcm(12, 18)) # 36

수열 문제 (Sequence Problem)

수열 문제는 특정 패턴을 가진 수의 나열을 찾는 문제입니다. 피보나치 수열이 대표적인 예입니다.

예제: 피보나치 수열 구현

JavaScript

function fibonacci(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

console.log(fibonacci(6)); // 8
console.log(fibonacci(10)); // 55

Python

def fibonacci(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fibonacci(6)) # 8
print(fibonacci(10)) # 55

연습 문제

문제 1: 주어진 범위 내의 소수 찾기

주어진 범위 내의 모든 소수를 찾는 프로그램을 작성하세요.

JavaScript

function primesInRange(start, end) {
  const primes = Array(end + 1).fill(true);
  primes[0] = primes[1] = false;

  for (let i = 2; i <= Math.sqrt(end); i++) {
    if (primes[i]) {
      for (let j = i * i; j <= end; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes.reduce((acc, prime, index) => {
    if (prime && index >= start) acc.push(index);
    return acc;
  }, []);
}

console.log(primesInRange(10, 50)); // [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Python

def primes_in_range(start, end):
    primes = [True] * (end + 1)
    primes[0] = primes[1] = False

    for i in range(2, int(end**0.5) + 1):
        if primes[i]:
            for j in range(i * i, end + 1, i):
                primes[j] = False

    return [i for i in range(start, end + 1) if primes[i]]

print(primes_in_range(10, 50)) # [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

문제 2: 두 수의 최대 공약수와 최소 공배수 구하기

두 수의 최대 공약수와 최소 공배수를 구하는 프로그램을 작성하세요.

JavaScript

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

console.log(gcd(48, 180)); // 12
console.log(lcm(48, 180)); // 720

Python

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(48, 180)) # 12
print(lcm(48, 180)) # 720

결론

이번 글에서는 코딩 테스트 준비를 위해 수학 문제에 대해 배웠습니다. 이를 통해 소수 찾기, 최대 공약수와 최소 공배수, 수열 문제의 구현 방법을 익혔습니다. 다음 글에서는 문제 풀이 전략과 팁에 대해 알아보겠습니다.

다음 글에서 만나요!