본문 바로가기

전체 글

 (118)
퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 매우 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 기법을 사용하여 리스트를 정렬한다. 퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 대부분의 경우 매우 빠르게 동작한다. 다만, 최악의 경우 시간 복잡도는 O(n^2)이 될 수 있다.동작 원리퀵 정렬은 다음과 같은 단계를 따른다:피벗 선택 (Pivot Selection): 리스트에서 하나의 요소를 선택한다. 이 요소를 피벗(pivot)이라고 한다.분할 (Partitioning): 피벗을 기준으로 리스트를 두 부분으로 나눈다. 피벗보다 작은 요소들은 피벗의 왼쪽에, 피벗보다 큰 요소들은 피벗의 오른쪽에 위치하게 한다.재귀적 정렬 (Recursive Sorting): 분할..
삽입 정렬 (Insertion Sort) 삽입 정렬(Insertion Sort)은 비교 기반 정렬 알고리즘의 하나로, 마치 카드를 한 장씩 정렬하는 것처럼 리스트를 정렬한다. 이 알고리즘은 리스트를 순회하면서 현재 요소를 그 앞의 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식으로 동작한다.동작 원리초기 상태: 두 번째 요소부터 시작하여 리스트를 순회한다.삽입 위치 찾기: 현재 요소를 그 앞의 정렬된 부분과 비교하여 적절한 위치를 찾는다.교환 및 삽입: 적절한 위치를 찾으면 현재 요소를 그 위치에 삽입하고, 나머지 요소들을 오른쪽으로 이동시킨다.반복: 리스트의 끝까지 이 과정을 반복한다.알고리즘 단계두 번째 요소를 선택합니다. 첫 번째 요소는 이미 정렬된 상태로 가정한다.현재 요소를 앞의 정렬된 부분과 비교하여 적절한 위치를 찾는다.현재 요..
선택 정렬 (Selection Sort) 선택 정렬(Selection Sort)은 비교 기반 정렬 알고리즘의 하나로, 리스트를 반복적으로 순회하면서 정렬되지 않은 부분에서 가장 작은(또는 큰) 요소를 선택하여 정렬된 부분의 끝에 위치시키는 방식으로 동작한다. 이 과정은 리스트가 정렬될 때까지 계속된다.동작 원리초기 상태: 리스트의 처음부터 끝까지 순회한다.가장 작은 요소 찾기: 현재 위치에서 시작하여 정렬되지 않은 부분에서 가장 작은 요소를 찾는다.교환: 찾은 가장 작은 요소를 현재 위치의 요소와 교환한다.반복: 리스트 전체가 정렬될 때까지 위 과정을 반복한다.알고리즘 단계리스트의 첫 번째 요소를 최소값(min_index)으로 가정한다.나머지 요소들을 순회하며 현재 최소값보다 작은 요소가 있는지 확인한다.작은 요소가 발견되면 그것을 새로운 최소..
버블 정렬 (Bubble Sort) 버블 정렬(Bubble Sort)은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 자리를 바꾸는 작업을 반복하는 방식으로 리스트를 정렬한다. 이 과정은 리스트가 정렬될 때까지 계속되며, 가장 큰 요소가 "거품"처럼 리스트의 끝으로 이동하는 모습을 보인다.동작 원리초기 상태: 리스트의 처음부터 끝까지 반복한다.인접한 두 요소 비교: 각 반복에서 인접한 두 요소를 비교한다.교환: 두 요소가 잘못된 순서(오름차순 정렬에서는 앞의 요소가 뒤의 요소보다 클 때)에 있으면 자리를 바꾼다.반복: 이 과정을 리스트가 완전히 정렬될 때까지 반복한다.알고리즘 단계첫 번째 요소와 두 번째 요소를 비교하여 잘못된 순서이면 교환한다.두 번째 요소와 세 번째 요소를 비교하여 잘못된 순서이면 교환한..
이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 한 종류로, 각 노드가 다음과 같은 속성을 만족한다:왼쪽 서브트리의 모든 노드 값은 현재 노드의 값보다 작다.오른쪽 서브트리의 모든 노드 값은 현재 노드의 값보다 크다.각 서브트리도 이진 탐색 트리이다.이러한 속성 덕분에 이진 탐색 트리는 효율적인 탐색, 삽입, 삭제 연산을 지원한다.주요 연산탐색 (Search):이진 탐색 트리에서 특정 값을 탐색하는 연산이다.현재 노드와 비교하여 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리로 이동한다.평균 시간 복잡도는 O(log n)이다.삽입 (Insert):새로운 값을 트리에 삽입하는 연산이다.탐색 연산과 유사하게, 삽입할 위치를 찾아 해당 위치에 노드를 추가한다.평균 시간 복잡도는 O(lo..
이진 트리 (Binary Tree) 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 이진 트리는 트리 자료 구조의 한 종류로, 그 구조적 특성과 다양한 응용으로 인해 컴퓨터 과학에서 매우 중요한 역할을 한다.기본 개념노드 (Node): 트리의 기본 구성 요소로, 각 노드는 데이터를 저장한다.루트 (Root): 트리의 최상위 노드이다. 트리는 하나의 루트 노드를 가진다.부모 (Parent) 노드: 다른 노드를 가리키는 노드를 의미한다.자식 (Child) 노드: 다른 노드로부터 가리켜지는 노드를 의미한다.왼쪽 자식 (Left Child)와 오른쪽 자식 (Right Child): 각 노드는 최대 두 개의 자식 노드를 가지며, 왼쪽 자식과 오른쪽 자식으로 구분된다.리프 (Leaf) 노드: 자식 노드..
연결 리스트 기반 큐 (Linked List-based Queue) 큐(Queue)는 FIFO(First In, First Out) 구조를 가지는 자료 구조로, 먼저 삽입된 요소가 먼저 제거됩니다. 큐는 배열(Array) 또는 연결 리스트(Linked List)로 구현할 수 있습니다. 연결 리스트 기반 큐는 큐의 요소를 노드(Node)로 관리하여 동적으로 메모리를 할당합니다. 이 방법은 큐의 크기가 가변적이어서 메모리 사용이 효율적입니다.연결 리스트 기반 큐의 구조노드 (Node): 큐의 각 요소를 나타내는 기본 단위로, 데이터와 다음 노드를 가리키는 포인터를 포함합니다.데이터 (Data): 노드가 저장하는 값.다음 (Next): 다음 노드를 가리키는 포인터.큐 (Queue): 연결 리스트의 헤드(Front)와 테일(Rear) 노드를 가리키는 포인터를 포함합니다.프론트 ..
연결 리스트 기반 스택 (Linked List-based Stack) 스택(Stack)은 LIFO(Last In, First Out) 구조를 가지는 자료 구조로, 마지막에 삽입된 요소가 가장 먼저 제거된다. 스택은 배열(Array) 또는 연결 리스트(Linked List)로 구현할 수 있다. 연결 리스트 기반 스택은 스택의 요소를 노드(Node)로 관리하여 동적으로 메모리를 할당한다. 이 방법은 스택의 크기가 가변적이어서 메모리 사용이 효율적이다.연결 리스트 기반 스택의 구조노드 (Node): 스택의 각 요소를 나타내는 기본 단위로, 데이터와 다음 노드를 가리키는 포인터를 포함한다.데이터 (Data): 노드가 저장하는 값.다음 (Next): 다음 노드를 가리키는 포인터.스택 (Stack): 연결 리스트의 헤드(Top) 노드를 가리키는 포인터를 포함한다.탑 (Top): 스택..
728x90

티스토리툴바