728x90 Computer Science14 [자료구조] 이진탐색트리 (Binary Search Tree) ■ 이진 탐색 (Binary Search) 우리가 보통 벡터나 연결리스트를 활용하여 원하는 요소가 있는지 찾기 위해 순회를 할 경우 O(n)의 시간 복잡도를 갖고 전체를 둘러봐야한다. 하지만 정렬이 되어있는 상태라면 이렇게 할 필요 없이 이진 탐색을 해주면 된다. 이진 탐색이란 중간 요소를 기점으로 탐색할 값이 해당 요소보다 클 경우 우측을, 작을 경우 좌측을 탐색해주는 것인데 이를 찾을 때까지 [or 탐색 대상이 하나로 줄어들 때까지] 무한 반복 해주는 것이다. 반씩 쪼개서 탐색하므로 O(logN)의 시간 복잡도를 갖고 있으며 이는 일반적으로 전체를 순회하는 O(n)보다 좋은 성능을 의미한다. ■ 이진 탐색 트리 (BST; Binary Search Tree) [이론] 이진탐색트리는 이진트리의 구조를 띄.. 2024. 3. 29. [Algorithm] A* 알고리즘 ■ 들어가기 전 BFS의 두 가지 문제 중 가장 먼저 발견한 노드들을 방문한다는 한계점을 보완하기 위해 (1) 가중치 그래프(Weighted Graph)와 (2) 우선순위큐 (Priority Queue)를 사용한 다익스트라(Dijikstra) 알고리즘이 탄생했다. https://yjhdevelopdiary.tistory.com/196 [Algorithm] 다익스트라(Dijikstra) 알고리즘 ■ 배경 그래프의 탐색 알고리즘 중 BFS가 가볍고 구현하기 쉽다는 것을 알 수 있었다. 하지만 BFS의 단점은 아래 두 가지의 단점이 있다. (1) 목적지를 모른다. 그러므로 접근 가능한 모든 정점을 yjhdevelopdiary.tistory.com 하지만 다익스트라도 또 다른 BFS의 한계점은 보완하지 못했는데.. 2024. 3. 29. [Algorithm] 다익스트라(Dijikstra) 알고리즘 ■ 배경 그래프의 탐색 알고리즘 중 BFS가 가볍고 구현하기 쉽다는 것을 알 수 있었다. 하지만 BFS의 단점은 아래 두 가지의 단점이 있다. (1) 목적지를 모른다. 그러므로 접근 가능한 모든 정점을 탐색한다. (2) 가장 먼저 발견한(Discovered) 정점들을 방문 예약한다. 다익스트라 알고리즘은 위에서 (2) 문제를 해결하기 위해 고안된 알고리즘이다. ■ 특징 먼저 가중치 그래프를 활용하고 일반적인 큐(Queue)를 사용하는 BFS와 달리 우선순위 큐(Priority Queue)를 사용한다. (+)===== 우선 순위 큐는 아래 포스팅에 서술 및 구현해봤었다. https://yjhdevelopdiary.tistory.com/193 [자료구조] 우선 순위 큐 (Priority Queue) ■ 이론.. 2024. 3. 25. [Algorithm] BFS, DFS ■ 탐색 알고리즘 BFS, DFS는 그래프를 탐색할 때 사용하는 대표적인 탐색 알고리즘이다. 그래프는 이전 포스팅에서 정리해봤다. https://yjhdevelopdiary.tistory.com/194 [자료구조] 그래프 (Graph) ■ 의의 현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현 트리와 굉장히 유사한데 트리보다 약간 넓은 개념으로 보면 됨. 트리가 약간 그래프의 일종이라고 보는게 좀 더 정확할듯. yjhdevelopdiary.tistory.com ■ DFS (깊이 우선 탐색; Depth First Search) 시작점 기준 뎁스 가장 끝 부분까지 깊이 파고들어서 정보를 추출해주는 알고리즘이다. 막다른 길을 만날 때 까지 뎁스를 늘려 계속 파고드는 원리이다. [구현 방법] (1).. 2024. 3. 25. [자료구조] 그래프 (Graph) ■ 의의 현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현 트리와 굉장히 유사한데 트리보다 약간 넓은 개념으로 보면 됨. 트리가 약간 그래프의 일종이라고 보는게 좀 더 정확할듯. ■ 구성 (1) 정점 (Vertex) : 데이터를 표현 (사물, 개념 등) (2) 간선 (Edge) : 정점들을 연결하는데 사용 [사용 예시] 1. 소셜 네트워크 관계도 2. 지하철 노선도 3. 최적 길 판단 4. 다수 간의 호감도 등 ■ 종류 (1) 가중치 그래프 (Weighted Graph) 정점과 정점 사이를 잇는 간선에 가중치(비용)가 주어진 그래프를 뜻한다. (2) 방향 그래프 (Directed Graph) 정점과 정점 사이를 잇는 간선에 방향이 주어진 그래프를 뜻한다. ■ 표현 방법 (1) 인접 리스트 :.. 2024. 3. 25. [자료구조] 우선 순위 큐 (Priority Queue) ■ 이론 우선 순위 큐는 힙 트리(Heap Tree)의 구조를 갖는다. 최적 조건에 해당하는 값을 한 번에 구하고 싶을 때 유용한 자료구조이다. 연결리스트나 벡터 같은 경우 최대값 최소값을 찾으려면 O(n)만큼 선회하며 모든 값을 비교해줘야 도출할 수 있다. 하지만 우선순위큐는 힙트리의 구조로인하여 완전이진트리의 형태를 띄고 있다. 데이터를 삭제 및 추가하는 과정에서 대소관계를 비교하며 노드를 이동시키는 연산이 트리의 높이(logN)만큼 발생하므로 O(logN) 정도의 시간복잡도로 수행된다. [힙트리 설명 및 힙 정렬 알고리즘은 아래 포스팅에서 이전에 C#으로 구현해봤었다.] https://yjhdevelopdiary.tistory.com/172 [Alogrithm] 히프, 기수, 계수 정렬, 알고리즘 .. 2024. 3. 25. [Alogrithm] 히프, 기수, 계수 정렬, 알고리즘 비교표 ■ 히프 정렬 (Heap Sort) 1. 히프(heap) 자료구조를 사용하는 정렬 알고리즘임. 2. 히프는 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조이며 완전 이진 트리이다. 3. 최대힙 혹은 최소 힙에서 삽입, 삭제 연산에 내포되어있는 정렬 알고리즘들이 히프 정렬이다. * 완전이진트리 : 루트로부터 자식노드가 두 개씩 있는데 마지막 레벨의 노드들이 왼쪽부터 오른쪽으로 채워져있는 트리 (※ 마지막 바로 위 레벨 노드들은 다 꽉채워져있고 마지막 레벨의 노드들도 빈틈 없이 왼쪽부터 오른쪽 순서대로 채워져있어야함) [히프 정렬 과정] 1. 정렬할 데이터들을 먼저 히프로 삽입해야 함 2. 그런 다음 루트 노드들 하나씩 삭제하여 꺼내면 히프에 있는 데이터들이 순서대로 나오게 되는데 이 순서대로 나열한 것이 .. 2024. 2. 7. [Algorithm] 셸, 병합, 퀵 정렬 ■ 셸 정렬 (Shell Sort) 삽입 정렬을 보완한 알고리즘. Donald L. Shell이란 사람이 제안한 방법이라 셸 정렬임. [삽입 정렬의 문제점] 1. 데이터들이 삽입될 때 이웃한 위치로만 이동하는 것 2. 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있음 [특징] 1. 삽입 정렬의 확장된 개념. 전체 데이터를 한꺼번에 정렬하는 것이 아니라 매개변수를 설정한 후 이 매개변수만큼 떨어져 있는 데이터들을 모아 부분 리스트를 만든 다음 그 매개변수를 줄여가면서 정렬하는 방식 2. 일정한 간격(gap)만큼 떨어져있는 데이터들끼리 부분 리스트를 구성하고 각 부분 리스트에 있는 데이터들을 삽입 정렬하는 작업을 반복 3. 큰 간격에서부터 시작하여 각 .. 2024. 2. 7. [Algorithm] 선택 정렬, 버블 정렬, 삽입 정렬 ■ 선택 정렬 (Selection Sort) 정렬되지 않은 여러 데이터들 중에 '가장 작은 값'을 찾아 가장 앞의 데이터와 교환하는 작업을 반복하여 정렬 정렬되지 않은 전체 데이터 중에서 해당 위치에 맞는 데이터를 선택하여 위치를 교환 [구현] [시간 복잡도] 1. 선택 정렬의 시간 복잡도는 O(n^2) 2. 입력이 거의 정렬되어 있든지, 역순으로 정렬되어 있든지, 랜덤하게 되어 있든지를 구분하지 않고 항상 일정한 시간 복잡도를 가짐 (입력에 민감하지 않은 알고리즘) 3. 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적음 ■ 버블 정렬 (Bubble Sort) 첫번째 값부터 시작해서 바로 앞뒤 데이터를 비교하여 큰 것은 뒤로 보내는 방법을 사용하는 정렬 수가 정렬되는 모습이 물속의 거품(Bubbl.. 2024. 2. 7. 이전 1 2 다음 728x90
