1.언어 사용에 대한 고민
나는 그동안 python으로 알고리즘 공부를 해왔기 때문에, c++과 java만 가능한 수업이 다소 벅찼다. 그런데 대부분 c++로 알고리즘 공부를 한다고 하기도 해서, 이번주까지는 파이썬과 병행하고 다음주부터는 c++로 공부를 이어가보려고 한다.
1644 소수의 연속합
[문제정리]
-연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해보자.
-단, 같은 소수가 중복되어 사용되면 안된다.
[문제 푸는 방법]
아래의 두 가지 알고리즘을 적용해야한다.
1.에라토스테네스의 체 : 주어진 N까지의 소수를 미리 구한다.
2.투 포인터를 활용해, 연속된 소수의 합이 N이 되는지 확인하여 정답 구하기.
[1.에라토스테네스의체 코드 부분]
def sieve_of_eratosthenes(n):
is_prime=[True]*(n+1)
p=2
while(p*p<=n):
if is_prime[p]:
for i in range(p*p,n+1,p):
is_prime[i]=False
p+=1
return [p for p in range(2,n+1) if is_prime[p]]
n=int(input())
print(sieve_of_eratosthenes(n))
[2.투포인터 코드 부분]
result=0
start=0
end=0
while end<=len(prime_num):
temp=sum(prime_num[start:end])
if temp==n: #같으면 result 하나 카운트하고, end를 뒤로 한 칸 옮긴다.
result+=1
end+=1
elif temp<n: #합이 수 보다 작으면, end를 뒤로 한 칸 옮긴다.
end+=1
else: #합이 수보다 커지면, start를 뒤로 한 칸 옮긴다.
start+=1
[정답코드]
def sieve_of_eratosthenes(n):
is_prime=[True]*(n+1)
p=2
while(p*p<=n):
if is_prime[p]:
for i in range(p*p,n+1,p):
is_prime[i]=False
p+=1
return [p for p in range(2,n+1) if is_prime[p]]
n=int(input())
prime_num=sieve_of_eratosthenes(n)
result=start=end=0
while(end<=len(prime_num)):
temp=sum(prime_num[start:end])
if temp==n:
result+=1
end+=1
elif temp<n:
end+=1
else: #temp>n:
start+=1
print(result)
2960 에라토스테네스의 체
[문제]
에라토스네테스의체는, N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
1)2부터 N까지 모든 수를 적는다
2)지우지 않은 수 중 가장 작은 수를 선택하고, 이것을 P라 한다.
3)P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4)다 완료될 때까지 2번으로 돌아간다.
첫째 줄에 N K 형태로 주어졌을 때, N보다 작거나 같은 소수들 중 K번째 지우는 수를 구하는 프로그램을 작성하시오.
def sieve_of_eratosthenes(n):
delete_nums=[]
is_prime=[True]*(n+1)
p=2
while(p*p<=n):
if is_prime[p]:
delete_nums.append(p)
for i in range(p*p,n+1,p):
is_prime[i]=False
#지웠던 것을 또 지우는 과정이 발생한다. 따라서 중복되는 것은 추가하지 않게 하는 과정이 필요했다.
if i not in delete_nums:
delete_nums.append(i)
p+=1
#기존 코드는 전체를 우선 True로 만들어놓고, False 처리를 하여 자동으로 남겨지는 소수들이 카운트가 안됐다.
#그냥 남겨지는 애들도 추가하기 위해서 다음 코드를 넣었다.
for i in range(int(n**0.5)+1,len(is_prime)):
if is_prime[i]:
delete_nums.append(i)
return delete_nums
n,k=map(int,input().split())
delete_nums=sieve_of_eratosthenes(n)
print(delete_nums[k-1])2725 보이는 점의 개수
[문제]
1.(0,0)에서 보이는 (x,y)의 개수를 구하려고 한다.(x,y>=0, 정수)
2.(0,0)에서 (x,y)가 보인다는 것은 (0,0)과 (x,y)를 연결하는 직선이 다른 점을 통과하지 않아야한다.
3.N이 주어졌을 때, 0<=x,y<=N 즉 (N,N)좌표평면에서 보이는 (x,y)좌표의 개수를 출력하시오.
4.단, (0,0)은 계산하지 않는다.
5.첫째 줄에 테스트케이스 개수C(1이상 1000이하)가 주어진다. 각 테스트케이스는 N(1이상 1000이하)로 주어지고, 한 줄에 하나씩 주어진다.
[시간초과코드]
def no_see_cnt(n):
slope=[]
#(0,0)~(n,n) 모든 경우의 수에 대하여
for i in range(n+1):#x좌표
for j in range(0,i+1):#y좌표
print(f'{i},{j}')
if i==0 and j==0:
slope.append(0)
print('slope에 0추가')
break
else:
temp=j/i
print(f'temp={temp}')
if temp not in slope:
print(f'temp={temp}를 추가합니다.')
slope.append(temp)
else: #temp in slope
print('이미 기울기가 있네요!')
pass
return len(slope)*2-1
#마지막에 0,0 은 포함하지 않지만 우리는 포함되어있으므로 -1 해줘야함.
C=int(input())
for _ in range(C):
N=int(input())
print(no_see_cnt(N))시간을 무진장 초과하는 브루트포스 코드를 완성했다.
생각을 잘했기 때문에 스스로도 칭찬하지만, 기울기가 존재하면 범위 내에서 그 기울기인 애들을 미리 제거하는 방식을 취해야한다.
[정답코드]
DP와 최대공약수 개념 사용
def gcd(i, j):
if j == 0:
return i
return gcd(j, i % j)
dp = [0 for _ in range(1001)]
dp[1] = 3
for i in range(2, 1001):
cnt = 0
for j in range(1, i+1):
if i == j:
continue
if gcd(i, j) == 1:
cnt += 2
dp[i] = dp[i-1] + cnt
T = int(input())
for _ in range(T):
N = int(input())
print(dp[N])(0,0)에서 보이지 않으려면 직선의 기울기가 달라야 한다.
이를 다르게 생각하면, (a,b)에서 a,b를 나누어 뜨리는 약수가 존재하는 경우, 둘이 서로소가 아닌 경우 볼 수 없는 자리다.
=> a,b가 서로소인 경우 볼 수 있는 자리다! 그리고 cnt+=2 인 이유는, 대칭으로 두 개씩 증가하기 때문이다!
4/2나 6/3은 약분하면 둘 다 기울기가 2로 똑같다. 따라서 분자와 분모의 최대공약수가 1인 값들을 찾아내면 된다.
좌표끼리 분수를 만들고 약분되면 그 좌표는 보일 수가 없다.
이전에 이미 같은 기울기가 나왔다는 뜻이기 때문이다.
따라서 분모와 분자의 최대공약수가 1일때만 더해나가면된다.
출처: https://sangminlog.tistory.com/entry/boj-2725 [로그 남기기:티스토리]
'코딩테스트 준비' 카테고리의 다른 글
| 삼성SDS 알고리즘 특강 5일차 (0) | 2024.08.02 |
|---|---|
| 2024 하반기 삼성SDS 알고리즘 특강 2일차 (0) | 2024.07.30 |
