기초 수학과 구현

🧑‍💻 기초 수학과 구현

멀티잇 코딩테스트 러닝클래스'Python 5월반

최장 맨해튼 거리

|x1 - x2| + |y1 - y2| 의 값이 최장 맨해튼 거리다

• (x1, y1) , (x2, y2)

4개의 숫자가 주어지는데, 그 숫자로 만들 수 있는 제일 긴 맨해튼 거리를 만드는 것이다

permutations을 사용하여 주어진 4개의 숫자로 만들 수 있는 수열을 모두 구한다

• 그리고 맨해튼 거리 공식을 이용하여, 최장 맨해튼 거리를 구하면 된다

from itertools import permutations

numbers = list(map(int, input().split()))
answer = 0

for i in permutations(numbers, len(numbers)):
    answer = max(answer, (abs(i[0] - i[2]) + abs(i[1] - i[3])))

print(answer)

🚨🚨 팁, permutations 말고, 4중 for문을 통해서 풀 수 있다

• 단 4중 for문을 순회할 때에는, 중복되는 값이 없도록 한다

8진수 계산기

주어진 10 진수를 더하고, 더한 값을 8진수로 표시한다

while문을 사용하고, 8로 나눠서, 남은 값들을 eights 라는 리스트에 넣었다

eights[-1::-1] 을 해서, 숫자들을 뒤집어 준다

• 리스트에 append를 썼기 때문에, 원래 답과는 반대로 숫자들이 나열되어 있다

num = int(input())
numbers = list(map(int, input().split()))

tens = sum(numbers)
eights = []

while tens > 0:
    num = tens % 8
    tens = tens // 8
    eights.append(num)

eights = ''.join(map(str, eights[-1::-1]))    

print(int(eights))

🚨🚨 bin(), oct(), hex() 라는 내장함수를 사용할 수 있다

• bin() 은 이진수 / oct() 8진수 / hex() 16진수
• 출력될 때에는 0b / 0o / 0x 가 붙어서 [2:] 부터 출력해줘야 한다

소수 찾기

주어진 수열에서, 소수 번째 숫자들을 모두 더하는 것이다

먼저 1부터 100,000번째 소수들을 구했다

그리고 구한 소수를 인덱스로 활용해서 문제를 풀었지만, FAIL(Timeout)이 있어서 틀렸다

# ---------------- 틀린 코드 --------------------

# 100,000까지 모든 소수 구하기
prime = set(range(2, 100001))

for i in range(2, 100001):    
    if i in prime:
        not_prime = set(range(2 * i, 100001, i))
        prime -= not_prime

# 수열을 받고, 수열 안에 있는 값들 더하기
N = int(input())
nums = list(map(int, input().split()))
answer = 0
i = 0

while N > list(prime)[i] - 1:

    answer += nums[list(prime)[i] - 1]
    i += 1

print(answer)

일단 제일 중요한 것은 모든 소수를 구할 때에, 시간을 줄이기 위해 for문에서 range의 범위를 반으로 줄였다

• for i in range(2, 100002 // 2):
• 1차적으로 소수 구하기를 할 때, 시간이 절약되었다

while문에서 for문으로 바꿨다

• for문으로 구했던 소수를 순회할 수 있다고 생각해서, for문으로 바꿨다

# ---------------- 정답 코드 --------------------
# 100,000까지 모든 소수 구하기
prime = set(range(2, 100002))

for i in range(2, 100002 // 2):    
    if i in prime:
        not_prime = set(range(2 * i, 100002, i))
        prime -= not_prime

# 수열을 받고, 수열 안에 있는 값들 더하기
N = int(input())
nums = list(map(int, input().split()))
answer = 0

for i in prime:
    if N >= i:
        answer += nums[i - 1]
    else:
        break


print(answer)