Realuda의 블로그

탐색 알고리즘은 말 그대로 어떤 데이터 구조에서 원하는 값이 있는지 찾아내는 알고리즘이다. 선형 탐색 알고리즘가장 간단한 탐색 방법은 선형 탐색이 있다.선형 탐색은 데이터 구조를 처음부터 끝까지 하나씩 살펴보는 것을 말한다.배열이나 리스트같은 선형 데이터 구조에서 사용할 수 있다. 예를 들어 다음과 같은 배열이 있다고 하자.arr = [2, 12, 15, 11, 7, 19, 45] 이 배열에서 7이라는 값을 찾으려고 한다.선형 탐색 알고리즘을 사용하면 배열의 0번 인덱스부터 시작해서 배열의 요소를 하나씩 살펴본다.위 배열을 0번 인덱스부터 살펴보면 2, 12, 15, 11, 7. 다섯번째 요소에서 원하는 값 7을 찾을 수 있다. 이번에는 배열에서 9라는 값을 찾으려고 해보자.9라는 값은 배열에 없기 때문..

스택 스택은 LIFO(Last In First Out) 원칙을 따르는 선형 데이터 구조이다. 스택이라는 이름 그대로 어떤 데이터가 쌓인 구조를 생각하면 좋다.LIFO(후입선출) LIFO는 Last In First Out의 줄임말로, 데이터의 삽입과 삭제 작업의 순서에 대한 원칙이다. 이는 즉 데이터를 스택에서 제거할 때, 스택에 삽입한 순서의 반대 순서를 따른다는 뜻이다. 스택의 기본 동작 스택을 다룰 때에는 몇가지 기본 동작을 숙지해야한다.push: 스택에 데이터를 삽입하는 동작이다. 스택의 맨 위에 데이터를 삽입한다.pop: 스택에서 데이터를 제거하는 동작이다. 스택의 맨 위의 데이터를 제거한다.peek: 스택에서 데이터를 조회하는 동작이다. 스택의 맨 위의 데이터를 조회한다. 그 외에 isEmpty..

배열(Array)Array는 우리 말로 배열이라고 한다. 배열은 모든 요소를 순서대로 나열한 선형 데이터 구조이다. 배열은 모든 데이터를 메모리의 연속된 위치에 저장한다. 대체로 동일한 데이터 타입의 데이터만을 저장한다.  배열의 가장 큰 특징은, 배열의 첫 번째 요소의 메모리 위치를 안다면 나머지 요소의 위치를 상대적으로 알 수 있다는 것이다. 예를 들어, 어떤 배열의 시작 위치가 0x0010이고 4바이트의 정수형 데이터를 저장하고 있다면 이 배열의 3번째 요소는 0x0010 + 2 * 0x0004 = 0x0018에 있을 것이다.배열의 인덱스 배열에서 어떤 데이터가 있는 위치를 인덱스라고 한다. 인덱스는 0부터 시작한다. 즉, 배열의 첫번째 데이터의 인덱스는 0이다. 위의 예시에서 배열의 세번째 데이터..

DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)은 대표적인 그래프 탐색 알고리즘이다. 두 알고리즘은 이름 그대로 깊이와 너비를 기준으로 그래프의 모든 노드를 순회하며 원하는 값을 찾는다.  먼저 그래프가 무엇인지 알아보자. 그래프는 정점과 간선으로 이루어진 비선형적 데이터 구조이다. 그래프를 표현하는 방법은 두가지가 있다.인접 행렬 표현 인접 행렬은 그래프를 0과 1의 행렬로 표현하는 방식이다. 그래프에 n개의 정점이 있다면 n*n 행렬을 만든다. 그리고 정점 i에서 j로 가는 간선이 있는 경우 행렬의 (i, j) 요소를 1로 표시하고, 간선이 없는 경우 (i, j) 요소를 0으로 표시한다. 예를 들어 위의 그림에서 정점이 3개인 그래프를 3*3 크기의 행렬로 표현할 수 있다. 세 정점은 자기 자신을..

정렬은 주어진 배열이나 요소들을 요소에 대한 비교 연산자에 따라 재배열 하는 것을 말한다. 정렬 알고리즘은 문제의 복잡성을 줄이기 때문에 중요하다. 예를 들어,출력하려는 데이터가 수백개라면 어떤 식으로든 정리하는 편이 보기 좋다.데이터를 정렬하면 O(1)시간만에 k번째로 작은 항목과 k번째로 큰 항목을 알 수 있다.거대한 데이터셋에서 검색하는 것이 쉬워진다. 정렬된 데이터가 있다면 이진 탐색을 사용해 검색할 수 있다.데이터베이스를 정렬하면 쿼리 성능이 향상된다.데이터셋을 정렬하면 패턴, 추세 및 이상을 식별하는데 도움이 된다.정렬 알고리즘을 사용하면 다음과 같은 장점이 있다.데이터를 정리하여 정보를 더 쉽고 빠르게 검색하고 분석할 수 있다.많은 알고리즘이 정렬된 데이터셋에서 더 효율적으로 작동한다.정렬을..

Big O 표기법은 알고리즘의 시간복잡도나 공간복잡도를 설명하는데 사용되는 도구이다. Big-O는 알고리즘의 시간복잡도의 상한을 표현하는 방법으로, 알고리즘의 최악의 상황을 분석한다. 입력 크기에 따라 알고리즘에 걸리는 시간의 상한을 O(f(n))으로 표기하는데, 여기서 f(n)은 알고리즘이 크기 n의 문제를 해결하기 위해 수행하는 연산의 수를 나타내는 함수이다. Big-O의 정의 두 함수 f(n)과 g(n)이 주어졌을 때, f(n) =n_0 에 대해 f(n)이 c>0 이고 n_0>=0 인 상수가 존재할 때 f(n)은 O(g(n)) 이라고 한다. 간단히 말해서, c와 n_0이 상수인 모든 n>=n_0 에 대해 f(n)이 c*g(n) 보다 더 빨리 증가하지 않으면 f(n)은 O(g(n)) 이다. 수학적으로..