본문 바로가기

전체 글

Prefix Sum부터 Dashboard 최적화까지: 반복 계산을 없애는 사고방식 이번 주에는 정렬, 이분 탐색, Two Pointer와 Sliding Window, DFS/BFS를 차례로 공부했다.각 알고리즘의 동작 방식은 다르지만 공통적으로 보이는 생각이 하나 있었다.이미 알고 있는 정보를 활용해서 불필요한 계산을 줄일 수 없을까?Prefix Sum(누적합)은 이 질문을 가장 직접적으로 보여주는 알고리즘이다.처음에는 단순히 배열의 합을 빠르게 구하는 방법처럼 보이지만, 원리를 따라가다 보면 백엔드에서 사용하는 사전 집계(Pre-aggregation), Materialized View, Cache 같은 성능 최적화 방식과도 비슷한 사고방식을 발견할 수 있다.이번에는 Prefix Sum의 원리부터 Greedy와의 차이, 그리고 대규모 Dashboard 집계 문제까지 연결해서 정리한다... 더보기
DFS와 BFS는 왜 Stack과 Queue를 사용할까? 재귀부터 웹 크롤링까지 자료구조를 공부하면서 Stack, Queue, Set의 특징을 각각 배웠다.그런데 자료구조를 따로 공부할 때는 이런 의문이 남았다.Stack과 Queue를 실제로 어디에 사용하는 걸까?DFS는 왜 Stack이고 BFS는 왜 Queue일까?DFS와 BFS를 공부하면서 이 자료구조들이 실제 알고리즘 안에서 어떻게 조합되는지 조금 더 명확하게 연결할 수 있었다.이번 글에서는 단순히 DFS와 BFS 코드를 외우기보다 탐색 순서가 어떻게 Stack과 Queue라는 자료구조로 이어지는지를 정리한다.1. 그래프 탐색이란 무엇인가?먼저 DFS와 BFS가 무엇을 탐색하는 알고리즘인지부터 볼 필요가 있다.다음과 같은 구조가 있다고 하자. A / \ B .. 더보기
계산을 다시 하지 않는 방법: Two Pointer와 Sliding Window 이해하기 정렬과 이분 탐색을 공부한 뒤 Two Pointer와 Sliding Window를 살펴봤다.처음에는 두 기법 모두 left, right 같은 인덱스를 움직이는 방식이라 비슷해 보였다. 하지만 공부하면서 중요한 것은 포인터 자체가 아니라는 점을 알게 됐다.핵심 질문은 이것이었다.이미 확인하거나 계산한 정보를 이용해서 다음 탐색에서 불필요한 작업을 어떻게 제거할 수 있을까?Two Pointer는 조건을 이용해 탐색할 필요가 없는 후보를 제거하고, Sliding Window는 이전 구간의 결과를 이용해 같은 값을 다시 계산하는 일을 제거한다.둘의 방식은 조금 다르지만 결국 같은 방향을 바라보고 있다.1. Two Pointer란 무엇인가?Two Pointer는 이름 그대로 두 개의 위치를 관리하면서 문제를 해결.. 더보기
이분 탐색은 왜 O(log N)일까? 정렬된 데이터에서 절반을 버리는 원리 정렬과 O(N log N)을 공부한 다음 이분 탐색(Binary Search)을 살펴봤다.처음에는 이분 탐색을 left, right, mid를 움직이면서 값을 찾는 알고리즘 정도로 생각하기 쉽다. 하지만 더 중요한 질문은 따로 있다.왜 데이터가 정렬되어 있으면 O(N)이 걸리던 탐색을 O(log N)으로 줄일 수 있을까?이 질문을 이해하면 단순히 이분 탐색 코드를 외우는 것을 넘어, 정렬된 정보가 탐색 성능에 어떤 영향을 주는지 이해할 수 있다.그리고 이 사고방식은 이후 DB의 B+Tree Index나 Composite Index, Keyset Pagination을 공부할 때도 연결된다.1. 하나씩 찾는 방법은 왜 O(N)일까?다음과 같이 100만 개의 숫자가 있다고 하자.[1][2][3][4][5] ... 더보기
정렬은 어디서 해야 할까? Bubble Sort부터 DB ORDER BY와 Keyset Pagination까지 자료구조와 시간복잡도를 공부한 뒤 알고리즘으로 넘어가면서 가장 먼저 정렬(Sorting)을 살펴봤다.처음에는 정렬 알고리즘이라고 하면 Bubble Sort, Merge Sort 같은 알고리즘의 구현 방법을 외우는 것이 중요하다고 생각하기 쉽다.하지만 백엔드 개발 관점에서 더 궁금했던 것은 따로 있었다.왜 어떤 정렬은 O(N²)이고 어떤 정렬은 O(N log N)일까?그리고 실제 서비스에서는 애플리케이션과 DB 중 어디에서 정렬해야 할까? 이 질문을 따라가다 보니 정렬 알고리즘의 시간복잡도와 DB의 ORDER BY, 인덱스, Pagination이 서로 떨어진 주제가 아니라는 것을 알 수 있었다.1. 정렬이란 무엇인가?정렬은 데이터를 특정 기준에 따라 순서대로 배치하는 작업이다.예를 들어 다음 배열이 있다고.. 더보기
[자료구조]백엔드 개발에서 자료구조는 언제 사용할까? Spring과 FastAPI로 이해하는 List, Set, Map자료구조를 공부하다 보면 이런 생각이 들 때가 있다.List, Set, HashMap을 배우긴 했는데 실제 백엔드 개발에서는 어디에 사용하는 걸까?코딩테스트에서는 배열을 순회하고 HashMap으로 값을 찾는 문제를 많이 풀지만, 실제 Spring이나 FastAPI 프로젝트를 개발할 때는 자료구조가 조금 다르게 느껴졌다.하지만 DB에서 데이터를 조회하고 DTO로 변환하는 과정을 생각해보니 자료구조가 왜 필요한지 조금씩 연결되기 시작했다.이번 글에서는 기사(Article) 데이터를 예제로 List, Set, Map이 실제 백엔드에서 어떻게 사용되는지 정리해보려고 한다.1. DB에서 데이터를 조회하면 어디로 갈까?먼저 다음과 같은 article .. 더보기
[자료구조] Stack, Queue, Deque 쉽게 이해하기 백엔드 개발을 공부하다 보면 Stack, Queue, Deque라는 자료구조를 자주 만나게 된다.처음에는 보통 이렇게 외운다.Stack = LIFOQueue = FIFO하지만 단순히 용어만 외우면 금방 헷갈린다.이번 글에서는 세 자료구조를 “데이터를 어떤 순서로 넣고 꺼내는가?”라는 관점에서 이해해보려고 한다.특히 Python에서 list와 deque가 어떻게 다른지, 그리고 왜 list.pop(0)보다 deque.popleft()를 사용하는 것이 좋은지도 함께 살펴본다.1. Stack, Queue, Deque의 차이세 자료구조의 가장 큰 차이는 데이터를 꺼내는 순서다.데이터가 다음과 같이 들어왔다고 생각해보자.A → B → CStack에서는 마지막에 들어온 C가 먼저 나온다.C → B → AQueue에.. 더보기
[알고리즘] 정렬 알고리즘 알고리즘 공부를 시작하면서 가장 먼저 마주치는 주제 중 하나가 정렬(Sorting)이다.처음에는 단순하게 생각했다.숫자를 작은 순서대로 나열하는 걸 왜 이렇게 깊게 공부해야 하지?하지만 정렬은 코딩테스트에서만 등장하는 개념이 아니다.백엔드 개발을 하다 보면 자연스럽게 이런 코드를 자주 만나게 된다.ORDER BY created_at DESC 게시글 최신순 조회, 인기순 랭킹, 상품 가격순 정렬, 로그 시간순 조회처럼 실제 서비스에서도 데이터의 순서는 굉장히 중요하다.특히 대용량 데이터를 다룰수록 중요한 것은 단순히 데이터를 정렬할 수 있느냐가 아니라, 어디에서, 얼마나 많은 데이터를, 어떤 방식으로 정렬할 것인가? 라는 문제다. 이번 글에서는 Bubble Sort와 Merge Sort를 통해 O(N²)과.. 더보기

티스토리툴바