728x90
728x90
728x90
728x90

숫자에는 우리가 미처 알지 못했던 흥미로운 규칙과 비밀이 숨어 있습니다. 이번 포스팅에서는 몇 가지 간단한 규칙을 통해 숫자의 매력을 탐구해볼까요? 각 숫자의 배수성 판단을 위한 재미있는 규칙을 살펴보며, 이를 효율적으로 활용할 방법에 대해 알아보겠습니다.

 

2의 배수: 마지막 자리가 짝수인지 확인

숫자가 짝수인지 판단하는 가장 간단한 방법은 마지막 자리를 보는 것입니다. 마지막 자리가 0, 2, 4, 6, 8 중 하나라면 그 숫자는 짝수입니다.

예시:

  • 12 → 짝수
  • 35 → 홀수
number = 12
if number % 2 == 0:
    print(f"{number}은 짝수입니다.")
else:
    print(f"{number}은 홀수입니다.")

 

3의 배수: 각 자리 숫자의 합

어떤 숫자가 3의 배수인지 확인할 때, 각 자리 숫자의 합이 3으로 나누어지는지 확인하면 됩니다.

예시:

  • 27 → (3의 배수)
  • 134 → (3의 배수가 아님)
def is_multiple_of_3(number):
    digit_sum = sum(int(digit) for digit in str(number))
    return digit_sum % 3 == 0

number = 27
if is_multiple_of_3(number):
    print(f"{number}은 3의 배수입니다.")
else:
    print(f"{number}은 3의 배수가 아닙니다.")

 

4의 배수: 마지막 두 자리가 4의 배수

숫자가 4의 배수인지 확인하려면 마지막 두 자리가 4로 나누어떨어지는지 보면 됩니다.

예시:

  • 316 → (4의 배수)
  • 123 → (4의 배수가 아님)
number = 316
last_two_digits = int(str(number)[-2:])
if last_two_digits % 4 == 0:
    print(f"{number}은 4의 배수입니다.")
else:
    print(f"{number}은 4의 배수가 아닙니다.")

 

5의 배수: 마지막 자리가 0 또는 5

5의 배수인지 확인하려면 숫자의 끝이 0이나 5인지 확인하세요.

예시:

  • 25 → 5의 배수
  • 42 → 5의 배수가 아님
number = 25
if str(number)[-1] in ('0', '5'):
    print(f"{number}은 5의 배수입니다.")
else:
    print(f"{number}은 5의 배수가 아닙니다.")

 

6의 배수: 2의 배수이면서 3의 배수

숫자가 6의 배수인지 확인하려면 두 가지 조건을 모두 만족해야 합니다: 짝수이면서 각 자리 숫자의 합이 3으로 나눠져야 합니다.

예시:

  • 18 → 짝수이고 (3의 배수, 따라서 6의 배수)
  • 20 → 짝수지만 (3의 배수가 아님)
def is_multiple_of_6(number):
    return number % 2 == 0 and sum(int(digit) for digit in str(number)) % 3 == 0

number = 18
if is_multiple_of_6(number):
    print(f"{number}은 6의 배수입니다.")
else:
    print(f"{number}은 6의 배수가 아닙니다.")

 

7의 배수: 독특한 규칙

7의 배수를 확인하는 규칙은 다소 복잡할 수 있습니다. 숫자에서 나누기 10을 한 몫에서 1의 자리 숫자에 2를 곱한 숫자를 뺍니다.

예시:

  • 371 → 37 - (1 x 2), 35는 7의 배수
def is_multiple_of_7(number):
    while number > 99:
        last_digit = number % 10
        remaining_number = number // 10
        number = remaining_number - (last_digit * 2)
    return number % 7 == 0

number = 371
if is_multiple_of_7(number):
    print(f"{number}은 7의 배수입니다.")
else:
    print(f"{number}은 7의 배수가 아닙니다.")

 

8의 배수: 마지막 세 자리에 주목하라

숫자가 8의 배수인지 확인하려면 마지막 세 자리가 8로 나누어떨어지는지 보면 됩니다.

예시:

  • 1048 → (8의 배수)
  • 1234 → (8의 배수가 아님)
number = 1048
last_three_digits = int(str(number)[-3:])
if last_three_digits % 8 == 0:
    print(f"{number}은 8의 배수입니다.")
else:
    print(f"{number}은 8의 배수가 아닙니다.")

 

9의 배수: 각 자리 수의 합이 9의 배수

