RUBY

퀵 정렬 퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다 def qSort(ns): if len(ns) < 2: return ns midIdx = len(ns) // 2 midVal = ns[midIdx] smallNums = [] sameNums = [] bigNums = [] for n in ns: if n < midVal: smallNums.append(n) elif n == midVal: sameNums.append(n) ..

병합 정렬 병합 정렬 병합 정렬은 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용해서 정렬 알고리즘이다. 즉, 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합친다. 다음과 같이 1부터 8까지 총 8개의 숫자가 들어있는 배열에 있다고 가정, 특징 알고리즘을 큰 그림에서 보면 분할(split) 단계와 방합(merge) 단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾아야 하는 분할 비용보다 모든 값들을 비교해야하는 병합 비용이 크다. 예제에서 보이는 것과 같이 8 -> 4 -> 2 -> 1 식으로 전반적인 반복의 수는 점점 절반으로 줄어들 기 때문에 O(logN) 시간이 필요하며, 각 패스에서 병합할 ..

하노이의 탑 하노이의 탑 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다. • 한 번에 한개의 원판만 옮길 수 있다. • 큰 원판이 작은 원판 위에 있어서는 안 된다. def moveDisc(discCnt, fromBar, toBar, viaBar): # 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥 if discCnt == 1: print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!') else: moveDisc(discCnt-1, fromBar, viaBar, toBar) # (discCnt-1)개들을 경유 기둥으로 이동 print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 ..

재귀 알고리즘 재귀 함수 호출한 함수 안에서 그 함수를 다시 호출(recursive call)함으로 반복하는 것을 의미한다. 쉽게 말하면 def를 통해 함수를 만든다. 그리고 만든 함수 안에서 다시 그 함수를 호출하는 것을 의미한다. 반복문 대신 재귀 함수를 이용한 예 def recusion(num): if num > 0: print('*' * num) return recusion(num - 1) else: return 1 recusion(10) ********** ********* ******** ******* ****** ***** **** *** ** * 재귀 함수를 이용한 팩토리얼 구하기 def factorial(num): if num > 0: return num * factorial(num - ..

평균 평균 여러 수나 양의 중간값을 갖는 수를 평균이라고 한다 0~99까지의 수 중 30개의 랜덤 숫자의 평균 import random nums = random.sample(range(0, 100), 30) print(f'nums: {nums}') total = 0 for n in nums: total += n average = total / len(nums) print(f'average: {round(average, 2)}') 50이상 90이하 수들의 평균 import random nums = random.sample(range(0, 100), 30) print(f'nums: {nums}') targetNums = [] total = 0 for n in nums: if n >= 50 and n = se..

근삿값 근삿값 특정 값(참값)에 가장 가까운 값을 근삿값이라고 한다. import random nums = random.sample(range(0, 50), 20) print(f'nums: {nums}') inputNum = int(input('input number: ')) print(f'inputNum: {inputNum}') nearNum = 0 minNum = 50 for n in nums: absNum = abs(n - inputNum) # print(f'absNum: {absNum}') if absNum < minNum: minNum = absNum nearNum = n print(f'nearNum: {nearNum}') nums: [20, 3, 47, 30, 27, 21, 4, 31, 46,..

최빈값 최빈값 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 한다. class MaxAlgorithm: def __init__(self, ns): self.nums = ns self.maxNum = 0 self.maxNumIdx = 0 def setMaxIdxAndNum(self): self.maxNum = self.nums[0] self.maxNumIdx = 0 for i, n in enumerate(self.nums): if self.maxNum < n: self.maxNum = n self.maxNumIdx = i def getMaxNum(self): return self.maxNum; def getMaxNumIdx(self): return self.maxNumIdx; nums = [1, 3,..

최솟값 최솟값 자료구조에서 가장 작은 값을 찾는다. class MinAlgorithm: def __init__(self, ns): self.nums = ns self.minNum = 0 def getMinNum(self): self.minNum = self.nums[0] for n in self.nums: if self.minNum > n: self.minNum = n return self.minNum ma = MinAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11]) minNum = ma.getMinNum() print(f'minNum: {minNum}') minNum: -11 리스트에서 아스키코드가 가장 작은 값을 찾는 알고리즘을 만들어보자 class MinAlgorithm..