Total

[2960] 에라토스테네스의 체

2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 풀이 """ N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. """ n,k = map(int, input().split()) list = [0] * (n+1) for i in range(2, n+1): list[i]=i cnt=1 # 1 지움 ch=True for i in range(2, n+1): if ch: for j in range(i, n+1, i): if list[j]!=0: if cnt==k: print(j) ch=False break cnt += 1 list[j]=0

[2457] 공주님의 정원

2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 분석 N개의 꽃들 중에서 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력 풀이 import sys input=sys.stdin.readline n = int(input()) f = [] for i in range(n): sm,sd,em,ed=map(int, input().split()) f.append([sm*100+sd, em*100+ed]) f.sort() start..

[1026] 보물

1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 분석 A 배열 가장 큰 값 * B 배열 가장 작은 값으로 정렬하여 더하기 B에 있는 수 재배열 불가하지만 최솟값 출력이므로 무방 풀이 """ 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0]×B[0] + ... + A[N-1]×B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안된다. S의 최솟값을 출력 5 1 1 1 6 0 2 7 8 3 1 """ import ..

[11758] CCW (선분 방향)

11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 분석 CCW(Counter Clock Wise) 알고리즘 CCW(Counter Clock Wise) 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘 공식 CCW = (𝑿₁𝒀₂ + 𝑿₂𝒀₃ + 𝑿₃𝒀₁) - (𝑿₂𝒀₁ + 𝑿₃𝒀₂ + 𝑿₁𝒀₃) 방향 CCW 결과 0 : karla.tistory.com 풀이 """ 2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다...

CCW(Counter Clock Wise) 알고리즘

CCW(Counter Clock Wise) 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘 공식 CCW = (𝑿₁𝒀₂ + 𝑿₂𝒀₃ + 𝑿₃𝒀₁) - (𝑿₂𝒀₁ + 𝑿₃𝒀₂ + 𝑿₁𝒀₃) 방향 CCW 결과 0 : 반시계방향 삼각형의 넓이 |CCW 결괏값| /2 : 세 점으로 이뤄진 삼각형 넓이

[14565] 역원(Inverse) 구하기 (확장 유클리드 호제법)

14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net 분석 덧셈역 n-a (11 + 15) mod 26 = 0 곱셈역 xgcd(11﹡X, 26) = 1이 되는 X를 찾는 것 ➔ 11 * 𝒔 + 26 * 𝒕 = 1일 때 𝑆 값(곱셈역) (11 * 19) mod 26 = 1 확장 유클리드 알고리즘 확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's..

[21568] Ax+By=C (확장 유클리드 호제법)

21568번: Ax+By=C A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ≤ 1,000,000,000 www.acmicpc.net 분석 확장 유클리드 알고리즘 확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's Identity) 의 명제를 기반으로 해를 구하는 알고리즘 베주 항 karla.tistory.com 풀이 """ A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ..

확장 유클리드 알고리즘

확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's Identity) 의 명제를 기반으로 해를 구하는 알고리즘 베주 항등식 (Bezout's Identity) ax + by = d 를 만족하는 (x, y) 정수해는 d 의 값이 gcd(a, b) 의 배수일 때 존재하며, 이 존재하는 경우 나오는 값들만 (x, y) 의 정수해가 될 수 있다. 즉, d % gcd(a, b) == 0 인 경우이다. 만약 4x + 3y = 2 이라는 방적식이 있다고 하자. 이 때 (x, y)의 정수해는 ... ,(-1, 2), (2, -2), (5, -6), ... 등이 된다. 4, 3 의 최대공약수는 1이며 우변의 2는 1의 배수이기 ..

[10934] 최소공배수 (유클리드 호제법)

1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 분석 최소공배수 = A * B / 최대공약수 풀이 """ 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) """ def gcd(a,b): if b==0: return a else: return gcd(b,a%b) T=int(input()) ..

[1850] 최대공약수 (유클리드 호제법)

1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘 큰 수를 작은 수로 나누는 MOD 연산을 수행한다. 앞 단계에서 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다. 단계 2를 반복하다가 나머지가 0이되는 순간의 작은 수를 최대 공약수로 선택한다. 풀이 """ 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가..