자료구조와 알고리즘의 비교 설명
자료구조는 데이터를 정리하고 저장하기 위한 다양한 방법을 의미합니다. 반면, 알고리즘은 특정 문제를 해결하기 위해 수행되는 명령어의 유한 집합입니다. 이 두 가지가 결합되어 소프트웨어 프로그램이 만들어집니다.
스택(Stack) 자료구조 설명
스택은 데이터가 한쪽 끝에서만 삽입되고 삭제되는 순서 리스트입니다. 이 구조의 특징은 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 것입니다. 즉, 후입선출(LIFO) 방식으로 작동합니다.
큐(Queue) 자료구조 설명 및 선형큐와 원형큐 비교
큐는 한쪽 끝에서 데이터가 삽입되고 반대쪽 끝에서 삭제되는 선입선출(FIFO) 방식의 리스트입니다. 선형큐는 첫 번째 요소의 앞에 빈 공간이 생겨도 마지막 요소의 위치가 큐의 크기에 도달하면 더 이상 데이터를 삽입할 수 없는 단점이 있습니다. 반면, 원형 큐는 배열의 끝을 연결하여 이러한 문제를 해결합니다. 즉, 빈 공간이 있으면 이를 활용하여 데이터 삽입이 가능하게 됩니다.
연결리스트(Linked List) 자료구조 설명
연결리스트는 중간에 데이터를 삽입하거나 삭제하는 데 용이한 자료구조입니다. 각 노드는 데이터 필드와 링크 필드를 포함하고 있으며, 삽입 및 삭제 시에는 이전 노드의 링크 필드 값을 수정하여 작업을 수행합니다.
배열(Array)과 연결리스트(Linked List) 비교
배열은 고정된 용량을 가지므로 메모리를 비효율적으로 사용할 수 있습니다. 반면, 연결리스트는 동적으로 크기가 조정되므로 메모리를 효율적으로 활용할 수 있습니다. 배열은 n번째 요소에 O(1) 시간에 접근할 수 있지만, 연결리스트는 O(n) 시간이 걸립니다.
이진트리 설명
이진트리는 공백이거나 루트와 두 개의 서브트리로 구성된 노드의 유한 집합입니다. 이진트리의 종류로는 최대 높이를 가진 편향 트리, 중간에 빈 값을 가지지 않는 완전 이진트리, 마지막 레벨까지 꽉 찬 포화 이진트리가 있습니다.
이진탐색트리(Binary Search Tree, BST) 설명
이진탐색트리는 왼쪽 서브트리에 작은 값이, 오른쪽 서브트리에 큰 값이 위치하는 이진트리입니다. 이 구조의 특징은 모든 원소가 서로 다른 키 값을 가지며, 중위 순회를 통해 오름차순으로 정렬됩니다. 또한 탐색, 삽입, 삭제 연산의 시간 복잡도는 O(log n)입니다.
이진탐색트리의 최악(worst case) 시간복잡도와 해결 방안
이진탐색트리가 편향 이진트리일 경우 최악의 시간 복잡도가 O(n)으로 발생할 수 있습니다. 이를 해결하기 위해, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1을 넘지 않도록 유지하는 AVL 트리로 변환하면 최악의 시간 복잡도를 O(log n)으로 개선할 수 있습니다.
힙(heap) 트리 설명
힙 트리는 각 노드가 부모 노드와 자식 노드 간에 특정한 순서적 성질을 가지는 완전 이진트리입니다. 최대 힙은 각 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 구조이고, 최소 힙은 각 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 구조입니다
정렬 알고리즘
삽입 정렬 (Insertion Sort)
삽입 정렬은 배열을 하나씩 확인하며, 각 원소를 자신보다 작은 값이 있는 위치에 삽입하여 정렬하는 방법입니다.
작동 원리:
•
배열을 왼쪽에서 오른쪽으로 탐색하면서 현재 원소를 이전 원소들과 비교합니다.
•
적절한 위치를 찾아 현재 원소를 삽입합니다. 시간 복잡도: O(n²) (최악의 경우, 모든 원소를 비교하여 위치를 변경해야 하기 때문입니다)
버블 정렬 (Bubble Sort)
버블 정렬은 인접한 두 원소를 비교하여 자리를 바꾸는 방식입니다. 이 과정을 반복하여 가장 큰 값이 배열의 끝으로 "버블"처럼 이동합니다.
작동 원리:
•
배열의 처음부터 끝까지 인접한 두 원소를 비교하고 필요하면 자리를 바꿉니다.
•
각 반복에서 가장 큰 값이 마지막으로 이동합니다.
•
시간 복잡도: O(n²) (최악의 경우, n번의 반복에서 매번 두 값을 비교해야 하기 때문입니다)
선택 정렬 (Selection Sort)
선택 정렬은 배열에서 가장 작은 값을 찾아 맨 앞의 원소와 교환하는 방식입니다.
작동 원리:
•
배열을 처음부터 끝까지 확인하면서 가장 작은 값을 찾습니다.
•
찾은 가장 작은 값을 맨 앞의 원소와 교환합니다.
•
시간 복잡도: O(n²) (매번 n번씩 비교하고 교환해야 하므로)
합병 정렬 (Merge Sort)
합병 정렬은 배열을 절반씩 나누어 재귀적으로 정렬하고, 나누어진 배열을 병합하여 정렬하는 방식입니다.
작동 원리:
•
배열을 두 개의 부분으로 나누어 각각 재귀적으로 합병 정렬을 수행합니다.
•
나누어진 배열들을 하나씩 비교하면서 병합하여 정렬된 배열을 만듭니다.
•
시간 복잡도: O(n log n) (분할과 병합 과정에서 반복문을 사용하여 최종적으로 O(n log n)의 시간이 걸립니다)
퀵 정렬 (Quick Sort)
퀵 정렬은 배열에서 '피벗'을 선택하고, 이 피벗을 기준으로 배열을 두 개의 부분으로 나누어 정렬하는 방식입니다.
작동 원리:
•
배열에서 피벗을 선택합니다.
•
피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치합니다.
•
왼쪽과 오른쪽 부분에 대해 재귀적으로 퀵 정렬을 수행합니다.
•
시간 복잡도: 평균 O(n log n), 최악 O(n²) (최악의 경우, 배열이 이미 정렬되어 있거나 모두 같은 값일 때 발생합니다)
힙 정렬 (Heap Sort)
힙 정렬은 힙 자료구조를 이용하여 정렬하는 알고리즘으로, 최대 힙 또는 최소 힙을 사용합니다.
작동 원리:
•
배열을 힙 구조로 변환합니다.
•
가장 큰 값(또는 작은 값)을 힙의 루트에서 꺼내어 배열의 끝에 배치합니다.
•
시간 복잡도: O(n log n) (힙 변환과 힙 재구성이 O(log n) 시간이 걸립니다)
셀 정렬 (Shell Sort)
셀 정렬은 삽입 정렬의 개선된 버전으로, 원소들 간의 간격을 두고 정렬한 후 점차 간격을 좁혀가며 정렬하는 방식입니다.
작동 원리:
•
배열의 원소들을 일정 간격으로 나누어 삽입 정렬을 수행합니다.
•
간격을 점차 줄여가며 반복합니다.
•
시간 복잡도: O(n³/2) (간격의 선택에 따라 달라지며, 최악의 경우 O(n³/2)입니다)
기수 정렬 (Radix Sort)
기수 정렬은 자릿수를 기준으로 원소를 정렬하는 알고리즘입니다. 주로 정수 값이나 문자열을 정렬할 때 사용됩니다.
작동 원리:
•
각 자릿수를 기준으로 정렬을 수행합니다.
•
이를 반복하여 정렬을 완료합니다.
•
시간 복잡도: O(nk) (n은 배열의 크기, k는 자릿수입니다)
그래프 알고리즘
깊이 우선 탐색 (DFS)
DFS는 그래프의 한 방향으로 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 되돌아가며 탐색하는 방법입니다.
작동 원리:
•
시작 노드에서 한 방향으로 끝까지 탐색합니다.
•
더 이상 방문할 노드가 없으면, 이전 노드로 되돌아가면서 탐색을 계속합니다.
•
용도: 경로 탐색, 그래프의 연결성 검사 등
너비 우선 탐색 (BFS)
BFS는 인접한 노드를 먼저 탐색한 후, 그 다음 레벨로 탐색을 확장하는 방식입니다.
작동 원리:
•
시작 노드에서 인접한 노드를 모두 방문한 후, 그 다음 레벨로 넘어갑니다.
•
큐 자료구조를 사용하여 탐색을 진행합니다.
•
용도: 최단 경로 찾기, 레벨별 탐색 등
크루스칼 알고리즘 (Kruskal's Algorithm)
크루스칼 알고리즘은 최소 신장 트리를 구하는 알고리즘으로, 간선의 가중치가 낮은 것부터 선택하여 트리를 구성합니다.
작동 원리:
•
그래프의 모든 간선을 가중치 순으로 정렬합니다.
•
간선을 하나씩 선택하면서 사이클이 생기지 않도록 트리에 추가합니다.
•
용도: 최소 신장 트리 구하기
프림 알고리즘 (Prim's Algorithm)
프림 알고리즘은 시작 노드에서부터 최소 신장 트리를 확장하는 방식입니다.
작동 원리:
•
시작 노드를 선택하고, 그 노드와 연결된 간선들 중에서 최소 가중치를 가진 간선을 선택합니다.
•
새로운 노드를 추가하고, 그 노드와 연결된 간선들 중에서 최소 가중치를 가진 간선을 선택하여 트리를 확장합니다.
•
용도: 최소 신장 트리 구하기
다익스트라 알고리즘 (Dijkstra's Algorithm)
다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 구하는 알고리즘입니다.
작동 원리:
•
출발 노드에서 다른 노드로 가는 최단 경로를 구합니다.
•
각 노드까지의 최단 경로를 계속 업데이트하여, 최종적으로 최단 경로를 구합니다.
•
용도: 최단 경로 구하기
플로이드 알고리즘 (Floyd's Algorithm)
플로이드 알고리즘은 모든 쌍에 대해 최단 경로를 구하는 알고리즘입니다.
작동 원리:
•
모든 노드를 중간 노드로 고려하여, 각 노드 간의 최단 경로를 업데이트합니다.
•
이를 반복하여 모든 노드 간의 최단 경로를 구합니다.
•
용도: 모든 쌍에 대한 최단 경로 구하기