Dachae's DevLogs

계수 정렬(Counting Sort) 계수 정렬(Counting Sort)은 값을 직접 비교하지 않고, 등장 횟수를 세는 방식으로 정렬을 수행하는 비비교 정렬 알고리즘입니다. 정수나 정수로 표현 가능한 데이터를 정렬할 때 매우 빠르며, 특히 데이터 값의 범위가 작고, 중복이 많을수록 효율적입니다.정렬하고자 하는 값들의 개수를 카운트 배열에 저장한 뒤, 각 값을 정렬된 위치로 바로 배치하는 방식이기 때문에 최악의 경우에도 O(n + k)의 시간 복잡도를 가집니다. (k는 값의 최대 범위)단점은 데이터 값이 음수이거나, 범위가 너무 넓을 경우 메모리 낭비가 발생할 수 있다는 점입니다. 1. 계수 정렬이란? 계수 정렬은 다음의 방식으로 정렬합니다.입력 배열의 값들을 세어, 값마다 등장 횟수를 저장누적 합을 ..

기수 정렬(Radix Sort) 기수 정렬(Radix Sort)은 데이터를 정렬할 때 숫자의 자릿수(또는 문자열의 위치)를 기준으로 정렬하는 비교하지 않는(non-comparison based) 정렬 알고리즘입니다. 버블 정렬이나 퀵 정렬처럼 값을 비교하지 않고, 숫자나 문자열의 각 자리를 기준으로 여러 번 분류하여 정렬합니다.정수나 고정 길이 문자열과 같이 구조가 명확한 데이터에서 매우 빠르게 동작할 수 있으며, 특히 비교 기반 정렬의 이론적 하한인 O(n log n)을 우회하여 O(nk)의 성능을 달성할 수 있습니다.단점으로는 비교 기반이 아니므로 모든 데이터에 적용할 수는 없으며, 자릿수를 기준으로 반복 작업이 필요하기 때문에 메모리 사용량도 상대적으로 높을 수 있습니다. 1. 기수 정렬이란? 기..

힙 정렬(Heap Sort) 힙 정렬(Heap Sort)은 완전 이진 트리 기반의 힙(Heap) 자료구조를 활용하는 정렬 알고리즘입니다. 정렬 과정에서 힙을 사용해 가장 큰 값(또는 가장 작은 값)을 빠르게 추출하고, 이를 반복하여 정렬을 완성합니다.힙 정렬은 시간 복잡도가 항상 O(n log n)으로 일정하며, 추가적인 메모리를 거의 사용하지 않는 제자리(in-place) 정렬입니다. 단점은 안정 정렬이 아니며, 구현이 다소 복잡하다는 점이지만, 일정한 성능과 메모리 효율이 요구되는 상황에서는 매우 유용한 선택이 될 수 있습니다. 1. 힙 정렬이란? 힙 정렬은 다음과 같은 두 단계를 반복합니다.최대 힙(Max Heap)을 구성하여 가장 큰 값을 루트로 보냅니다.가장 큰 값을 배열 뒤로 보내고, 남은 ..

병합 정렬(Merge Sort) 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 대표적인 정렬 알고리즘입니다. 데이터를 더 이상 나눌 수 없을 만큼 작게 쪼갠 뒤, 나눈 조각들을 정렬하면서 다시 하나로 합치는 방식으로 동작합니다.퀵 정렬과 마찬가지로 평균 시간 복잡도는 O(n log n)이지만, 병합 정렬은 최악의 경우에도 O(n log n)을 보장하며, 안정 정렬이라는 장점도 가집니다. 다만, 추가 메모리 공간이 필요하다는 단점이 있어 메모리 제약이 있는 환경에서는 고려가 필요합니다.이 글에서는 병합 정렬의 개념, 작동 방식, 다양한 언어로의 구현, 성능 분석을 포함해 병합 정렬이 어떤 상황에서 유용한지 살펴봅니다. 1. 병합 정렬이란? 병합 정렬은 데..

퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort)은 평균적으로 가장 빠르게 동작하는 정렬 알고리즘으로 알려져 있으며, 분할 정복(Divide and Conquer) 전략을 기반으로 합니다. 리스트에서 기준 값(피벗, pivot)을 정한 후, 피벗보다 작은 값과 큰 값을 나누어 각각을 재귀적으로 정렬하는 방식입니다.이 알고리즘은 in-place 정렬이 가능하고, 평균 시간 복잡도가 O(n log n)으로 매우 우수하기 때문에 실무에서도 널리 사용되며, 다양한 언어의 표준 라이브러리에도 활용됩니다. 다만, 피벗 선택이 좋지 않으면 최악의 경우 O(n²)까지 성능이 떨어질 수 있어 그에 대한 보완 전략도 함께 알아둘 필요가 있습니다. 1. 퀵 정렬이란? 퀵 정렬은 기준이 되는 값을 하나 정한 뒤,..

삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort)은 필요한 위치에 데이터를 삽입한다는 개념으로 동작하는 정렬 알고리즘입니다. 마치 카드를 손에 들고 하나씩 정렬하며 끼워 넣는 과정과 유사합니다. 간단한 구현과 직관적인 개념 덕분에 학습용으로 자주 사용되며, 실제로도 데이터가 거의 정렬되어 있는 경우 매우 효율적입니다. 1. 삽입 정렬이란? 삽입 정렬은 배열의 각 요소를 앞쪽 정렬된 영역에 하나씩 적절한 위치에 삽입하며 전체를 정렬해 나가는 방식입니다. 앞부분은 이미 정렬되어 있다는 가정 하에, 다음 요소를 비교하며 맞는 자리를 찾아 삽입합니다.작동 원리두 번째 원소부터 시작해서 현재 원소를 앞쪽 정렬된 부분과 비교비교하면서 본인의 위치보다 큰 원소들은 한 칸씩 뒤로 이동빈 ..

선택 정렬(Selection Sort) 선택 정렬(Selection Sort)은 정렬 알고리즘 중에서 개념적으로 가장 간단한 방식 중 하나로, 배열에서 가장 작은(또는 큰) 값을 반복적으로 찾아서 순서대로 앞쪽으로 옮기는 방식입니다. 구현이 매우 직관적이고 코드량도 적기 때문에 알고리즘 입문자에게 자주 소개되는 알고리즘입니다. 하지만 시간 복잡도가 O(n²)으로, 데이터 양이 많아질수록 성능이 크게 떨어져 실무에서는 거의 사용되지 않습니다. 1. 선택 정렬이란? 선택 정렬은 매 반복마다 가장 작은(또는 큰) 원소를 찾아서 현재 위치에 있는 원소와 교환하는 방식입니다.동작 방식 (오름차순 기준)리스트의 첫 번째부터 시작하여 가장 작은 값을 찾음현재 위치의 값과 가장 작은 값을 교환두 번째 위치부터 반복...

버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort)은 정렬 알고리즘 중 가장 단순한 방식으로, 인접한 두 값을 반복적으로 비교하고 필요에 따라 교환하여 정렬을 완성합니다. 이름처럼 큰 값이 점차 리스트 끝으로 ‘버블’처럼 떠오르는 모습에서 유래했습니다. 이 알고리즘은 이해와 구현이 매우 쉬워 알고리즘 학습의 입문 단계에서 자주 사용됩니다. 하지만 효율성 측면에서는 매우 낮기 때문에, 실무에서 사용되는 일은 거의 없습니다. 1. 버블 정렬이란? 버블 정렬은 인접한 두 요소를 비교하여 정렬 기준에 맞지 않으면 서로 교환하는 방식을 여러 번 반복하는 정렬 알고리즘입니다. 가장 큰 값이 반복문 한 번마다 맨 뒤로 이동하므로, 전체가 정렬될 때까지 과정을 반복합니다.작동 방식 (오름차순 기준)리..

정렬(Sorting) 정렬(Sorting)은 데이터를 일정한 순서(오름차순, 내림차순 등)로 재배치하는 알고리즘입니다. 정렬은 탐색, 최적화, 통계 처리 등 거의 모든 컴퓨터 과학 문제의 전처리 단계로 중요하게 사용됩니다. 정렬 알고리즘은 수행 방식, 안정성, 시간/공간 복잡도에 따라 다양하게 나뉘며, 내부 정렬(internal sorting)과 외부 정렬(external sorting)로도 분류할 수 있습니다. 대표적인 정렬 방식에는 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등이 있으며, 각 언어는 기본 라이브러리 또는 메서드를 통해 내부적으로 고도화된 정렬 알고리즘을 제공합니다. 1. 정렬 알고리즘이란?정렬의 목적데이터를 빠르게 검색하거나 탐색을 쉽게 하기 위해이진 탐색..

큐(Queue) 프로그래밍에서 데이터를 순차적으로 저장하고 처리해야 하는 상황은 매우 흔합니다. 이때 유용하게 사용되는 자료구조가 바로 큐(Queue) 입니다. 큐는 먼저 들어간 데이터가 먼저 나오는(FIFO, First-In-First-Out) 특성을 가지며, 실제 생활 속 줄 서기와 매우 유사한 구조를 가지고 있습니다. 이러한 특성 덕분에 프로세스 관리, 작업 스케줄링, 너비 우선 탐색(BFS) 등 다양한 분야에서 큐는 필수적으로 활용됩니다. 1. 큐(Queue)의 개념 큐는 놀이공원의 줄 서기와 같습니다. 먼저 줄을 선 사람이 먼저 놀이기구를 타게 되죠!큐는 데이터를 먼저 들어온 순서대로 처리하는 선형 자료구조입니다. FIFO (First-In-First-Out) 구조로, 먼저 추가한 데이터가 먼..

스택(Stack) 프로그래밍에서 자료를 효율적으로 관리하고 처리하기 위해 다양한 자료구조가 사용됩니다. 그 중에서도 스택(Stack)은 가장 기본적인 자료구조 중 하나입니다. 스택은 데이터를 "쌓았다가 꺼내는" 방식으로 동작하는데, 마지막에 넣은 데이터가 가장 먼저 나오는(LIFO, Last-In-First-Out) 특성을 가지고 있습니다. 이 간단한 원리는 다양한 알고리즘 문제, 특히 괄호 검사, 문자열 처리, 수식 계산, 깊이 우선 탐색(DFS) 등에서 매우 중요한 역할을 합니다. 1. 스택(Stack)의 개념 스택은 마치 접시를 쌓는 것과 같습니다. 마지막에 올린 접시를 먼저 꺼내야 안전하죠!스택은 한 쪽 끝에서만 데이터를 추가하거나 삭제할 수 있는 선형 자료구조입니다. 가장 나중에 들어간 데이터..

슬라이딩 윈도우(Sliding Window) 슬라이딩 윈도우(Sliding Window) 기법은 배열이나 문자열에서 연속된 구간(subarray, substring) 을 다룰 때 매우 유용한 최적화 알고리즘입니다.이 글에서는 슬라이딩 윈도우의 개념, 종류, 구현 방법, 그리고 다양한 언어별(파이썬, C++, 자바, 자바스크립트) 실습 예제까지 제공하여, 초급부터 중급 개발자까지 쉽게 이해하고 응용할 수 있도록 돕겠습니다. 1. 슬라이딩 윈도우란?슬라이딩 윈도우는 일정 범위(구간)를 유지하면서, 그 구간을 배열이나 문자열 위에서 한 칸씩 이동(slide) 시키는 기법입니다. 이 방식을 사용하면, 모든 구간을 새로 계산하지 않고, 이전 구간의 정보를 활용해 빠르게 결과를 업데이트할 수 있습니다.기본 아이디..

투 포인터(Two Pointer) 투 포인터(Two Pointer) 기법은 배열이나 리스트를 빠르게 탐색하거나 조건을 만족하는 부분 구간을 찾을 때 매우 유용한 알고리즘입니다.이 글에서는 투 포인터의 개념부터 다양한 유형, 그리고 언어별(파이썬, C++, 자바, 자바스크립트) 예제 코드까지 다루며, 여러분이 투 포인터를 완벽히 이해하고 실전 문제에 적용할 수 있도록 도와드리겠습니다. 1. 투 포인터(Two Pointer)란?투 포인터는 말 그대로 두 개의 포인터를 이용해 배열이나 리스트를 탐색하는 방법입니다. 이 두 포인터는 한 방향으로 움직이거나, 서로 반대 방향으로 이동하며 문제를 해결합니다.투 포인터 기본 형태시작점과 끝점(start, end)을 설정합니다.각 포인터를 조건에 따라 이동시키면서 원..

구간 합(Prefix Sum) 간 합(Prefix Sum)은 배열이나 수열에서 특정 구간의 합을 빠르게 계산하기 위한 기법입니다. 특히 여러 번 구간 합을 요청받는 문제에서 큰 성능 차이를 만들어내는 핵심 테크닉입니다.이 글에서는 구간 합의 기본 개념부터 구현 방법, 그리고 주요 언어별 코드 예제를 제공하여 여러분이 실전 문제에 바로 적용할 수 있도록 돕겠습니다. 1. 구간 합(Prefix Sum)이란?구간 합은 배열의 특정 구간 [i, j]의 합을 빠르게 구하기 위해 사전에 합을 저장해두는 기법입니다. 일반적인 방법으로 매번 i부터 j까지 합을 구하면 O(N)이 걸리지만, 구간 합 배열을 이용하면 O(1)만에 답을 구할 수 있습니다.기본 아이디어원본 배열 arr이 있을 때, prefix_sum[i] ..

[Lv. 1] 폰켓몬 https://school.programmers.co.kr/learn/courses/30/lessons/1845 문제설명당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다..