성장하고 개발하는 계란의 이야기

이번 글에서는 이분 탐색이라 불리는 검색 알고리즘을 소개합니다. 이분 탐색은 정렬된 데이터에서 값을 빠르게 찾을 때 사용되는 대표적인 알고리즘입니다. 이분 탐색 (Binary Search)개념정렬된 배열에서 탐색 - 정렬된 배열에서 원하는 값의 위치를 찾는 알고리즘입니다.중간 지점을 기준으로 해서 영역을 절반으로 나누고 목표 값과 크기를 비교하며 목표값이 존재하는 영역의 범위를 좁혀갑니다. O(Log n)의 시간복잡도를 갖는 탐색 알고리즘입니다. 일반적인 탐색은 n 개의 데이터 중에서 찾는 다고 할 경우 O(n)의 시간 복잡도를 가집니다.정렬이 되어야만 사용할 수 있는 알고리즘입니다. 정렬되어 있지 않은 경우에는 먼저 정렬 과정을 수행해야 합니다. [알고리즘 이론] 퀵 정렬, 병합 정렬, 힙 정렬, 계수..

이번 글에서는 그리디 알고리즘(Greedy Algorithm)을 다루어 보겠습니다. 그리디 알고리즘은 매 단계에서 “지금 당장 가장 좋아 보이는 선택”을 반복적으로 수행해 답을 찾는 전략입니다. 매 순간의 최적해를 찾는 것이기에 전체적으로 보았을 때 항상 최적해를 보장하는 것은 아니므로 문제의 특성을 이해하는 것이 중요합니다. 그리디 알고리즘(Greedy Algorithm)개념 최적의 선택 - 전체 문제를 해결하기 위해 각 단계에서 가장 좋아보이는 선택을 합니다. 이런 부분적으로 최적인 선택을 통해 전체 문제의 해를 구하는 알고리즘입니다. 빠른 계산 - 모든 경우를 탐색하지 않고 한 번 결정한 선택을 다시 되돌리지 않기 때문에 계산 과정이 간단하고 속도가 빠릅니다. 전제 조건 💡문제를 더 작은 문제로 ..

최근 [알고리즘 이론] 시리즈에서는 DFS와 BFS 같은 그래프 탐색 알고리즘을 살펴보았습니다. 이번 글에서는 완전 탐색의 일종인 백트래킹에 대해 알아봅니다. 백트래킹은 DFS처럼 깊이 우선으로 탐색하지만, 조건을 만족하지 못하는 분기를 빨리 가지 치기하여 불필요한 경로를 탐색하지 않는다는 점이 특징입니다. [알고리즘 이론] DFS(깊이 우선 탐색)BFS와 DFS는 그래프나 트리를 탐색하는 대표적인 알고리즘입니다. 두 알고리즘은 동작방식과 사용하는 자료구조가 다릅니다. 혹시나 그래프나 트리에 대해 알고 싶다면 아래 링크를 참조하세요.growingegg.tistory.com 백트레킹 개념점진적 해결 – 백트래킹 알고리즘은 후보 해를 하나씩 쌓아가며 진행합니다. 현재까지 만든 부분 해가 조건을 만족할 수..

BFS와 DFS는 그래프나 트리를 탐색하는 대표적인 알고리즘입니다. 두 알고리즘은 동작방식과 사용하는 자료구조가 다릅니다. 혹시나 그래프나 트리에 대해 알고 싶다면 아래 링크를 참조하세요. [알고리즘 이론] 해시 테이블, 그래프, 트리, 힙오늘은 자료구조의 나머지 부분인해시 테이블, 그래프, 트리, 힙에 대해서다뤄 보도록 하겠습니다. 그럼 들어가 볼까요? 해시 테이블(Hash Table)해시 테이블은 데이터를 키(key)와 값(value)의 쌍으로growingegg.tistory.com DFS(Depth-first Search, 너비 우선 탐색)개념DFS는 가능한 깊게 내려가며 그래프를 탐색한 뒤, 더 이상 갈 수 없으면 다른 분기점으로 백트랙킹(backtracking) 하여 다른 경로를 탐색하는 알..

