🖥 CS/자료구조

이진 탐색(Binary Search)

✔️ 이진 탐색이란? 이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교합니다. 만약 X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들로, X가 중간 값보다 크면 중간 값을 기준으로 우측의 데이터들로 다시 탐색을 시작하여 해당 값을 찾을 때까지 반복합니다. 📌 시간 복잡도 N개의 배열을 이진 탐색하게 되면 N, N/2, N/4, N/8 ... 으로 진행될 것입니다. 여기서 탐색 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면 K = log2N일 것입니다. 즉, 이진 탐색의 시간 복잡도는 O(logN)입니다. ✔️ 이진 탐색의 예시 1. 예를 들어 { 17, 28, 43, 67, 88, 9..

연결 리스트(Linked List)

✔️연결 리스트란? 추상적 자료형인 리스트를 구현한 자료구조로, 각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. ✔️연결리스트의 장, 단점 - 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. - 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다 - 데이터를 연속적으로 연결시키지 않고 따로 떨어트려서 연결했기 때문에 노드의 주소를 계속 타야해서 랜덤엑세스가 불가능하다. - Head의 주소를 잃어버리면 뒤쪽의 노..