Daily BOJ 22/01/10-22/01/16
2022/01/16

⚠ 스포일러 주의 ⚠
이 글은 BOJ(백준 온라인 저지) 문제 해답을 포함하고 있습니다.



계절 학기 종강!

  • 통계 과목을 3주간 들었는데 정말 하기 싫었다.
  • 하지만 ML/DL할 때 사용한다고 하니 이 악물고 해야했다.
  • 다행으로 계산기, 책, 강의자료, 울프람알파, 엑셀 다 허용되는 오픈북 시험이라 조금은 마음 놓고 풀었다.
  • 들어야 하는 수학 강의 다 들었다~~~~



2022/01/11 화요일

#7806 GCD! [G4]

링크

  • 실버 선생님의 도움을 받은 문제
  • n10이고, k240이라 하면
    • $240=2^4\cdot3\cdot5$
    1. 10!중에 2의 개수와 4를 비교해서 작은 수 만큼이 n!kgcd2의 개수.
    2. 마저 똑같이 하면 됨
1
2
3
4
5
6
7
8
9
int f(int N, int x) {
int ans = 0;
while(N!=0){
ans += N/x;
N/=x;
}

return ans;
}

N!에서 소수 x의 개수가 있는가 찾는 코드

참고하기 좋은 문제: #1676 팩토리얼 0의 개수

#1890 점프 [S2]

링크

문제에 대한 예시 그림

  • 예시에 써진 것을 그대로 dp테이블로 만들면 된다.
  • 출력해야 할 것은 dp[N-1][N-1]



2022/01/12 수요일

#23832 서로소 그래프 [G1]

링크

  • phi(2) + ... + phi(N)

#16563 어려운 소인수분해 [G4]

링크

에라토스테네스 체를 좀 응용하면 최소 소인수도 들고 있을 수 있고 최대 소인수도 들고 있을 수 있고 그렇다.
by. 실버 선생님

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> prime;
int minPrime[5000009];
void sieve(int n){
for(int i=2; i<=n; i++){
if(!minPrime[i]) prime.push_back(i);
for(auto j: prime){
if(i*j>n) break;
minPrime[i*j]=j;
if(i%j==0) break;
}
}
}

참고 문서: Linear-sieve

  • 이제 n이 소수가 아닐 때마다 그걸 나누는 소인수가 minPrime[n]에 들어있는 것
  • 그래서 그걸로 n을 나누고 또 그 다음으로 가고 하면 된다.

#11688 최소공배수 찾기 [G4]

링크

  • #7806 GCD!이랑 접근이 비슷함
  • lcm(A, B)의 소인수가 가지는 개수를 L과 비교해서 C를 만들어가면 된다.



2022/01/13 목요일

#2014 소수의 곱 [G1]

링크

  • priority_queue(pq)를 이용하는 문제
    1
    priority_queue<int, vector<int>, greater<int>> pq;
    작은 순서대로 받도록 하는 것.
  • 다익?bfs? 돌듯이? while문을 돌면서 현재(now=pq.top())에 주어진 소수를 곱하면서(for 사용) 범위 안이면 push. 넘치면 break;
    • 근데 이대로 하면 $3\cdot2$이 있는데 $2\cdot3$를 또 계산하려고 해서 now%x==0이면 나가게 걸어두면 된다
    • x는 마지막으로 곱해준 수보다 작거나 같아야 해서 이렇게 걸어두면 됨



2022/01/14 금요일

#12107 약수 지우기 게임1 [G3]

링크

실버스러운 문제에 대한 대화
본격 문제 만든 사람 앞에서 이 문제가 그사람스럽다고 말하기.

  • 게임 이론 문제
  • 나는 싫다 이런거…

각 상태마다 반드시 “이긴다” 아니면 “진다”라는 답이 있겠지? (모든 경우를 해보면 그중에 이기는 수가 있다 없다를 판단할 수 있으니까)
이기는 상태라면 “이걸 지우면 이긴다”라는 수가 존재할 것
1이 항상 지워진다는 것에 착안하여 전략을 세워야 함
by. 실버 선생님

#2421 저금통 [G5]

링크

1
2
3
4
5
6
7
8
9
10
int ans = 1;
dp[1][1] = 1;
for(int k=1+2; k<=2+2*N; k++){
for(int i=1; i<k; i++){
int j = k-i;
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cal(i, j);
ans = max(ans, dp[i][j]);
}
}
cout << dp[N][N]-1;
  • dp[i][j]: (i, j)일 때 소수의 개수
  • (1, 1) → (1, 2), (2, 1) → (1, 3), (2, 2), (3, 1) → ... 가는 것을 for로 구현했다. 표를 2배 더 그려야 하긴 하는데 알게 뭐람 $1\le N \le 999$인데

