그리고, 2를 제외한 소수는 모두 홀수이므로 3부터 시작해서 더해서 원하는 짝수가 나오는 홀수 두 개를 찾습니다.
LIMIT = 1000001
prime_list = [True] * (LIMIT)
for i in range(2,1001):
if prime_list[i]:
for j in range(2*i,LIMIT, i):
prime_list[j] = False
while True:
x = int(input())
if(x==0): break
for i in range(3,LIMIT):
if prime_list[i] and prime_list[x-i]:
print(x, '=', i, '+' , x-i)
break
에라토스테네스의 체
: 해당 수보다 작은 모든 수로 나누어 보아서 소수인지 확인하는 방법입니다.
1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 채택하고, 나머지 2의 배수를 지웁니다.
3. 지워지지 않은 수 중 제일 작은 3을 채택하고, 나머지 3의 배수를 모두 지웁니다.
4. 지워지지 않은 수 중 제일 작은 5를 채택하고, 나머지 5의 배수를 모두 지웁니다.
다음과 같은 과정을 반복합니다.
에라토스테네스의 체
n=1000
a = [False,False] + [True]*(n-1)
primes=[]
for i in range(2,n+1):
if a[i]:
primes.append(i)
for j in range(2*i, n+1, i):
a[j] = False
print(primes)
문제에서 최대 공약수가 1인 k의 개수를 구하라는 의미는, n의 서로소를 구하라는 뜻입니다.
서로소의 개수를 구하는 함수는 오일러 파이 함수가 있습니다.
오일러 파이 함수란?
임의의 양의 정수 m에 대하여, m 이하의 양의 정수 중 m과 서로송인 양의 정소의 개수를 구하는 함수입니다.
$$p_1, p_2, ..., p_n$$이 m의 소인수라고 할 때 아래 공식이 성립하게 됩니다.
오일러 파이 함수 식에 대한 증명
\(p\)가 소수라면, 1부터 \(p^k\) 까지의 수 중 \(p\)를 인수로 가지는 숫자의 개수는 \(p^{k-1}\)입니다.
그러므로
$$\Phi(p^k)=p^k - p^{(k-1)}$$
식이 성립됩니다.
그러므로 만약 a가 다음과 같이 정의된다면, 아래의 식으로 나타낼 수 있습니다.
이제 파이썬으로 나타내면 다음과 같습니다.
n = int(input())
answer=n
for i in range(2, round(n**0.5) + 1):
#소인수 이면
if n%i==0:
#소인수 구하기
while n%i==0:
n//=i
#(1-(1/i))
answer*=((i-1)/i)
if n>1:
answer*=1-(1/n)
print(int(answer))
요청과 결과가 동시에 일어난다는 약속으로, 요청을 하면 요청한 자리에서 결과가 주어져야 합니다.
장점 : 일의 순서가 매우 직관적이고 간단합니다.
단점 : 앞의 일이 오래걸리더라도 뒤의 일은 대기해야합니다.
비동기(asynchronous: 동시에 일어나지 않는)
요청한 자리에서 결과가 주어지지 않습니다.
장점 : 앞의 일이 오래걸리면, 그 시간 동안 다른 작업을 할 수 있습니다. 즉, 자원을 효율적으로 사용할 수 있습니다.
단점 : 일의 순서를 직관적으로 생각하기 어려워서, 무엇이 먼저 완료될지 보장할 수 없습니다.
그렇다면, 비동기에서도 순서가 반드시 지켜져야할 때는 어떻게 해야할까요?
예를 들어, 서버에서 데이터를 가져와서 사용할 때는 반드시 데이터를 작업을 끝내야 합니다.
이를 위해 Promise를 사용합니다.
Promise
Promise는 Javascript 비동기 처리에 쓰이는 객체입니다.
비동기 작업의 결과인 미래의 완료 또는 실패와 그 결과 값을 나타냅니다.
이것을 사용하면 비동기 메서드에서 마치 동기 메서드처럼 값을 반환할 수 있습니다.
다만 원하는 최종 결과를 반환하는 것이 아닌, 미래의 어떤 시점에 결과를 제공하겠다는 약속을 반환합니다.
Promise의 값은 다음 중 하나의 상태를 가집니다.
대기(pending) : 이행하지도, 거부하지도 않은 초기 상태
이행(fulfilled) : 연산이 성공적으로 완료됨.
거부(rejected) : 연산이 실패함.
이행이나 거부될 때, 프로미스의 then 메서드에 의해 대기열(큐)에 추가된 처리기들이 호출됩니다.
Promise를 통해 약속을 받는 것은 알겠지만, 그러면 약속 안의 결과값을 받으려면 어떻게 해야할까요?
이를 위해 await을 사용합니다.
Await
await 연산자는 Promise를 기다리기 위해 사용됩니다.
연산자는 반드시 async function 내부에서만 사용할 수 있습니다. asnyc 함수의 본문 외부에서 사용하면 SyntaxError 가 발생합니다.
async가 무엇인지는 await을 설명 후 설명하겠습니다.
await은 다음과 같이 사용할 수 있습니다.
[rv] = await expression;
expression : Promise 혹은 기다릴 어떤 값입니다.
rv : Promise에 의해 만족되는 값이 반환됩니다. Promise가 아닌 경우에는 그 값 자체가 반환됩니다.
await 문은 Promise가 이행(fulfill)되거나 거부(reject) 될 때까지 async function 의 실행을 일시 정지합니다.
Promise가 이행(fulfill)되면 async function 를 일시 정지한 부분부터 실행합니다.
이때 await 문의 반환값은 Promise 에서 이행(fulfill)된 값이 됩니다.
만약 Promise가 거부(reject)되면, await 문은 거부(reject)된 값을 throw합니다.
예제
만약 Promise가 await에 넘겨지면, await은 Promise가 fulfill되기를 기다렸다가, 해당 값을 리턴합니다.
function resolveAfter2Seconds(x) {
return new Promise(resolve => {
setTimeout(() => {
resolve(x);
}, 2000);
});
}
async function f1() {
var x = await resolveAfter2Seconds(10);
console.log(x); // 10
}
f1();
만약 값이 Promise가 아니라면, 해당 값은 resolve된 Promise로 변환되며 이를 기다립니다.
async function f2() {
var y = await 20;
console.log(y); // 20
}
f2();
만약 Promise가 reject되면, reject된 값이 throw됩니다.
async function f3() {
try {
var z = await Promise.reject(30);
} catch(e) {
console.log(e); // 30
}
}
f3();
try블럭 없이 rejected Promise다루기
var response = await promisedFunction().catch((err) => { console.error(err); });
// response will be undefined if the promise is rejected
Async function
Async Function 객체를 반환하는 하나의 비동기 함수를 선언합니다.
비동기 함수는 이벤트 루프를 통해 비동기적으로 작도아는 함수로, 암시적으로 Promise를 사용하여 결과 값을 반환합니다.
구문
async function name([param[, param[, ... param]]]) {
statements
}
name: 함수 이름
async함수는 항상 promise를 반환합니다.
만약 async함수의 반환값이 명시적으로 promise가 아니라면 암묵적으로 promise로 감쌉니다.
예시. 위와 아래의 코드는 같은 내용입니다.
async function foo() {
return 1
}
function foo() {
return Promise.resolve(1)
}
추가적인 내용
async/await 함수의 목적은 사용하는 여러 promise의 동작을 동기스럽게 사용할 수 있게 하고, 어떠한 동작을 여러 promise의 그룹에서 간단하게 동작하게 하는 것입니다. promise가 구조화된 callback과 유사한 것 처럼 async/await 또한 제네레이터(generator)와 프로미스(promise)를 묶는것과 유사합니다.
await과 Promise...then은 다른 것입니다. 두 개 이상의 Promise를 동시에 기다리고 싶다면, Promise...then을 통해 병렬적으로 수행할 수 있습니다.
개념을 제대로 알지 못한 상태에서 비동기를 사용하면서 발생한 문제들
Promise{<pending>} 값을 반환될 때가 있었습니다. 이유 : async 함수는 return이 promise가 아니어도, 암묵적으로 promise로 감싸기 때문이었습니다. 해결 : 해당 함수를 사용하기 위해서는 await 함수() 의 형태를 사용해야 합니다.
많은 Promise 값을 전부 기다려야할 때가 있었습니다. 해결 : Promise.all()을 사용하여, 순회 가능한 객체에 주어진 모든 프로미스가 이행한 후, 혹은 프로미스가 주어지지 않았을 때 이행하는 프로미스를 반환합니다. 이 때, 프로미스 중 하나라도 거부당하면 Promise.all()은 즉시 거부합니다. 자세한 내용은 해당 Promise.all() 페이지를 참고해주시기 바랍니다.
수업들의 (시작하는 시간, 끝나는 시간) 을 확인하여, 필요한 강의실을 구하는 문제입니다.
풀이 방법
수업 시간을 시작하는 시간을 기준으로 정렬을 합니다.
첫 수업은 반드시 방이 필요하므로, 방에 수업을 추가합니다.
이 때, 방에 들어간 수업의 시작 시간은 뒤에 수업들에게 필요하지 않고, 수업의 끝나는 시간이 필요합니다. 그래서 수업시간의 끝나는 시간을 방에 대한 정보로 저장합니다.
반복문으로 수업을 확인하면서 수업시간의 시작하는 시간보다, 방의 끝나는 시간보다 빠를 때는 방을 추가합니다.
아니라면 방의 끝나는 시간을 해당 수업의 끝나는 시간으로 수정합니다.
이 때, 방은 min heap으로 되어있어서, 끝나는 시간은 가장 빠른 것이 나오게 됩니다.
import heapq
N = int(input())
classTime = [tuple(map(int,input().split())) for _ in range(N)]
classTime.sort()
Room = []
# 끝나는 시간을 Room에 추가합니다.
heapq.heappush(Room, classTime[0][1])
for i in range(1,N):
# 시작하는 시간이 끝나는 시간보다 빠를 경우
if classTime[i][0] < Room[0]:
# Room 추가
heapq.heappush(Room, classTime[i][1])
else:
heapq.heappop(Room)
heapq.heappush(Room,classTime[i][1])
print(len(Room))
3. 거리 합이 최소인 k구간으로 나누기 위해,거리로 정렬한 것에서 k-1번째의 거리들을 사용합니다.
import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
sensorPoint = sorted(list(map(int,input().split())))
if k>=n:
print(0)
sys.exit()
dist = []
for i in range(1,n):
dist.append(sensorPoint[i] - sensorPoint[i-1])
dist.sort(reverse=True)
print(sum(dist[k-1:]))
2. 사용 가능한 동전부터 원하는 숫자(k)까지 반복문을 통해, 해당 숫자를 맞추기 위해 동전을 사용하는 가장 적은 횟수를 확인합니다.
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
coins = [int(input()) for _ in range(n)]
coins.sort()
dp = [10001] * (k+1)
dp[0] = 0
# 사용 가능한 코인들만 확인
for coin in coins:
# coin 부터 구하려는 숫자까지 확인
for i in range(coin,k+1):
dp[i] = min(dp[i], dp[i-coin]+1)
if dp[k]== 10001: print(-1)
else: print(dp[k])
