약수의 개수가 짝수인지 홀수인지 바로 알아내는 제곱수 판단하는 방법

1. 문제 11815번: 짝수? 홀수? (acmicpc.net) 11815번: 짝수? 홀수? B를 A로 나누었을 때 나머지가 0 이라면 A는 B의 약수라고 할 수 있다. (A > 0, B > 0) 예를 들면 15 의 약수는 1, 3, 5, 15 이다. 주어진 수가 가지는 약수 개수가 홀수인지 짝수인지 판별해보자. www.acmicpc.net 2. 풀이 소인수분해 해서 (지수+1)의 곱의 합으로 짝수인지 홀수인지 판단해볼라했는데 수가 10의 18제곱까지 있어서 그런지 시간초과 from sys import stdin n = int(stdin.readline()) num_list = list(map(int,stdin.readline().split())) for i in num_list: p = 2 answer..

• format_list_bulleted 정수론
• · 2023. 3. 5.
• textsms

등차수열 구간의 최대공약수를 한번에 구하는 방법

1. 문제 23888번: 등차수열과 쿼리 (acmicpc.net) 23888번: 등차수열과 쿼리 등차수열은 연속하는 두 항의 차이가 일정한 수열을 뜻한다. 연속한 두 항 중 뒷항에서 앞항을 뺀 값을 공차라고 한다. 초항이 $a$이고 공차가 $d$인 등차수열이 주어진다. 수열의 $i$번째 원소를 www.acmicpc.net 2. 풀이 L번째 항부터 R번째 항까지의 합과 최대공약수를 구하는 문제 등차수열의 합은 초항이 $a_{1}$이고 항 수가 n개이며 공차가 d일때.. $$\frac{n(a_{1} + a_{n})}{2}$$ 등차수열의 일반항은 a + (n-1)d이다. 그러면 L번째 항부터 R번째 항까지의 합은.. 초항이 a + (L-1)d이고 끝 항은 a + (R-1)d이며.. 항 수는 R-L+1개이니까...

• format_list_bulleted 정수론
• · 2023. 2. 27.
• textsms

외심과 내심의 직선거리를 구하는 방법 - 오일러의 삼각형 정리

1. 문제 16480번: 외심과 내심은 사랑입니다 (acmicpc.net) 16480번: 외심과 내심은 사랑입니다 수진이는 외심과 내심 없이는 살 수 없다고 말할 정도로 외심과 내심을 사랑한다. 하지만, 갑자기 수진에게 어려운 일이 닥쳤다. 바로 평면에 있는 삼각형 ABC에서 외접원의 반지름의 길이 R이고, www.acmicpc.net 2. 오일러의 삼각형 정리(Euler's triangle theorem) 삼각형의 외접원, 내접원, 방접원의 반지름이 각각 R, r, r'이라고 할때, 삼각형에서 외심과 내심 사이의 직선거리는 $\sqrt{R^{2} - 2Rr}$ 외심과 방심사이 직선거리는 $\sqrt{R^{2} + 2Rr^{'}}$ 근데 증명이 조금 까다롭던데 이걸 증명을 해봐야하는거냐 말아야하는거냐 외..

• format_list_bulleted 기하학
• · 2023. 2. 21.
• textsms

원을 두 현으로 분할할때 길이를 구하는 방법 - power theorem(방멱 정리)

1. 문제 16478번: 원의 분할 (acmicpc.net) 16478번: 원의 분할 장난꾸러기 혁주는 어렸을 때부터 가위를 아주 잘 다루었다. 그래서 그는 색종이를 가위로 아무렇게나 자르는 것을 좋아한다. 혁주는 오늘 친구에게 원 모양의 색종이를 생일 선물로 받았다. 그 www.acmicpc.net 2. 방멱 정리(power theorem) 원 위에 두 현 AB, CD가 주어질때, 교차점이 P라고 한다면.. PA * PB = PC * PD라는 정리 (증명) BC에 대한 원주각 CAB와 CDB가 서로 같고, 맞꼭지각으로 CPA, BPD가 서로 같기때문에, 삼각형 APC와 DPB는 서로 닮음이다. 닮음의 성질에 의해 PA:PD = PC:PB이고, 이를 정리하면 PA*PB = PC*PD 비슷하게.. 중고등학..

• format_list_bulleted 기하학
• · 2023. 2. 21.
• textsms

2차원 배열에서 경로의 개수 구하기 - 최단 경로가 아닌 경우

1. 문제 1520번: 내리막 길 (acmicpc.net) 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 2. 풀이 이 문제에서 핵심은 "어떤 칸을 최초 방문할 때 해당 칸에서 목적지까지 도달할 수 있는 경우의 수에 대한 정보를 기록해 놓고, 다음 방문 시 기록된 값을 참조해서 반복된 연산을 피하는 것이다" dp[y][x]를 (x,y)에서 (n-1,m-1)까지 조건에 맞는, 도달하는 경우의 수라고 정의하자. m,n = map(int,stdin.readline().split()) maps = [list(map(in..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 2. 19.
• textsms

컴퓨터로 한붓그리기 하는 방법 - 오일러 경로를 찾는 알고리즘

1. 문제 16168번: 퍼레이드 (acmicpc.net) 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net 2. 오일러 경로(eulerian trail) "모든 변을 단 한번만 지나서 주어진 그래프를 완성할 수 있는가" 그래프의 모든 간선을 1번만 지나서 모든 정점을 방문하는 연속된 경로를 오일러 경로라고 부른다 혹은 한붓그리기라고도 불린다. 위와 같이 정점은 여러번 지나도 상관없다 위와 같은 그래프는 오일러 경로가 존재하는 그래프이다. 특히 시작점과 끝점이 같은 오일러 경로는 ..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 2. 19.
• textsms