선형 검색(Linear Search)은 가장 기본적이고 단순한 탐색 기법입니다. 데이터 집합의 첫 번째 요소부터 마지막 요소까지 하나씩 순서대로 확인하면서 원하는 값을 찾아냅니다. 이 방식은 정렬되지 않은 데이터에도 그대로 적용할 수 있다는 큰 장점이 있으며, 순차 검색(Sequential Search)이라고도 불립니다. 이름이 선형(linear)인 이유는 시간 복잡도가 데이터의 크기 n에 비례하여 O(n)으로 증가하기 때문입니다.선형 검색의 복잡도시간 복잡도: O(n)공간 복잡도: O(1)입력과 출력입력:데이터 목록:20 4 89

삼항 검색(Ternary Search)은 이진 탐색(Binary Search)과 마찬가지로 정렬된 리스트를 하위 리스트로 나누어 탐색하는 알고리즘입니다. 이진 탐색이 리스트를 두 부분으로 나누는 것과 달리, 삼항 검색은 두 개의 중간값(mid)을 사용하여 리스트를 세 부분으로 분할합니다. 리스트를 더 많은 구간으로 나눌수록 키 값을 찾기 위해 확인해야 할 범위가 빠르게 줄어들어 탐색 효율이 향상됩니다.삼항 검색의 복잡도시간 복잡도(Time Complexity): O(log₃ n)공간 복잡도(Space Complexity): O(1)

버블 정렬(Bubble Sort)은 비교 기반 정렬 알고리즘으로, 인접한 두 요소를 차례대로 비교하고 필요할 때 서로 교환(swap)하여 배열 전체를 올바른 순서로 만들어 갑니다. 다른 정렬 알고리즘에 비해 구현이 매우 간단하지만, 그만큼 성능 면에서 단점도 있습니다. 특히 데이터 개수가 많은 대규모 데이터셋에는 부적합하며, 정렬 작업을 완료하는 데 상당한 시간이 소요될 수 있습니다. 버블 정렬의 동작 원리 버블 정렬은 배열의 처음부터 끝까지 인접한 두 요소를 비교하며, 앞의 값이 뒤의 값보다 크면 두 값을 맞바꿉니다. 이러한 과

비영구 CSMA(Non-persistent CSMA)는 매체 접근 제어(MAC, Medium Access Control) 계층에서 동작하는 반송파 감지 다중 접속(CSMA, Carrier Sense Multiple Access) 프로토콜의 한 방식으로, 채널이 사용 중일 때 공격적으로 재전송을 시도하지 않는 비공격적(non-aggressive) 버전입니다.CSMA 계열 프로토콜에서는 둘 이상의 사용자 또는 노드가 하나의 케이블이나 광섬유처럼 여러 노드를 연결하는 공유 매체, 혹은 무선 주파수 스펙트럼의 일부를 통해 데이터를 송수신합

1-지속 CSMA(1-persistent CSMA)는 매체 접근 제어(MAC) 계층에서 동작하는 반송파 감지 다중 접속(CSMA) 프로토콜의 공격적인 방식입니다. CSMA 프로토콜에서는 여러 사용자 또는 노드가 공유 매체를 통해 데이터를 주고받습니다. 이 공유 매체는 여러 노드를 연결하는 단일 케이블이나 광섬유일 수도 있고, 무선 스펙트럼의 일부일 수도 있습니다. 1-지속 CSMA에서는 송신 스테이션이 전송할 프레임을 갖고 있을 때 채널이 사용 중인 것으로 감지되면, 해당 전송이 끝날 때까지 기다렸다가 즉시 프레임을 전송합니다. 채

P-지속형(p-persistent) CSMA는 반송파 감지 다중 접속(Carrier Sense Multiple Access, CSMA) 프로토콜의 한 방식으로, 1-지속형 CSMA와 비지속형(non-persistent) CSMA의 장점을 결합한 기술입니다. CSMA 프로토콜에서는 여러 사용자 또는 노드가 하나의 공유 매체를 통해 데이터를 송수신합니다. 이 공유 매체는 여러 노드를 연결하는 단일 케이블이나 광섬유일 수도 있고, 무선 주파수 스펙트럼의 일부일 수도 있습니다.P-지속형 CSMA에서는 전송할 프레임을 가진 송신국이 채널이

CSMA/CD(Carrier Sense Multiple Access with Collision Detection, 충돌 감지 기능을 갖춘 반송파 감지 다중 접속)는 매체 접근 제어(MAC) 계층에서 동작하는 반송파 전송용 네트워크 프로토콜입니다. 이 방식은 여러 스테이션이 하나의 공유 채널을 함께 사용하는 환경에서, 전송 전에 채널이 사용 중인지 먼저 감지(listen)하고, 채널이 비어 있을 때까지 전송을 미루는 것이 핵심 원리입니다.그럼에도 불구하고 두 개 이상의 스테이션이 거의 동시에 전송을 시작하면 충돌(collision)이

CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)는 매체 접근 제어(MAC) 계층에서 동작하는 반송파 전송용 네트워크 프로토콜입니다. 충돌이 발생한 후 이를 처리하는 CSMA/CD(Carrier Sense Multiple Access/Collision Detection)와 달리, CSMA/CA는 충돌이 발생하기 전에 이를 사전에 방지하는 것이 특징입니다.CSMA/CA 알고리즘 동작 과정CSMA/CA의 동작 절차는 다음과 같습니다.프레임 전송 준비가 완료되면 송신 스테이

추상 데이터 타입(ADT)이란?데이터 타입(Data Type)은 컴퓨터 프로그램에서 사용할 수 있는 데이터의 종류를 의미합니다. 정수형(integer), 실수형(float)처럼 자료의 형태를 나타낼 뿐만 아니라, 해당 데이터가 차지하는 메모리 공간의 크기도 함께 정의합니다. 예를 들어 정수형은 일반적으로 4바이트, 문자형(character)은 1바이트의 공간을 사용합니다.추상 데이터 타입(Abstract Data Type, ADT)은 그중에서도 특별한 종류의 데이터 타입으로, 값의 집합과 연산의 집합으로 그 동작이 정의됩니다. 여기

스택(Stack)은 마지막에 삽입된 데이터가 가장 먼저 삭제되는 LIFO(Last In First Out, 후입선출) 방식으로 동작하는 대표적인 자료구조입니다. 이러한 특성 덕분에 스택은 수식 평가(expression evaluation), 함수 호출 관리, 재귀(recursion) 처리 등 다양한 컴퓨터 과학 분야에서 폭넓게 활용됩니다. 이번 글에서는 스택의 핵심 연산들을 살펴보고, 스택 ADT를 활용한 예제까지 함께 확인해 보겠습니다.ADT(추상 자료형)란 무엇인가?ADT(Abstract Data Type, 추상 자료형)는 값들

꼬리 재귀란 무엇인가?꼬리 재귀(tail recursion)는 재귀 호출이 함수의 마지막(꼬리) 문장으로 실행되는 재귀를 의미합니다. 즉, 재귀 호출이 끝나고 반환된 이후에 더 이상 수행할 작업이 남아 있지 않은 경우를 말합니다. 이러한 특성 덕분에 컴파일러가 코드를 효율적으로 최적화할 수 있어, 일반적인 재귀보다 성능 면에서 유리합니다.꼬리 재귀 예제다음은 n부터 0까지의 숫자를 출력하는 간단한 꼬리 재귀 함수입니다.#include <iostream> using namespace std; void printN(int

큐(Queue)란 무엇인가? 큐(Queue)는 선입선출(FIFO, First In First Out) 방식으로 동작하는 대표적인 자료구조입니다. 즉, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조를 가지며, 너비 우선 탐색(BFS, Breadth First Search)과 같은 그래프 탐색 알고리즘을 비롯해 다양한 분야에서 널리 활용됩니다. ADT(추상 자료형)의 개념 ADT(Abstract Data Type, 추상 자료형)는 값의 집합과 연산의 집합으로 그 동작이 정의되는 특수한 형태의 자료형입니다. 추상이라는 표현이 붙는

