[Algorithm] 기초 수학 구현하기

1. 최장 맨해튼 거리

맨해튼 거리는 x,y 평면의 두개의 점에서 거리를 최단 거리로 구하는 문제이다. 맨해튼 거리

문제의 의미는 결국 좌표평면 위헤서의 어떤 구현이라는 걸 보여주는 단어이기 때문에 맨해튼

거리로 거리를 측정하라는 표현에 우리는 문제를 풀면서 좌표평면의 개념을 떠올려야 한다

완전 탐색

주어지는 수는 4개이기 때문에 좌표는 두개 밖에 생성이 안된다. 실제로 가능한 경우의 수는 24가지

정도이다. a,b,c,d를 무작위로 배열 한뒤 중복되지 않도록 for ~ if ~ continue로 처리 하여 각 점의

x,y 값을 정하고, distance 값을 구하기 위해 abs 함수를 이용한다. 나온 dist 값들 중 최대값을 구하기

위해 max 함수를 사용한다.

S = list(map(int, input().split()))
ans = 0
for a in S:
    x1 = a
    for b in S:
        # 수를 중복해서 사용하면 안 된다!
        if a == b:
            continue
        y1 = b
        for c in S:
            if a == c or b == c:
                continue
            x2 = c
            for d in S:
                if a == d or b == d or c == d:
                    continue
                y2 = d
                # 맨해튼 거리 계산
                dist = abs(x1 - x2) + abs(y1 - y2)
                # 가장 큰 값으로 정답 갱신
                ans = max(ans, dist)

print(ans)

2. 8진수 계산

N진법으로 변환하는 함수를 수도코드로 생각해보면 일단 10진수를 입력받고 for 문을 돌려

10진수 >  N 일때 까지만 나누기를 실행하고 나눈 몫을 append 하고.... 알고리즘은 바로 떠오

를 정도로 단순하지만 코드적으로 복잡하다는 것을 알 수 있다. 아래의 코드는 10진법을 2진법으로

바꾸는 python 코드이다

A = int(input())
result = []
while A:
    result.append(str(A % 2))
    A //= 2
print(''.join(reversed(result)))

python운 2,8,16 진수에 대한 내장 함수를 제공한다 . 각각 bin(),oct(),hex() 함수이다.

각 함수의 사용법도 어렵지 않다 함수의 인자에 바꾸고자 하는 정수를 넣으면 해당 진수로 변환

한 결과를 문자열로 반환한다. 대신 2진수를 0b, 8진수는 0o ,16진수는 0x 접두사가 붙어있다.

import sys
input = sys.stdin.readline

N = int(input())
# 배열로 모든 정수를 입력.
S = list(map(int, input().split()))

# 모든 정수를 더한 후에, 8진수 변환
print(oct(sum(S))[2:])

3. 소수 구하기

하나의 수가 소수인지 판별할 때는 위 방법도 충분히 효율적입다. 그러나 이 문제처럼 소수를 여러 번

판 별해야 될떄는 에라토스테네스의 체를 사용하는 것이 더 효율적이다. 에라토스테네스의 체는 어떤 수

의 약수를 세는 것보다 배수를 세는 것이 훨씬 쉽다는 것에서 출발한다. 어떤수가 소수라면, 그 소수에 대한

배수를 모두 제거해주는 방식으로 동작한다.

def Sieve(N):
    # 초기에는 모두 소수일 수 있다고 가정한다
    is_prime = [1 for _ in range(N + 1)]
    prime = []
    for i in range(2, N + 1):
        # 소수가 아니라고 판정된 수는 건너뛴다
        if not is_prime[i]:
            continue
        prime.append(i)
        # 소수의 배수들을 쳐내는 과정
        for j in range(2 * i, N + 1, i):
            is_prime[j] = 0
    return prime

4. 에라토스테네스의 체

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 에라토스테네스의 체를 사용하면 대량의 소수를 빠르게 

구할 수 있다. 에라토스테네스 체를 구하는 방법은 다음과 같다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2의 배수를 지운다
3. 남은 수중 가장 작은 수(3,5,7..)의 배수를 지운다
4. 3의 과정을 반복한다.
5. 소수만 남는다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]