각 자리 숫자의 합이 9로 나누어지는지 확인하면 그 숫자가 9의 배수인지 알 수 있습니다.

예시:

  • 729 → (9의 배수)
  • 812 → (9의 배수가 아님)
def is_multiple_of_9(number):
    digit_sum = sum(int(digit) for digit in str(number))
    return digit_sum % 9 == 0

number = 729
if is_multiple_of_9(number):
    print(f"{number}은 9의 배수입니다.")
else:
    print(f"{number}은 9의 배수가 아닙니다.")

 

마무리: 숫자의 규칙을 활용해보세요!

이렇게 다양한 숫자의 규칙들을 알고 있다면, 숫자와 관련된 문제를 더 빠르고 효율적으로 풀 수 있습니다. 간단한 규칙 하나가 큰 차이를 만들어낼 수 있죠. 앞으로 숫자를 다룰 때 이러한 규칙을 떠올리며 활용해 보세요!

 

독자에게 질문!

  • 숫자 2532는 어떤 규칙에 해당할까요?
  • 여러분이 알고 있는 다른 흥미로운 숫자 규칙은 무엇인가요?

댓글로 여러분의 생각을 나눠보세요! 😊

728x90
728x90
728x90
728x90

최대공약수(Greatest Common Divisor, GCD)는 두 개 이상의 수가 가질 수 있는 가장 큰 공통 인수를 의미합니다. GCD는 수학적 문제뿐만 아니라 컴퓨터 과학에서도 중요한 역할을 하며, 이와 관련된 다양한 알고리즘이 발전해 왔습니다. 이번 글에서는 가장 기본적인 방법부터 가장 효율적인 알고리즘까지 살펴보겠습니다.

 

1. 브루트 포스 방식

최대공약수를 구하는 가장 단순한 방법은 브루트 포스 방식입니다. 이 방법은 두 수의 공통 인수들을 모두 찾아내어 그 중 가장 큰 값을 찾는 방식입니다.

# Python으로 구현한 브루트 포스 방식

def gcd_brute_force(a, b):
    min_val = min(a, b)
    for i in range(min_val, 0, -1):
        if a % i == 0 and b % i == 0:
            return i

# 예시
print(gcd_brute_force(48, 18))  # 출력: 6

이 방식은 두 수의 최소값에서부터 하나씩 감소하면서 두 수의 공통으로 나누어지는 가장 큰 값을 찾습니다. 간단하지만, 두 수가 클 경우 반복 횟수가 매우 많아져 비효율적입니다.

 

2. 유클리드 호제법

유클리드 호제법은 GCD를 계산하는 데 있어서 훨씬 더 효율적인 방법으로 알려져 있습니다. 이 방법은 두 수를 나눈 나머지를 이용하여 반복적으로 계산합니다. 기본 아이디어는 두 수의 GCD가 작은 수와 그 나머지의 GCD와 같다는 점입니다.

# Python으로 구현한 유클리드 호제법

