Alex-Moon Alex-Moon

정의 퀵 정렬(suick sort)은 가장 빠른 정렬 알고리즘으로 알려져 있으며 널리 사용된다. 배열 안의 한 원소(요소)를 선택하는 데, 이 원소를 pivot이라고 한다. pivot을 기준으로 pivot보다 작은 원소들은 왼쪽 그룹으로 큰 원소들은 오른쪽 그룹으로 옮긴다. 다시 각 그룹에서 pivot을 선택하여 나누기를 반복하고 모든 그룹이 1명씩 남으면 정렬이 완료된다. 1. 배열을 두 그룹으로 나누기 5 7 1 4 6 2 3 9 8 위의 배열에서 6을 pivot으로 선택하여 그룹을 나눈다. pivot을 x, 왼쪽 끝 원소의 인덱스를 pl, 오른쪽을 pr이라고 하겠다. 그룹을 나누려면 pivot 이하인 원소를 배열 왼쪽(맨 앞쪽)으로, 피벗 이상인 원소를 배열 오른쪽(맨 뒤쪽)으로 이동시켜야 한다. ..

정의 셸 정렬(shell sort)은 단순 삽입 정렬의 장점을 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘이다. 단순 삽입의 특징 - 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠르다. - 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다. 셀 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄인다. 위의 배열은 먼저 서로 4칸씩 떨어진 원소를 꺼내어 4개의 그룹으로 나누고 그룹별로 정렬한다. 이런 방법을 '4 - 정렬'이라고 한다. 아직 정렬을 마치지 않았지만 정렬의 상태와 가까워졌다. 이어서 2칸 떨어진 원소를 모두 꺼내 '2 - 정렬'을 진행한다. 이후..

단순 선택 정렬의 정의 단순 선택 정렬(straight selection sort)은 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘이다. 다음은 단순 선택 정렬의 과정이다. 아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택하고, 아직 정렬하지 않은 부분의 맨 앞 원소와 교환하는 작업을 반복한다. 이 과정을 n - 1번 반복하면 정렬하지 않은 부분이 없어지면서 전체 정렬을 완료한다. 알고리즘의 개요는 다음과 같다. for i in range(n - 1): min # a[i], ... a[n-1]에서 키 값이 가장 작은 원소의 인덱스 a[i]와 a[min]의 값을 교환 더보기 더보기 def selection_sort(a): n = len(a) for i in ran..

정렬 알고리즘의 정의 정렬(sorting)이란 텍스트나 숫자 등의 key를 항목 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 데이터를 정렬하면 쉽게 검색할 수 있다. 값이 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순(ascending order)정렬이라 하고, 반대를 내림차순(descending order) 정렬이라 한다. 정렬 알고리즘은 데이터를 교환-선택-삽입하면서 정렬을 완료한다. 대부분의 정렬 알고리즘은 이 세가지를 응용한다. 안정성 여러 정렬 알고리즘 가운데 안정적인(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다. 위의 그림처럼 안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 말한다. 안정적이지 않은 알고리즘..

어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀(recursion)라고 한다. 재귀를 사용하는 대표적인 예로 팩토리얼(factorial) 문제가 있다. 팩토리얼은 양의 정수를 순서대로 곱한다는 의미다. 양의 정수 n의 팩토리얼(n!)은 다음과 같이 재귀적 정의를 할 수 있다. (재귀 과정으로 팩토리얼값을 구하는 문제는 재귀의 원리를 이해하기 위한 예제일 뿐 알고리즘 문제를 풀 때 현실적으로 적절하지 않다.) 더보기 def factorial(n :int): if n > 0: return n * factorial(n - 1) else: return 1 if __name__ == '__main__': n = int(input('출력할 팩토리얼 값을 입력하세요 : ')) p..

Queue 큐는 스택과 같이 데이터를 임시 저장하는 자료구조이다(배열을 사용하여 구현 가능). 가장 먼저 넢은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다. 컴퓨터에서 데이터를 주고받을 때 각 주변장치들 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위한 임시 기억 장치로 큐가 사용되는데, 이것을 buffer라고 한다. 큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue). 데이터를 꺼내는 쪽을 front, 넣는 쪽을 rear라고 한다. 위의 배열은 원소 24를 인큐하고 19를 디큐하는 작업이다. 인큐는 맨 뒤의 인덱스에 추가하면 그만이기 때문에 복잡도는 O(1)으로 적은 cost로 구현 가능하다. 하지만 디큐는 맨 앞의 원소를 꺼낸 후 모든 원..

검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다. 배열 검색의 종류로는 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다. 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다. 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다. 해시법 hashing 검색과 더불어 데이터의 추가와 삭제도 효율적이다. 해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 배열의 키들은 해시함수를 거쳐서 해시값(Hash Table)을 만들어 낸다. Hash Tabl..

검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다. 배열 검색의 종류로는 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다. 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다. 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다. 이진 검색 binary search 이진 검색은 원소가 오름차순이나 내림차순으로 정렬(sort)된 배열에 좀 더 효율적으로 검색할 수 있는 알고리즘이다. (선형 검색보다 빠르게 검색 가능) 위의 그림처럼 오름차순으로 정렬된 배열에서 76을 찾는 과정..