[재귀] 나 자신을 다시 호출하는걸 재귀라고 한다. 바로 실습으로 가보자. [실습 1] 유클리드 호제법 # 유클리드 호제 def gcd(a,b): c = a % b if c == 0 : return b return gcd(b,c) # return을 빠트려서는 안된다. a, b = map(int,input('최대 공약수를 구하고픈 두 수 ? : ').split()) print(f'{a}, {b}의 최대공약수는 {gcd(a,b)}') return gcd(b,c)에서 return을 빼먹을 경우, b의 값과 관련 없이 함수 gcd(a,b)는 None을 return하게 된다. 왜냐면 자기 자신을 불러오기 전 함수 gcd(a,b)는 무엇을 return할껀지가 안정해지기 때문. 백준 문제 풀이를 통해 재귀 알고리즘의..
제로베이스
[최댓값] 자료구조에서 가장 큰 값을 찾는다. 자료의 0번째 인덱스 값을 max라 두고, for문을 돌려 값을 비교해가며 실제 max를 찾습니다. class MaxAlgo: def __init__(self,datas): self.datas = datas self.max_value = 0 def get_max_value(self): self.max_value = self.datas[0] for i in self.datas: if self.max_value < i : self.max_value = i return self.max_value mylist = [11, 8, 76, 75, 10, 72, 68, 93, 35, 41, 64, 42, 30, 29, 65, 48, 56, 76, 29, 66] maxalg..
[Selection Sort] 주어진 리스트 중에 최솟값을 찾아, 그 값 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정리하는 알고리즘 매번 가장 작은 것을 선택한다 라는 의미에서 선택정렬 알고리즘이라고 한다. N-1 만큼 최솟값을 찾아 맨 앞으로 보내야 한다. 따라서 연산 횟수는 \( N + (N-1) + (N-2) +(N-3) + ... + 2 = (N-1)(N+2)/2 = O(N^2) \) 과정 ) 가장 작은 숫자인 1을 가장 앞에 있는 숫자인 4와 자리를 바꾸고, 그다음 가장 작은 숫자인 2는 정렬이 잘 되어 있고, 그다음 작은 숫자인 3을 3번째 위치에 있는 5와 바꾸고... def select_sort(datas): for i in range(len(datas)-1): min_index = ..
[삽입 정렬] 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다. 버블 정렬은 큰숫자를 뒤로 밀어내며 정렬하는 반면, 삽입 정렬은 정렬이 이미 되어있는 앞부분과 나 자신을 비교해서, 나 자신이 어디에 삽입되면 되는지를 찾는다. 데이터가 거의 정렬되어있다면 매우 효율적인 알고리즘이다. 정렬되어 있는 배열과 비교할 때도, 자기보다 작은 데이터를 만나면 그 위치에서 멈추면 되므로 모든 데이터를 다 볼 필요가 없다. 시간 복잡도는 \( O(N^2) \) 이며, 최선의 경우 \( O(N) \) 을 갖는다. 빨간 박스는 이미 정렬되어 있는 부분을 말한다. 1. 처음에는 자료에서 두 번째 요소를 가지고 이전 데이터와 비교를 시작하며 빨간색 박스를 찾는다. 2. 정렬되어있지 않은 값을 하나하나 정렬된 배열(빨간..