def gcd_euclidean(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 예시
print(gcd_euclidean(48, 18))  # 출력: 6

이 방법은 연산을 반복하면서 나머지가 0이 될 때까지 두 수를 갱신합니다. 유클리드 호제법의 시간 복잡도는 로, 브루트 포스 방식보다 훨씬 빠릅니다.

 

3. 스테인 알고리즘(이진 GCD)

나눗셈 연산보다 비트 연산이 더 효율적인 컴퓨터에서 쓸만한 스테인 알고리즘이 있습니다. 이 알고리즘은 나눗셈을 사용하지 않고 이진 연산을 사용하여 GCD를 계산합니다.

스테인 알고리즘은 다음과 같은 규칙을 따릅니다:

  • 두 수가 모두 짝수일 경우, GCD는 두 수를 2로 나눈 값의 GCD에 2를 곱한 값입니다.
  • 두 수 중 하나만 짝수일 경우, GCD는 짝수가 아닌 수와 동일한 수의 GCD입니다.
  • 두 수가 모두 홀수일 경우, 두 수의 차를 이용하여 GCD를 계산합니다.
# Python으로 구현한 스테인 알고리즘

def gcd_stein(a, b):
    if a == b:
        return a
    if a == 0:
        return b
    if b == 0:
        return a

    if (a & 1) == 0:  # a가 짝수
        if (b & 1) == 0:
            return gcd_stein(a >> 1, b >> 1) << 1
        else:
            return gcd_stein(a >> 1, b)
    if (b & 1) == 0:  # b가 짝수
        return gcd_stein(a, b >> 1)

    # 둘 다 홀수일 때
    if a > b:
        return gcd_stein((a - b) >> 1, b)
    return gcd_stein((b - a) >> 1, a)

# 예시
print(gcd_stein(48, 18))  # 출력: 6

스테인 알고리즘은 특정 상황에서 유클리드 호제법보다 더 빠른 성능을 보입니다. 특히, 컴퓨터의 하드웨어에서 나눗셈 연산보다 비트 시프트가 더 빠른 경우 효율적입니다.

 

4. 알고리즘 비교

유클리드 호제법과 스테인 알고리즘 모두 상당히 효율적이지만, 상황에 따라 비트 연산이 가능한 스테인 알고리즘이 더 나은 성능을 발휘할 수 있습니다.

 

결론

최대공약수를 구하는 다양한 방법 중에서 브루트 포스 방식은 가장 단순하지만, 큰 수에 대해서는 비효율적입니다. 유클리드 호제법은 널리 사용되는 효율적인 방법이며, 스테인 알고리즘은 비트 연산을 이용하여 추가적인 최적화를 이룰 수 있는 방법입니다. 각 방법의 특성을 이해하고 상황에 맞는 알고리즘을 선택하는 것이 중요합니다.

다양한 상황에서 가장 적합한 알고리즘을 선택함으로써 연산 효율성을 극대화할 수 있습니다. 특히, 하드웨어와 소프트웨어의 특성에 따라 나눗셈과 비트 연산의 속도 차이가 클 경우 스테인 알고리즘을 선택하면 큰 차이를 만들어낼 수 있습니다.

728x90
728x90
728x90
728x90

소수 판별은 알고리즘의 중요한 개념 중 하나로, 소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 양의 정수를 의미합니다. 이번 포스팅에서는 소수를 판별하는 여러 알고리즘을 가장 단순한 방법부터 효율적인 방법까지 단계적으로 살펴보겠습니다.

 

1. 가장 단순한 방법: 나이브 접근법

가장 기본적인 소수 판별 알고리즘은 단순하게 숫자 n에 대해 2부터 n-1까지의 모든 수로 나누어 보는 것입니다.

# 나이브 소수 판별 함수
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

이 방식은 이해하기 쉽지만, 비효율적입니다. 특히 n이 커질수록 반복의 횟수가 너무 많아져 계산 속도가 급격히 느려집니다. 시간 복잡도는 O(n)입니다.

 

2. 개선된 방법: 제곱근까지 검사하기

나이브 접근법의 가장 큰 문제점은 불필요한 연산이 많다는 점입니다. 실제로는 n의 제곱근까지만 검사하면 소수 여부를 판단할 수 있습니다. 예를 들어, n = 36이라면, 6보다 큰 수로는 이미 이전에 나누어진 결과를 통해 나누어지는지 확인한 것입니다.

import math

# 제곱근을 이용한 소수 판별 함수
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

이 방법은 n의 제곱근까지만 반복하므로 시간 복잡도가 O(√n)으로 줄어듭니다. 이는 이전 방법보다 훨씬 효율적입니다.

 

3. 더 나은 개선: 6의 배수 최적화

소수의 대부분은 6의 배수와 관련된 패턴을 가집니다. 2와 3을 제외하고, 모든 소수는 6k-1 또는 6k+1 형태를 가집니다. 이를 이용해 더 효율적인 소수 판별 알고리즘을 만들 수 있습니다.

import math

# 6의 배수를 활용한 소수 판별 함수
def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

이 방법은 이전의 제곱근 접근법을 최적화한 것으로, ii + 2 두 값을 검사함으로써 불필요한 계산을 줄입니다. 시간 복잡도는 여전히 O(√n)이지만, 실제로는 반복 횟수가 줄어들어 더 빠릅니다.

 

4. 에라토스테네스의 체: 여러 수의 소수 여부 판별하기

여러 개의 숫자에 대해 소수를 판별해야 할 때는 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하는 것이 효율적입니다. 이 방법은 특정 범위 내의 모든 소수를 빠르게 찾을 수 있는 알고리즘입니다.

# 에라토스테네스의 체를 이용한 소수 리스트 생성 함수
def sieve_of_eratosthenes(limit):
    primes = [True] * (limit + 1)
    p = 2
    while p * p <= limit:
        if primes[p]:
            for i in range(p * p, limit + 1, p):
                primes[i] = False
        p += 1
    return [p for p in range(2, limit + 1) if primes[p]]

# 예시: 50 이하의 모든 소수 찾기
print(sieve_of_eratosthenes(50))

이 방법은 크기가 큰 범위에서 소수를 빠르게 찾을 수 있도록 설계되었습니다. 시간 복잡도는 O(n log log n)으로 매우 효율적입니다.

 

5. 세그먼트 에라토스테네스의 체: 큰 범위에서의 소수 판별

에라토스테네스의 체보다 더 효율적인 방법 중 하나는 세그먼트 에라토스테네스의 체(Segmented Sieve of Eratosthenes)입니다. 이 알고리즘은 매우 큰 범위에서 소수를 찾고자 할 때 사용됩니다. 세그먼트 체는 기본적으로 에라토스테네스의 체를 여러 구간으로 나누어 소수를 판별하는 방법입니다.

import math

# 세그먼트 에라토스테네스의 체 함수
def segmented_sieve(limit):
    segment_size = int(math.sqrt(limit)) + 1
    primes = sieve_of_eratosthenes(segment_size)
    low = segment_size
    high = 2 * segment_size
    sieve = [True] * (segment_size)
    
    while low < limit:
        if high > limit:
            high = limit
        sieve = [True] * (high - low)

        for prime in primes:
            start = max(prime * prime, (low + prime - 1) // prime * prime)
            for j in range(start, high, prime):
                sieve[j - low] = False

        for i in range(low, high):
            if sieve[i - low]:
                print(i, end=" ")

        low = low + segment_size
        high = high + segment_size

# 예시: 100 이하의 모든 소수 찾기
segmented_sieve(100)

이 알고리즘은 메모리 사용량을 줄이면서도 큰 숫자 범위에서 소수를 찾는 데 매우 효율적입니다. 특히, 큰 n 범위에서 소수를 판별할 때 메모리 문제를 해결하고, 각 구간에 대해 병렬 처리를 사용할 수 있습니다. 시간 복잡도는 여전히 O(n log log n)이지만, 범위가 커질 때 더 효율적으로 작동합니다.

 

결론

  • 나이브 접근법은 이해하기 쉽지만 매우 비효율적입니다 (O(n)).
  • 제곱근 최적화는 반복 횟수를 줄여 효율성을 높였습니다 (O(√n)).
  • 6의 배수 최적화는 소수의 특성을 활용해 더 적은 연산으로 소수 여부를 판별합니다 (O(√n)).
  • 에라토스테네스의 체는 여러 개의 숫자에 대해 소수를 구할 때 가장 효율적인 방법 중 하나입니다 (O(n log log n)).
  • 세그먼트 에라토스테네스의 체는 매우 큰 범위에서 소수를 판별할 때 메모리 효율성을 극대화할 수 있는 방법입니다.

소수 판별 문제를 해결하는 다양한 접근 방법을 소개했으니, 상황에 맞게 적절한 알고리즘을 선택해 활용해 보세요. 코드를 직접 실행해 보면서 각 방법의 효율성을 체감하는 것도 좋은 학습 방법이 될 것입니다.

728x90
728x90
728x90
728x90

최단 경로 문제는 그래프 사이에서 두 노드 사이의 가장 짧은 경로를 찾는 문제이다. 최단 경로 알고리즘에는

1. 너비 우선 탐색 BFS

2. 다익스트라 알고리즘

3. 벨만-포드 알고리즘

4. 플로이드-워셜 알고리즘

이 있다

 

그래프

그래프는 상하위의 개념이 없이 각각의 노드와 노드들을 간선(edge)으로 연결한 자료구조이다.

지도 어플의 최단거리. 배송 최소이동거리, 지하철 노선도의 최단경로 등에서 활용되고 있다.

너비 우선 탐색

그래프에서 가까운 노드부터 탐색하는 알고리즘으로 간선의 길이가 없을 때 사용하는 알고리즘

a노드에서 인접한 노드 e, b, d, h로 이동하면서 탐색하는 알고리즘

def DFS(graph, root):
    open = [root]
    close = []

    while open:
        n = open.pop()
        close.append(n)
        if n not in close:
            close.append(n)
            open += graph[n] - set(close)
    return close

print(BFS(graph_list, root_node))

 

다익스트라

간선의 길이가 양수 일 때 사용하는 알고리즘이며 하나의 노드에서 다른 노드들까지 최단거리를 계산하는 알고리즘

  1. 아직 선택되지 않은 노드 중에서 가장 간선의 길이가 짧은 노드를 선택한다.
  2. 1번에서 선택된 노드와 연결된 다른 노드의 최단 거리를 갱신한다.
  3. 탐색하지 않은 노드가 있으면 1번으로 돌아간다.
import heapq


def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    while queue:
        current_distance, current_destination = heapq.heappop(queue)

        if distances[current_destination] < current_distance:
            continue

        for new_destination, new_distance in graph[current_destination].items():
            distance = current_distance + new_distance
            if distance < distances[new_destination]:
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])

