정렬 알고리즘(1) - 정의, 버블정렬, 선택정렬, 삽입정렬

정렬이란? 정렬이란 키(key)들을 항목값의 대소관계에 따라 데이터집합을 일정한 순서로 늘어놓는 작업입니다. 정렬은 데이터를 정렬하면 데이터를 더욱 쉽게 검색 할 수 있습니다. 따라서 정렬을 한다는 것은 데이터들을 일정한 형태로 데이터를 나열하는 것과 같습니다. 정렬의 형태로 오름차순 정렬과 내림차순 정렬이 있습니다. 오름차순 정렬은 값이 작은 데이터부터 앞에 배치합니다. 반대로 내림차순 정렬은 값이 큰 데이터부터 앞에 배치합니다. 정렬의 종류로 9가지가 있습니다. 버블정렬, 선택정렬, 삽입정렬, 셸정렬, 퀵정렬, 병합정렬, 힙정렬, 도수정렬입니다. 앞에서 뒤의 순으로 학습을 하는 것이 권장된다고 합니다. 중요한 정렬은 퀵정렬, 병합정렬, 힙 정렬, 삽입 정렬입니다. 버블정렬 bubble sort 하나의..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 3. 27.

재귀 알고리즘: 거울에 비춰진 거울 속의 거울 속의 거울 속의 ~

재귀란? 어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의하는 경우를 재귀(recursion)라고 합니다. 어떤 사건의 결과가 동일한 사건의 원인이 되는 경우를 재귀라고 합니다. 자연수의 정의를 예로 들어보겠습니다. 자연수를 1,2,3,4,...,의 규칙성을 가진 수라고 정의할 수 있습니다. 이를 재귀적 형태로 정의하면 다음과 같습니다. 1은 자연수다. 자연수의 다음 수는 자연수다.팩토리얼 알아보기 팩토리얼 문제 또한 재귀알고리즘을 통해 해결할 수 있습니다. 정수 n의 팩토리얼은 다음과 같이 재귀적 정의를 할 수 있습니다. n 이 자연수일 때, n = 0 이면, 0! = 1 n > 0 이면, n! = n * (n-1)!이를 함수로 구현하면 다음과 같습니다. def factorial(n..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 3. 27.

큐(queue): 점심시간에 은행에서 업무를 보는 사람들

개론 큐란? 큐는 스택과 같이 데이터를 임시로 저장하는 자료구조 입니다. 스택은 가장 나중에 들어간 데이터가 먼저 나오는 후입선출(Last in First Out, LIFO) 구조라면 큐는 가장 먼저 들어간 데이터가 먼저 나오는 선입선출(First in First Out, FIFO) 구조 입니다. 은행창구에서 번호표대로 업무 보는 사람들, 놀이기구를 타기 위해 줄을 사는 사람들 모두 큐입니다. 큐의 작업와 구조 큐에 데이터를 넣는 행위를 인큐(enqueue)라고 합니다. 데이터를 제거하는 행위를 디큐(dequeue)라고 합니다. 큐에서 데이터 입구는 rear, 데이터 출구는 front 라고 합니다. 큐의 구현방법 큐는 배열로 구현하는 방법과 링 버퍼로 구현하는 방법 두가지가 있습니다. 큐는 데이터의 추가..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 3. 27.

스택: 차곡차곡 쌓여가고 있는 나의 빨래들처럼

스택이란? 스택은 데이터를 임시로 저장하는 자료구조로 데이터를 차곡차곡 쌓을 수 있습니다. 스택에 데이터를 넣는 작업을 push, 빼는 작업을 pop이라고 합니다. 스택의 윗부분을 top, 아랫부분을 bottom이라고 합니다. 스택 구성요소 스택 배열 스택의 본체입니다. 데이터를 저장하는 공간입니다. 인덱스가 0 인 공간이 바닥(bottom)입니다. 빈 스택에 데이터를 넣으면 인덱스가 0인 공간부터 채워집니다. stk[0] = data 스택 크기: capacity 스택에 들어갈 수 있는 데이터의 최대 개수입니다. 스택배열의 크기와 일치합니다. capacity = len(stk) 스택 포인터: ptr 스택이 현재 가진 데이터의 수입니다. ptr이 0이면 스택은 비어있습니다. 스택이 가득찼다면 ptr은 ca..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 3. 26.