#18310 안테나 [S3]

링크

1
2
3
sort(v.begin(), v.end());
if(N%2==1) cout << v[N/2];
else cout << v[N/2-1];
  • 중간값 찾기



2022/01/15 토요일

#2212 센서 [G5]

링크

  • 정렬을 해서 센서와 센서 사이의 거리를 d[0]~d[N-1]까지 있을 것
  • 거기서 K-1개를 빼면(N-K개 남기면) 그게 답
  • (3), (6, 7, 8, 10), (12, 14, 15), (18), (20)

#2015 수들의 합 4 [G5]

링크

1
2
3
4
5
6
7
8
map<int, ll> m;
ll ans = 0;
for(int i=1; i<=N; i++){
if(s[i]==K) ans++;
ans += m[s[i]-K];
m[s[i]]++;
}
cout << ans;
  • 누적합을 구하는 배열 s[i]를 생성
  • 원래는 d[j]-d[i-1]=K을 구하는건데 이제 그러면 d[i-1]=d[j]-K
  • 나머지는 코드보면 됨

#1016 제곱 ㄴㄴ 수 [G1]

링크

1
2
3
4
5
6
7
8
for(auto i: prime){
if(i*i>MAX) break;
ll st = MIN/(i*i);
if(MIN%(i*i)!=0) st++;
for(ll j=st; (i*i)*j<=MAX; j++){
isSquare[(i*i)*j-MIN] = true;
}
}
  • 에라토스테네스의 체 느낌
  • st: MIN보다 살짝 큰 소수의 제곱으로 나누어 떨어지는 수
  • 제한이 1 ≤ min ≤ 1,000,000,000,000이므로 그냥 배열에 넣으면 터지니깐 min ≤ max ≤ min + 1,000,000을 이용해서 isSquare에 수를 집어넣을 때 MIN만큼 빼자

#14567 선수과목 (Prerequisite) [G5]

링크

  • 위상 정렬을 정말로 정직하게 짜면 답이 나온다.
  • queue<pii> q해서 {now, cnt}저장



2022/01/16 일요일

#2870 수학숙제 [S4]

링크

1
2
3
4
5
6
7
8
9
10
11
12
import re
N = int(input())
ans = []

for _ in range(N):
tmp = ""
s = input()
tmp = re.findall("\d+", s)
ans += list(map(int, tmp))

for x in sorted(ans):
print(x)

C++로 도저히 짜기 싫어서 검색을 많이 했다…

  • import re를 이용하면 정규식을 쓸 수 있다
  • \d+를 쓰면 연속한 숫자를 찾을 수 있음 리스트([])로 반환
  • 이것을 int로 변환해서 매핑해서 list로 바꿔서 ans에 추가로 저장함
  • sorted(ans): iterable한 데이터를 새로운 정렬된 리스트로 만들어서 반환

#24268 2022는 무엇이 특별할까? [S2]

링크

1
2
3
4
5
6
7
8
int a[10] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};
do{
ll num = cal();
if(num>N){
cout << num;
return 0;
}
} while(next_permutation(a, a+D));
  • #10974 모든 순열에서 next_permutation을 썼으면서 기억을 못하고 결국엔 힌트 받아서 썼음.
  • 배열 a가 좀 순서가 특별한 이유는 0으로 시작하는 숫자 막으려고, 그리고 저렇게 두고 돌리면 숫자가 내림차순으로 돌아가는데…

#24270 미니 버킷 리스트 [G4]

링크

한별이
한별이가 귀엽다.

  • 단위 시간을 더한 합을 S라 하면
  • 정답은 $N! \cdot _{N+1}H_{K-S}$인데
  • 약분약분하면 (K-S+1) + ... + (K-S+N)



후기

BOJ 800 solve!
2022/01/16 15:22

  • 파이썬을 좀 더 잘 쓰고 싶다. 근데 이거는 ML/DL만지면 더 괜찮아질까 싶기도 한데 그거랑 이거랑 좀 다른 문법을 쓰는 것 같다고 느꼈는지라 브론즈 문제는 파이썬으로 푸는 연습을 해봐야 할 것 같다.
  • 배운걸 까먹었던 나 자신이 바보같다. 이렇게 정리를 하면 조금은 낫지 않을까?
  • 앞으로도 꾸준히 문제 풀고 정리하고 해서 알찬 1000문제 푸는 것을 하자. 항상 고생많고 너무 무리는 말자🥰
  • 항상 도와주는 실버선생님과 사랑을 가득주는 정님에게 엄청난 감사를 남긴다🤗💕