벨만-포드

간선의 길이가 음수일 때도 사용가능하다 사이클이 음의 값을 가지면 사용 불가능하다.

  • 시작 노드에 대해서 거리를 0으로 초기화, 나머지 노드는 거리를 무한으로 설정
  • 정점 수(n) -1 만큼 다음 과정을 반복
  • 매 반복 마다 모든 간선 확인
  • 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 거리 정보 갱신
  • n-1번 반복 이후, n번째 반복에서도 거리 값이 갱신된다면 음수 순환이 존재

다익스트라는 방문하지 않는 노드 중에서 가장 가까운 노드를 방문했지만 벨만-포드는 매 반복마다 모든 간선을 확인한다는 것이 차이점이다.

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
INF = sys.maxsize

adj = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    adj[a].append((c, b))


def ford():
    ans = [INF] * (n + 1)
    ans[1] = 0
    for i in range(1, n):
        for j in range(1, n + 1):
            for c, b in adj[j]:
                if ans[j] == INF:
                    continue
                if ans[b] > c + ans[j]:
                    ans[b] = c + ans[j]
    for j in range(1, n + 1):
        for c, b in adj[j]:
            if ans[j] == INF:
                continue
            if ans[b] > ans[j] + c:
                print(-1)
                sys.exit()
    return ans


