이것저것 기록

* 의 문제 10을 정리한 내용입니다. 1. 병합 정렬이란? 입력을 두 개로 분리하고 각각 해결한 다음, 이 결과를 모아서 원래의 문제를 해결하는 전략이다. 대개 재귀 호출을 이용하여 구현한다. 일반적으로 다음과 같은 과정을 거친다. 분할: 입력 데이터를 2개로 분할한다. 이때, 파이썬에서는 // 연산자를 사용한다. 정복: 부분 데이터를 정렬한다. 결합: 정렬된 부분 배열을 다시 하나의 배열에 합병한다. 아래 그림에서 [6, 5, 12, 10, 9, 1]이 입력 배열이라고 했을 때, 가장 먼저 [6, 5, 12] 와 [10, 9, 1]로 분리한다. [6, 5, 12]는 [6]과 [5, 12]로 분리하고, [10, 9, 1]은 [10]과 [9, 1]로 분리한다. 더 쪼갤 수 있는가? [5, 12]는 [5]..

* 의 문제 09를 정리한 내용입니다. 1. 삽입 정렬이란? 자신보다 앞의 원소가 큰지 작은지 확인하여 자신의 위치를 찾아 '삽입'하는 알고리즘이다. 정렬되어 있는 경우는 비교를 하지 않기 때문에 버블 정렬과 달리 불필요한 비교가 줄어들었다. 2. 일반적인 삽입 정렬 알고리즘 def ins_sort(a): n = len(a) for i in range(1, n): # 앞 원소와 비교해야하기 때문에 가장 앞 원소는 무시한다 key = a[i] # 기준 원소 j = i - 1 # 바로 하나 앞 원소 while j >=0 and a[j] > key: # 앞 원소가 나보다 클 경우만 위치 변경 a[j+1] = a[j] # a[j+1]는 기준 원소 j -= 1 # 한 칸씩 앞으로 전진하며 비교 a[j+1] = k..

* 의 문제 08를 정리한 내용입니다. 1. 선택 정렬이란? 정렬 알고리즘 중 가장 직관적인 알고리즘이라고 한다. 초딩 때 운동장에서 키 순서대로 줄을 설 때를 생각해보자. 160cm, 150cm, 170cm, 180cm 가 있다고 했을 때, 우선 여기서 가장 키가 작은 150cm를 가장 앞에 세운다. 그리고 남은 세 명의 키를 비교하여 가장 키가 작은 160cm를 150cm 뒤에 세운다. 그리고 남은 두 명의 키를 비교하여 가장 키가 작은 170cm를 160cm 뒤에 세운다. 남은 180은 자동적으로 가장 뒤에 서게 된다. 위에서 설명한 정렬 방식을 일반하면 다음과 같다. 0 인덱스 부터 하나씩 보면서 제일 작은 값을 찾고 0번 인덱스와 교체한다. 그 후 1인덱스 부터 하나씩 보면서 작은 값 찾고 1번..

* 의 문제 07를 정리한 내용입니다. 1. 순차 탐색이란? 임의의 리스트 A가 주어졌다고 가정해보자. 나는 리스트A에 임의의 원소 X가 있는지, 없는지 확인하고 싶다. 이때 리스트에 있는 첫 번째 자료부터 하나씩 비교하면서 같은 값을 찾는 -- '리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색하는' 알고리즘을 순차 탐색이라고 한다. 순차 탐색 알고리즘으로 원하는 값을 찾으려면 몇 번 비교해야할까? 이것은 케바케다. 만약 내가 찾고자하는 원소가 리스트의 맨 앞에 있다면 단 한번의 비교로도 찾을 수 있다. 하지만 맨 뒤에 있다면? 즉, 같은 원소여도 원소가 리스트의 어디에 위치했느냐에 따라 비교 횟수가 달라진다. 이처럼 경우에 따라 계산 횟수가 다를 때는 보수적인 관점에서 최악의 경우로 시간 복..

* 의 문제 05를 정리한 내용입니다. 1. 일반적인 알고리즘으로 최대 공약수 구하기 # 최대공약수 알고리즘 def gcd_algorithm (a, b): i = min(a,b) while True: if a%i == 0 and b%i == 0 : print("GCD = {}".format(i)) return i i = i-1 print("i = {} " .format(i)) 두 개의 숫자를 입력받는다. 입력받은 수 중 작은 수를 찾는다. (min (a,b)) 생각해보면 당연한 프로세스다. 최대 공약수라는 말 자체가 입력 받은 두 개의 수를 나누는 수 중 공통인 것들 중, 가장 큰 것인데 -- 어떤 수를 나누려면 그 수보다 커서는 안된다 (되긴 하는데 여기서는 안됨, 분수 X) if문에 걸려 값을 ret..