BFS와 DFS는 그래프나 트리를 탐색하는 대표적인 알고리즘입니다. 두 알고리즘은 동작방식과 사용하는 자료구조가 다릅니다. 혹시나 그래프나 트리에 대해 알고 싶다면 아래 링크를 참조하세요. [알고리즘 이론] 해시 테이블, 그래프, 트리, 힙오늘은 자료구조의 나머지 부분인해시 테이블, 그래프, 트리, 힙에 대해서다뤄 보도록 하겠습니다. 그럼 들어가 볼까요? 해시 테이블(Hash Table)해시 테이블은 데이터를 키(key)와 값(value)의 쌍으로growingegg.tistory.com BFS(Breadth-first Search, 너비 우선 탐색) 개념최단 경로를 탐색하거나 계층 단위로 노드를 탐색해야 할 때 유리한 알고리즘입니다. 시작 지점부터 현재 계층의 노드를 전부 탐색하고 다음 계층으로 넘어갑..

이전에 시간 복잡도가 O(n^2)인 알고리즘에 대해 다뤄보았는 데요. [알고리즘] 정렬(버블, 선택, 삽입)버블정렬 *정의: 리스트 혹은 배열의 인접한 두 요소를 비교하여 정렬하는 방식. 첫번째 요소부터 마지막 요소까지 정렬을 진행하고 마지막 요소를 제외한 나머지 리스트로 모든 요소가 정렬될growingegg.tistory.com 이번에는 시간복잡도가 O(nlogn)보다 빠른 정렬 알고리즘에 대해 알아보도록 하겠습니다. 퀵 정렬 (Quick Sort)개념분할 정복 방식(Divide-Conquer)의 비교 기반 정렬 알고리즘입니다. 배열에서 정렬의 기준이 되는 피벗(pivot) 값을 선택한 뒤, 피벗 값을 기준으로 큰 요소와 작은 요소로 배열을 분할합니다. 이후 분할된 하위 배열에 대해 같은 과정을 반복..

오늘은 자료구조의 나머지 부분인해시 테이블, 그래프, 트리, 힙에 대해서다뤄 보도록 하겠습니다. 그럼 들어가 볼까요? 해시 테이블(Hash Table)해시 테이블은 데이터를 키(key)와 값(value)의 쌍으로 저장하는 자료 구조입니다. python을 주로 다루는 분들은 Dictionary, java나 C++은 MAP이라는 자료 구조로 익숙할 것입니다. 여기서 키(key)는 데이터에 접급하기 위한 고유한 식별자이며 값(value)은 키에 대응하는 실제 데이터입니다. 앞서 배운 배열을 기준으로 생각해보면 데이터의 위치를 나타내는 인덱스가 키 값이며 배열에 저장된 데이터가 실제 값인 것입니다. 다만 배열은 연솟된 메모리를 바탕으로 인덱스도 연속된 정수로 표현되지만 해시 테이블은 다양한 형태의 데이터 ..

배열 ( Array ) 개념 같은 자료형의 데이터를 연속된 메모리 공간에 순서대로 저장하는 자료 구조. 특징고정 크기: 배열은 선언 시에 크기가 고정되며, 이후에는 크기 변경이 불가합니다. 연속된 메모리 : 데이터들이 메모리 상에 연속적으로 존재하고 있습니다. 같은 자료형 : 배열의 모든 요소는 동일한 자료형 인덱스를 통한 접근 : 배열은 연속된 메모리에 존재하며 모든 요소는 동일한 크기를 가지고 있기 때문에 배열의 시작 주소만 알면 인덱스를 통해 나머지 데이터에 바로 접근할 수 있습니다. 기본 동작 검색🕛시간 복잡도 : O( 1 )💡동작 설명배열에는 데이터의 시작 주소가 저장되어 있습니다. 배열의 크기가 고정이기 때문에 배열의 시작 위치로부터 n번째 데이터에 접급할 경우 아래와 같은 방식으로 데이..