확장 유클리드 호제법 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다. 확장 유클리드 호제법을 제대로 이해하려면 수학 증명 과정까지 공부해야 한다고 하지만 여기서는 확장 유클리드 호제법 관련 문제를 풀기 위한 알고리즘만 설명하려고 한다. 확장 유클리드 호제법의 핵심 이론 확장 유클리드 호제법에서 해를 구하고자 하는 방정식 해를 구하고자 하는 방정식 ax + by = c (a, b, c, x, y는 정수) 이때 위 방정식은 c% gcd(a, b) = 0인 경우에만 정수해를 가진다. 다시 말해 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다. 이는 ax + by = c가 정수해를 갖게 하는 c의 최소값이 gcd(a, b..

백준 11399 - ATM 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 답안 코드 : N = int(input()) A = list(map(int, input().split())) S = [0]*N # 합 배열 for i in range(1, N): # 삽입 정렬 insert_point = i insert_value = A[i] for j in range(i-1, -1, -1): if A[j] 그리디 # N의 최대값이 1,000 그리고 시간제한 1초니까 n^2이하 ..

유클리드 호제법 유클리드 호제법 euclidean-algorithm은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다. 유클리드 호제법의 핵심 이론 유클리드 호재법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문이다. MOD 연산 : 두 값을 나눈 나머지를 구하는 연산 MOD 연산을 이해하면 다음과 같은 3단계로 유클리드 호제법을 구현할 수 있다. MOD 연산으로 구현하는 유클리드 호제법 1 큰 수를 작은 수로 나누는 MOD 연산을 수행한다. 2 앞 단계에서의 작은 수와 MOD 연산 결..

백준 1427 - 소트인사이드 문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 답안 코드 : import sys print = sys.stdout.write A = list(input()) for i in range(len(A)): Max = i for j in range(i + 1, len(A)): if A[j] > A[Max]: # 내림차순이므로 최댓값을 찾음 Max = j if A[i] 파이썬에서는 input 데이터를 list로 변환하면 자동으로 자릿수 나누어 리스트화 해준다. # ( 파이썬 짱 ) # 이번에도 그저 s..

백준 2750 - 수 정렬하기 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 답안 코드 : N = int(input()) A = [0]*N for i in range(N): A[i] = int(input()) for i in range(N-1): for j in range(N-1-i): if A[j] > A[j+1]: temp = A[j] A[j] = A[j+1] A[j+1] = temp for i in range(N): print(A[i]) ..

소수 소수 구하기의 핵심 이론 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 에라토스테네스의 체 원리는 다음과 같다. ① 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다. ② 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다. ③ 리스트의 끝까지 ②를 반복한 후 리스트에서 남아 있는 모든 수를 출력한다. 에라토스테네스의 체를 사용할 때 시간 복잡도 일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlo..