Dachae's DevLogs

[Queue] 줄 서서 처리하는 선입선출(FIFO) 자료구조

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

[Stack] 쌓고 꺼내는 후입선출(LIFO) 자료구조

스택(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마리를 고르는 방법은 다..

[Lv. 1] 완주하지 못한 선수 https://school.programmers.co.kr/learn/courses/30/lessons/42576 문제설명수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.제한사항마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.completion의 길이는 participant의 길이보다 1 작습니다.참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니..