단계 수(Step Count) 방법이란?단계 수(Step Count) 방법은 알고리즘을 분석하는 대표적인 기법 중 하나입니다. 이 방법은 알고리즘 내 각 명령문이 실제로 몇 번 실행되는지 횟수를 세고, 그 결과를 바탕으로 알고리즘의 시간 복잡도를 도출합니다.예를 들어 순차 탐색(Sequential Search) 알고리즘이 있다고 가정해 보겠습니다. 각 명령문이 실행되는 데 각각 c1, c2 … 만큼의 시간이 소요된다면, 이 알고리즘의 시간 복잡도를 아래와 같이 계산할 수 있습니다.알고리즘실행 횟수비용(Cost)seqSearch(ar

이 글에서는 두 행렬을 곱하는 방법, 즉 행렬 곱셈(Matrix Multiplication) 알고리즘에 대해 자세히 살펴보겠습니다.행렬 곱셈의 기본 조건행렬 곱셈은 모든 행렬에 대해 항상 가능한 것은 아니며, 반드시 다음 조건을 만족해야만 수행할 수 있습니다.두 행렬 A와 B가 있고, 각각의 크기(차원)가 A는 m×n, B는 p×q라고 가정해 봅시다. 이때 두 행렬의 곱은 첫 번째 행렬 A의 열(column) 개수 n과 두 번째 행렬 B의 행(row) 개수 p가 같을 때, 즉 n = p인 경우에만 계산할 수 있습니다.조건이 만족되면

상각 분석(Amortized Analysis)이란?상각 분석은 가끔 발생하는 연산은 매우 느리지만, 빈번하게 실행되는 대부분의 연산은 빠른 경우에 사용하는 비용 분석 기법입니다. 해시 테이블(Hash Table), 분리 집합(Disjoint Set) 등의 자료 구조 성능을 평가할 때 상각 분석이 반드시 필요합니다.해시 테이블에서는 대부분의 경우 탐색 시간 복잡도가 O(1)로 상수 시간이 소요되지만, 때때로 O(n) 연산이 실행되기도 합니다. 해시 테이블에서 원소를 검색하거나 삽입할 때 일반적으로는 상수 시간 안에 작업이 완료되지만,

배열 자료구조의 핵심 기본 연산배열(Array)은 가장 기본적이면서도 폭넓게 활용되는 자료구조로, 프로그래밍에서 반드시 알아야 할 다음과 같은 핵심 연산들을 제공합니다.순회(Traverse): 배열의 모든 요소를 처음부터 끝까지 차례대로 방문하며 확인삽입(Insertion): 배열의 지정된 위치에 새로운 요소 추가삭제(Deletion): 배열에서 특정 요소를 제거하고 뒤쪽 요소들의 위치를 앞으로 당김검색(Search): 배열 내에서 원하는 값이 존재하는지 탐색갱신(Update): 특정 위치의 요소 값을 새로운 값으로 변경순회는 배열

이번 글에서는 이진 트리(binary tree)를 컴퓨터 메모리에 어떻게 표현하는지 살펴보겠습니다. 이진 트리를 표현하는 대표적인 방법은 두 가지가 있습니다. 바로 배열(Array)을 이용하는 방법과 연결 리스트(Linked List)를 이용하는 방법입니다.1. 배열을 이용한 표현먼저 다음과 같은 트리가 있다고 가정해 보겠습니다.배열 표현 방식은 트리의 요소들을 레벨 순서(level order), 즉 위에서 아래로, 같은 레벨에서는 왼쪽에서 오른쪽으로 차례대로 탐색하면서 데이터를 저장합니다. 따라서 노드들이 레벨별로 순서대로 배열에

이진 트리의 주요 속성이 글에서는 이진 트리(Binary Tree) 자료 구조가 가지는 중요한 속성들을 살펴보겠습니다. 먼저 아래와 같은 이진 트리가 있다고 가정해 보겠습니다.이진 트리의 대표적인 속성들은 다음과 같습니다.1. 레벨별 최대 노드 수레벨 l에서 가질 수 있는 최대 노드 수는 2l-1입니다. 여기서 레벨(level)이란 루트에서 해당 노드까지의 경로에 포함된 노드의 개수를 의미하며, 루트 자신도 포함됩니다. 이때 루트의 레벨은 1로 간주합니다.2. 높이별 최대 노드 수높이가 h인 이진 트리에 존재할 수 있는 최대 노드

이 글에서는 이진 탐색 트리(Binary Search Tree)에 저장된 모든 키를 체계적으로 방문하는 네 가지 대표적인 순회(Traversal) 알고리즘을 살펴봅니다. 바로 중위 순회(Inorder Traversal), 전위 순회(Preorder Traversal), 후위 순회(Postorder Traversal), 그리고 레벨 순서 순회(Level-order Traversal)입니다. 설명을 위해 다음과 같은 이진 탐색 트리가 있다고 가정하겠습니다. 네 가지 순회 방식과 결과 비교 1. 중위 순회 (Inorder Trav

이 글에서는 이진 탐색 트리(Binary Search Tree)를 레벨 순서(level-order)로 순회하는 방법을 살펴보겠습니다. 레벨 순서 순회는 루트 노드부터 시작해 같은 깊이(레벨)에 있는 노드들을 왼쪽에서 오른쪽으로 차례대로 방문한 뒤, 한 단계 아래 레벨로 내려가는 방식입니다. 너비 우선 탐색(BFS, Breadth-First Search)과 같은 개념으로, 큐(queue) 자료구조를 활용해 손쉽게 구현할 수 있습니다. 레벨 순서 순회의 동작 원리 예를 들어 다음과 같은 이진 탐색 트리가 있다고 가정해 보겠습니다. 루