약수를 세는 것보다 배수를 세는 것이 더 쉽다(홀수인 약수의 합, 유일한 소인수의 개수를 구하는 방법)

SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어떤 정수 x의 약수 중 홀수인 약수의 합을 f(x)라고 할때, L,R이 주어지면 L이상 R이하의 모든 x에 대해 f(x)의 합을 구하는 문제 단순한 방법으로는 소인수분해를 해서 홀수인 소인수들의 곱으로 약수의 합을 구하면 된다. https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$ 라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_..

• format_list_bulleted 정수론
• · 2024. 4. 11.
• textsms

prefix sum만이 누적합이 아니다1 - value 누적합

1. 문제 28449번: 누가 이길까 (acmicpc.net) 28449번: 누가 이길까 HI-ARC는 종강을 맞아 HI팀과 ARC팀으로 나누어 친선대회를 열려고 한다. HI팀엔 $N$명 ARC팀엔 $M$명이 속해있다. 대회는 다른 팀끼리 모든 사람들끼리 한번씩 대결을 하는 것으로, 대회는 $N \times M$개 www.acmicpc.net 2. 풀이 n명의 리스트 A를 오름차순 정렬, m명의 리스트 B를 오름차순 정렬하고 A의 모든 원소 A[i]에 대하여, 리스트 B에서 lower bound와 upper bound를 찾아서 lower bound 밑으로는 A[i]보다 작은 수들이니까 A의 승리이고, upper bound 위로는 A[i]보다 큰 수니까 B의 승리 lower bound와 upper boun..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 4. 10.
• textsms

실수 구간에서 이분 탐색 방법 제대로 배우기

1. 문제 21627번: Ice Cream (acmicpc.net) 21627번: Ice Cream The first line contains three integers $n$, $v$, $u$ --- the number of ice cream cones, the melting rate and the rate of eating ice cream ($1\le n\le 3\cdot10^5$, $1\le v,u \le 10^9$). The second lines contains $n$ integers $a_i$ ($1\le a_i \le 10^9$) --- www.acmicpc.net 2. 풀이 n개의 아이스크림이 초당 v만큼 동시에 녹으며, 나는 초당 u만큼 아이스크림을 1개씩 먹을 수 있다. 모든 아이스크..

• format_list_bulleted 이분 탐색
• · 2024. 4. 7.
• textsms

구간에 원소를 더하는 쿼리가 많이 주어질 때 필요한 누적합 테크닉(imos법)

19951번: 태상이의 훈련소 생활 (acmicpc.net) 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 배열이 주어질때, 구간 [a,b]에 c를 더하는 쿼리가 여러개 주어지고, 모든 쿼리를 해결하고 나서 최종 배열을 구하는 문제 1 2 3 4 5 -1 -2 -3 -4 -5 라는 배열에서 [1,5]에 -3을 더하면... -2 -1 0 1 2 -1 -2 -3 -4 -5 여기서 [6,10]에 5를 더하면 -2 -1 0 1 2 4 3 2 1 0 여기서 [2,7]에 2를 더하면 -2 1 2 3 4 6..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 3. 31.
• textsms

job assignment problem으로 알아보는 비트마스킹을 이용한 다이나믹 프로그래밍

1. 문제 1311번: 할 일 정하기 1 (acmicpc.net) 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net N명의 사람이 있고, N개의 일이 있는데 각각의 일은 하는데 비용이 든다. 각 사람 1명당 1개의 일만 가능하고 각 일은 1명만이 맡을 수 있다. 이럴 때 최소비용은 얼마인가? 2. 풀이 이런 형태의 문제는 N명의 사람이 1,2,3,4,..,N의 순열대로 배정을 해본후, 각각의 경우에 대해 비용을 전부 조사해서 최솟값을 찾는 방식을 배웠다. 3명이면 (1,2,3), (1,3,2), ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 3. 27.
• textsms

틱택토 게임(tic tac toe)에서 가능한 모든 경우의 수를 찾는 방법

1. 틱택토 게임 3*3 게임판에서 O와 X를 서로 번갈아 둔다. 가로나 세로, 대각선으로 1줄(3개)이 서로 같게 만들면 승리 3*3 게임판에서 각각의 cell은 O, X, '.' 3가지중 한가지가 들어갈 수 있으므로.. 모든 가능한 게임판의 경우는 $3^{9} = 19683$가지로 몇가지가 없다 이 경우 중간에 게임이 끝나서 더 이상 둘 수 없는 경우가 있기 때문에 그런 경우를 고려해서 제외하면 된다. BFS를 이용해서 모든 가능한 경우를 조사할 수 있다. 1) deque에 (['.']*9, (첫 시작이 두는 수))를 먼저 넣고 BFS를 수행 특히 배열이 9칸이기 때문에 배열을 deepcopy해도 시간이 그렇게 오래걸리지 않는다. 2-1) 큐에서 하나씩 뽑은 다음, 게임판 배열을 순회해서 둘 수 있는..

• format_list_bulleted 게임이론
• · 2024. 3. 13.
• textsms