전체 글 (86) 썸네일형 리스트형 자료구조 문제 정리 (6) 탐색, 해싱 1. 이진 탐색 (Binary Search)정렬된 배열에서 값을 효율적으로 찾는 알고리즘배열의 중간 요소를 선택하고, 찾고자 하는 값과 비교하는 과정이 반복된다과정:중간 요소와 찾고자 하는 값을 비교중간 값이 찾는 값보다 크면 왼쪽 절반으로, 작으면 오른쪽 절반으로 검색 범위를 좁힌다이 과정을 범위가 하나의 요소로 좁혀질 때까지 반복하거나, 찾는 값이 없다고 판별될 때까지 반복한다시간 복잡도는 O(logn)을 보장하며, 정렬된 데이터에서 빠르게 값을 찾을 수 있다.이진 탐색은 배열이나 리스트와 같은 선형 자료구조에서 주로 사용된다. 2. 이진 탐색 트리 (Binary Search Tree, BST)이진 탐색 트리는 이진 트리의 특수한 형태로, 모든 노드가 특정 정렬 기준에 맞게 정렬되어 있다.특징:각 .. 자료구조 문제 정리 (5) 정렬 정렬 알고리즘 시간 복잡도정렬종류평균최악버블정렬O(n^2)O(n^2)선택정렬O(n^2)O(n^2)삽입정렬O(n^2)O(n^2)퀵정렬O(nlogn)O(n^2)2-way merge 정렬O(nlogn)O(nlogn)힙 정렬O(nlogn)O(nlogn)기수 정렬O(n)O(n)*삽입 정렬과 버블 정렬의 경우 이미 정렬된 입력 데이터로 O(n)의 시간복잡도를 얻을 수 있다 1. 버블 정렬(Bubble sort)버블 정렬은 가장 기본적인 알고리즘 중 하나로, 인접한 데이터와 비교하면서 가장 큰 데이터를 맨 뒤로 옮긴다.맨 뒤에서부터 저장을 완료해나가는 방식이다안정적인 정렬이다.void Bubble_Sort(int arr[], int len) { int i, j, tmp; for (i = 0; i arr[j + .. 자료구조 문제 정리 (4) 그래프 [그래프의 순회 : BFS, DFS] (1)다음 그래프를 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 방법으로 방문할 때각 정점을 방문하는 순서로 옳은 것은? *시작 정점은 A이다, 알파벳 순서대로 방문한다.너비 우선 탐색(BFS)시작정점 A와 인접한 노드 B,F를 모두 삽입해야 하므로 A B F가 큐에 삽입되고 이 순서대로 방문한다A B F C D E 순서대로 방문한다깊이 우선 탐색(DFS)시작 정점 A의 인접한 노드 중 하나만 선택하는데 알파벳 순서대로 선택하게 되면 A,B가 된다.A B C D E F 순서대로 방문한다 그래프의 깊이 우선 탐색은 스택을, 너비 우선 탐색은 큐를 이용한다. (2)다음 그래프의 정점 A에서부터 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 수행할 때, 방.. 이전 1 2 3 4 ··· 29 다음
