본문 바로가기
반응형

DEVELOPMENT/Algorithm

 (10)
DEVELOPMENT/Algorithm Big -O 빅오(Big O) 표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 나타내는 방법이다.즉, 입력 데이터의 크기가 커질 때 알고리즘이 얼마나 빨리 동작하는지, 또는 얼마나 많은 메모리를 사용하는지 나타낸다.Big O의 의미알고리즘의 성능을 입력 크기 n에 대한 함수로 표현한다.상수 계수와 낮은 차수 항은 무시하고 가장 큰 성장률만 표기한다.예를 들어, 연산 횟수가 3n^2 + 2n + 5 라면 Big O는 **O(n^2)**다.대표적인 시간 복잡도O(1)입력 크기에 상관없이 실행 시간이 일정한 경우예: 배열에서 특정 인덱스 접근O(n)입력 크기에 비례하여 실행 시간이 증가하는 경우예: 배열 전체를 순회하며 합을 구하기O(n^2)중첩 반복문이 있는 경우예: 버블 정렬, 선택 정렬O(log n)데이터가 반씩 줄..
DEVELOPMENT/Algorithm 해쉬(Hash) 해쉬는 데이터를 빠르게 저장하고 검색하기 위한 자료구조다.데이터의 키를 입력받아 해쉬 함수를 통해 배열의 인덱스로 변환하고, 그 인덱스 위치에 데이터를 저장하는 방식으로 동작한다.이 구조를 해쉬 테이블이라고 부른다.해쉬의 기본 개념일반적인 배열이나 리스트는 데이터를 순차적으로 탐색해야 하므로 검색 속도가 느리지만,해쉬는 해쉬 함수를 통해 직접 인덱스를 계산하므로 평균적으로 O(1) 시간 안에 데이터 접근이 가능하다.해쉬 테이블은 다음과 같은 구성 요소로 이루어진다.키(Key): 데이터를 구분하기 위한 고유 값값(Value): 실제 저장되는 데이터해쉬 함수(Hash Function): 키를 일정한 범위의 인덱스로 변환하는 함수버킷(Bucket): 변환된 인덱스에 해당하는 저장 공간해쉬 충돌서로 다른 키가 ..
DEVELOPMENT/Algorithm AVL 트리(AVL Tree) AVL 트리는 이진 탐색 트리의 한 종류로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1을 넘지 않도록 균형을 유지하는 트리 구조다. 1962년에 G.M. Adelson-Velsky와 E.M. Landis가 처음 제안했으며, 두 사람의 이름을 따서 AVL 트리라고 부른다.일반적인 이진 탐색 트리는 삽입 순서에 따라 한쪽으로 치우친 형태가 되어 탐색 효율이 떨어질 수 있다. 하지만 AVL 트리는 삽입과 삭제 시 자동으로 균형을 맞춰 주기 때문에 탐색, 삽입, 삭제 연산 모두 O(log n)의 시간 복잡도를 유지한다.균형 인수 (Balance Factor)각 노드는 자신의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이의 차이를 균형 인수라고 하며,균형 인수 = 왼쪽 서브트리 높이 - 오..
DEVELOPMENT/Algorithm 이진탐색트리(Binary Search Tree) 이진 탐색 트리 Binary Search Tree 는 탐색 효율을 높이기 위해 데이터를 정렬된 형태로 저장하는 트리 구조다.트리 Tree 는 계층적인 구조를 가진 자료구조로, 부모 노드 Parent 와 자식 노드 Child 로 구성되어 있다.이진 탐색 트리는 그중에서도 각 노드가 최대 두 개의 자식 노드를 가지며, 특정한 규칙에 따라 정렬되어 있는 트리다.이진 탐색 트리의 특징이진 탐색 트리에서는 각 노드에 대해 다음의 규칙이 적용된다.왼쪽 서브트리 Left Subtree 에 있는 모든 노드의 값은 부모 노드보다 작다.오른쪽 서브트리 Right Subtree 에 있는 모든 노드의 값은 부모 노드보다 크다.각 서브트리 역시 이진 탐색 트리의 성질을 만족한다.이 규칙 덕분에 탐색, 삽입, 삭제 연산이 평균적..
DEVELOPMENT/Algorithm 그래프(Graph) 그래프 Graph 는 정점 Vertex 과 간선 Edge 의 집합으로 이루어진 자료구조다.즉, 여러 개의 점이 선으로 연결된 형태를 말하며, 사물 간의 관계를 표현할 때 매우 유용한 구조다.그래프의 기본 개념그래프는 정점 Vertex 과 간선 Edge 로 구성된다.정점 Vertex 는 데이터나 객체를 의미한다.간선 Edge 는 두 정점을 연결하는 관계를 의미한다.예를 들어, 사람을 정점으로 두고 친구 관계를 간선으로 표현하면 소셜 네트워크를 그래프로 나타낼 수 있다.그래프의 종류그래프는 연결 방식과 간선의 방향 여부에 따라 여러 형태로 나뉜다.무방향 그래프 Undirected Graph간선에 방향이 없다. A와 B가 연결되어 있으면 B와 A도 연결되어 있다.방향 그래프 Directed Graph간선에 방..
DEVELOPMENT/Algorithm 정렬(Sorting)의 비교 정렬 Sorting 은 데이터를 일정한 순서대로 재배열하는 과정을 말한다.예를 들어 숫자를 오름차순으로 정렬하거나, 이름을 사전순으로 나열하는 것이 정렬의 예다.정렬 알고리즘은 비교 기반 정렬과 비비교 기반 정렬로 나눌 수 있다.여기서는 비교 기반 정렬 중 대표적인 네 가지 알고리즘인 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬을 중심으로 비교해보겠다.버블 정렬 Bubble Sort인접한 두 원소를 비교하여 순서가 잘못된 경우 서로 교환하는 방식이다.한 번의 패스가 끝날 때마다 가장 큰 값이 맨 뒤로 이동한다.단순하지만 비효율적이다.시간 복잡도최선: O n평균: O n 제곱최악: O n 제곱예시 코드 #include using namespace std;void bubbleSort(int arr[], i..
DEVELOPMENT/Algorithm 큐(Queue) 큐 Queue 는 먼저 들어온 데이터가 먼저 나가는 구조를 가진 자료구조다.즉, 선입선출 FIFO First In First Out 방식으로 작동한다.이는 마치 줄을 서서 기다리는 사람들의 행렬과 비슷하다.먼저 줄을 선 사람이 먼저 서비스를 받고 나가는 것과 같은 원리다.큐의 주요 연산인큐 Enqueue큐의 뒤 Rear 에 데이터를 추가한다.디큐 Dequeue큐의 앞 Front 에서 데이터를 꺼내고 제거한다.프론트 Front큐의 맨 앞에 있는 데이터를 확인하되, 제거하지 않는다.isEmpty큐가 비어 있는지를 확인한다.큐의 특징삽입은 뒤쪽에서, 삭제는 앞쪽에서 일어난다.데이터의 순서가 유지된다.순차적인 작업 처리나 버퍼 Buffer 구조에 자주 사용된다.대표적인 예로 프린터 대기열, 프로세스 스케줄링, ..
DEVELOPMENT/Algorithm 스택(Stack) 스택 Stack 은 데이터를 한쪽 방향으로만 넣고 빼는 자료구조다.가장 나중에 들어온 데이터가 가장 먼저 나가는 후입선출 LIFO, Last In First Out 구조를 가진다.즉, 접시를 쌓아두는 것처럼 위에 쌓은 접시부터 먼저 꺼내는 방식이다.스택의 주요 연산푸시 Push스택의 맨 위에 데이터를 추가한다.팝 Pop스택의 맨 위에 있는 데이터를 제거하고 반환한다.탑 Top 또는 Peek스택의 맨 위에 있는 데이터를 확인하되, 제거하지 않는다.isEmpty스택이 비어 있는지를 확인한다.스택의 특징삽입과 삭제가 한쪽 끝에서만 일어난다.후입선출 구조이기 때문에 순서가 반대가 된다.함수 호출, 되돌리기 기능, 괄호 검사, 수식 계산 등에 자주 사용된다.배열을 이용한 스택 구현 예시#include using ..
DEVELOPMENT/Algorithm 연결리스트(Linked List) 연결 리스트 Linked List 는 데이터를 순서대로 저장하지만 배열과 달리 메모리상에 연속적으로 존재하지 않는 자료구조다.각 데이터는 노드 Node 라고 부르며, 노드는 실제 데이터를 저장하는 영역과 다음 노드의 주소를 저장하는 포인터로 구성되어 있다.연결 리스트의 가장 큰 특징은 크기가 가변적이라는 점이다. 즉, 프로그램 실행 중에 노드를 자유롭게 추가하거나 삭제할 수 있다.배열처럼 메모리를 미리 크게 할당할 필요가 없기 때문에 메모리 효율성이 높다.하지만 임의 접근이 불가능하다는 단점이 있다. 특정 위치의 데이터를 찾기 위해서는 처음 노드부터 순차적으로 탐색해야 한다.연결 리스트의 종류단일 연결 리스트 Singly Linked List각 노드가 다음 노드의 주소만을 저장하는 형태다.마지막 노드는 ..
DEVELOPMENT/Algorithm 자료구조 개요 자료구조란?자료구조(Data Structure)는 데이터를 저장, 관리, 접근하는 방식을 의미한다.단순히 데이터를 모아놓는 것이 아니라, 효율적으로 데이터를 사용할 수 있도록 구조화하는 것이 핵심이다.즉, 프로그램이 데이터를 빠르고 효율적으로 처리하도록 설계한 논리적·물리적 구조라고 이해하면 된다.자료구조의 필요성효율적인 데이터 관리단순 배열처럼 무작정 데이터를 저장하면 검색, 삽입, 삭제에 시간이 많이 걸린다.자료구조를 사용하면 필요한 작업을 최소한의 시간으로 수행할 수 있다.알고리즘과의 연계자료구조는 알고리즘과 함께 작동한다.예: 정렬, 탐색, 최단 경로 계산 등 대부분 알고리즘이 자료구조에 의존한다.데이터의 의미 표현데이터 간의 관계, 순서, 계층 구조 등을 표현할 수 있다.예: 트리, 그래프 등자..
반응형

티스토리툴바