📌 유클리드 호제법 일반적인 최대공약수를 구하는 방법은 두 수의 공통 약수를 모두 구해 곱하는 방법입니다. 100과 40의 최대공약수를 다음과 같이 구할 수 있습니다. 100 = 2^2 * 5^2 40 = 2^3 * 5 ------------------------ 최대공약수 = 2^2 * 5 = 20 유클리드 호제법은 일반적인 방법과는 좀 다른 방법으로 두 수의 최대공약수를 구합니다. 유클리드 호제법은 다음과 같이 구할 수 있습니다. 먼저 큰 수를 작은 수로 나눈 나머지를 구합니다. 100 % 40 = 20 (%는 나머지를 구하는 연산자) 그 다음 나눴던 작은 수를 나머지로 다시 나누고 나머지를 구합니다. 나머지가 0이 될 때까지 이 과정을 반복합니다. 나머지가 0이 되었을 때, 마지막으로 나눈 수가 최..
Algorithm
📌 삽입정렬 (Insertion Sort) 배열에서 현재 자신의 위치보다 앞에 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 방법이다. 👉 과정 Loop 1 [5, 3, 8, 1, 2, 7] current_idx: 1 current_val: 3 arr[current_idx - 1]: 5 인덱스 1번에 5삽입 [5, 5, 8, 1, 2, 7] current_idx: 0 current_val: 3 arr[current_idx - 1]: 5 current_idx가 0이 됐기 때문에 while문에 걸리지 않고 인덱스 0에 current_val을 삽입 [3, 5, 8, 1, 2, 7] current_idx: 0 current_val: 3 arr[current_idx - 1]: 5 Loop 2 [3..
📌 선택정렬 (Selection Sort) 주어진 리스트에서 가장 작은 값을 찾고 그 값을 맨 앞에 있는 값과 교체한다. 그리고 맨 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체하는 방법이다. 버블 정렬과 마찬가지로 O(n^2)의 시간복잡도를 갖는다. 👉 과정 [3, 4, 2, 5, 1] 최소값인 1과 3 swap [1, 4, 2, 5, 3] 최소값 2와 4 swap [1, 2, 4, 5, 3] 최소값 3과 4 swap [1, 2, 3, 5, 4] 최소값 4와 5 swap [1, 2, 3, 4, 5] 남은 숫자가 5 하나 남았기 때문에 자동으로 5가 최소값이 된다. [1, 2, 3, 4, 5] 정렬 끝 👉 구현 def selection_sort(arr): for i in range(len(arr..
📌 버블정렬 (Bubble Sort) 버블 정렬은 뒤에서부터 앞으로 정렬하는 특징을 갖고 있다. 가장 큰 수가 맨 뒤로 가고 그 다음 큰 수가 그 앞에 위치하게 된다. 시간복잡도는 O(n^2)이다. 👉 과정 [3, 2, 4, 5, 1] 3과 2 swap 가장 앞에 수와 그 다음 수를 비교해서 앞에 있는 수가 더 크면 두 수를 swap한다. [2, 3, 4, 5, 1] 3과 4를 비교하는데 3이 더 작기 때문에 swap 없이 넘어간다. [2, 3, 4, 5, 1] 4와 5도 마찬가지로 4가 5보다 더 작기 때문에 swap 없이 넘어간다. [2, 3, 4, 5, 1] 5와 1 swap 5가 1보다 크기 때문에 5와 1을 swap [2, 3, 4, 1, 5] 가장 큰 수인 5는 자리가 정해졌기 때문에 이 다음..
N 진수 ➡️ 10 진수 변환 N진수에서 10진수로 변환하는 방법은 파이썬에서는 매우 간단하다. int() 함수를 사용하면 된다. int 함수는 실수를 정수로 변환해주는 역할도 하지만 밑(base)을 사용할 수도 있다. int(value, base)의 형태로 사용하면 된다. value는 값이고 base는 밑이다. value는 0, base는 10이 초기값이다. base는 2~36 사이의 값을 입력할 수 있다. print(int('1011', 2)) # 2^3 + 2^1 + 1 = 11 print(int('16', 8)) # 1 * 8^1 + 6 * 1 = 14 print(int('F', 16)) # 15 * 1 = 15 각각 2진수, 8진수 16진수를 10진수로 변환한 것이다. 이렇게 하면 쉽게 10진수..
자연수 N (N > 0)이 주어졌을 때 N의 약수 구하기 👉 단순한 방법 def find_divisor(n): divisors = [] for i in range(1, n + 1): if n % i == 0: divisors.append(i) return divisors num = 100 print(find_divisor(num)) # [1, 2, 4, 5, 10, 20, 25, 50, 100] 반복문을 1부터 n까지 돌려준다. 만약 n을 i로 나누었을 때 나누어 떨어지면 약수이므로 divisor_list 배열에 저장해준다. 시간복잡도: O(N) 👉 좀 더 효율적인 방법 def find_divisor(n): divisors = [] for i in range(1, int(n**0.5) + 1): if n..