temp = ford()
for i in range(2, n + 1):
    if temp[i] == INF:
        print(-1)
    else:
        print(temp[i])

 

플로이드 와샬

모든 정점에서 다른 모든 정점으로의 최단거리를 계산할 때 사용하는 알고리즘

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

 

728x90
728x90
728x90
728x90

유클리드 호제법

호제법(互除法)이라는 말은 서로(互) 나누기(除)라는 뜻으로 그리스의 수학자 유클리드의 저서 원론에 적혀있는 최초의 알고리즘으로서  최대공약수를 구하는 방법이다.

 

명제 및 알고리즘

두 양의 정수 a, b(a > b)에 대하여 gcd(a, b) = gcd(a, (b mod b))이다

gcd(a, b)a, b의 최대공약수를 뜻하며 a mod bab로 나눈 나머지이다.

 

파이썬 알고리즘은 다음과 같다

def E(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

증명

gcd(a, b) = G 라하면 적당한 서로수인 정수 A, B에 대해 a = GA, b = GB가 성립한다.

이를 a = bq + r에 대입하면

GA = GBq + r이고

r = G(A - Bq)이다.

 

한편, A - BqB의 관계가 gcd(B, A - Bq) = m (m 1) 즉, A - BqB가 서로소가 아니라고 한다면

B = mk, A - Bq = ml이 성립한다.

A = ml + Bq = ml +mkq = m(l + kq)이므로

mAB의 공약수임을 알수 있다.

그런데 A, B는 서로수 이므로 m = 1이 된다.

처음 가정했던 m ≠ 1과 모순이므로 m≠ 1이 틀렸고

즉, A - BqB는 서로수 이고

"두 양의 정수 a, b(a < b)에 대하여 gcd(a, b) = gcd(b, (a mod b))이다"는 참인 명제가 된다.


활용

1298, 34782의 최대공약수

gcd(34782, 1298) = gcd(1298, 1034), 1298 mod 1034 = 1034

gcd(1298, 1034) = gcd(1034, 264), 1034 mod 264 = 242

gcd(1034, 264) = gcd(264, 242), 364 mod 242 = 22

gcd(264, 242) = gcd(242, 22), 242 mod 22 = 0

따라서 1298, 34782의 최대공약수는 22


참고문헌

Library of Koreandria 블로그 인류 최초의 알고리즘 - 유클리드 호제법

2021월 10월 29일 - 명제 및 알고리즘에서 a, b(a < b)를 a, b(a > b)로 수정

                          명제 및 알고리즘, 증명에서 gcd(a, (a mod b))를 gcd(b, (a mod b))로 수정

2021월 11월 18일 활용 부분에서 최소공배수 ->최대공약수로 변경 항상 헷갈림...

728x90
728x90
728x90
728x90