개발 블로그

카카오 맵이 막히는 길을 피해 최적의 경로를 찾아주고, 유튜브가 내가 좋아할 것 같은 영상을 귀신같이 추천해주는 이유는 Graph라는 자료구조 덕분이다. 우리가 매일 쓰는 앱들 뒤에 조용히 숨어서 열심히 일하고 있는 Graph라는 자료구조를 공부해보려고 한다. Graph 란?그래프는 노드(Node), 엣지(Edge)로 이뤄진 자료구조이다.노드는 데이터를 담는 점이고, 엣지는 그 점들을 잇는 선이다.친구 관계로 생각하면 사람 한 명 한 명이 노드고, "친구"라는 관계가 엣지인 것이다.[나] ---- [친구A] | |[친구B] ---- [친구C]트리도 사실 그래프의 일종이다. 다만 트리는 계층 구조가 있고 사이클이 없는 특수 형태의 그래프이다.그래프는 트리보다 훨씬 자유로운 형태로 연..

Tree 자료구조를 공부하던 중, BST(Binary Search Tree)에서 파생된 구조들을 보다가 B-Tree 계열까지 흘러왔다.단순히 "균형 잡힌 트리"라는 설명에서 멈추지 않고, 각 변형이 어떤 한계를 보완하기 위해 등장했는지 제대로 짚고 싶어서 따로 정리해두기로 했다.https://dev-jiwonpark.tistory.com/54 (4) TreeTree 관련 포스팅을 업로드하기 이전에 Hash table 관련 내용을 올리려고 했는데 이전에 올려뒀던 포스팅이 있어 넘어가고 이번엔 Tree로 진행해보려고 한다.https://dev-jiwonpark.tistory.com/36 [자료구조] Hadev-jiwonpark.tistory.com B-Tree란?BST(Binary Search Tree)는 ..

Tree 관련 포스팅을 업로드하기 이전에 Hash table 관련 내용을 올리려고 했는데 이전에 올려뒀던 포스팅이 있어 넘어가고 이번엔 Tree로 진행해보려고 한다.https://dev-jiwonpark.tistory.com/36 [자료구조] Hash Table (해시 테이블) 알아보기이미지 최적화 공부를 하다가 문득 ‘데이터를 효율적으로 저장하고 꺼내는 방법’이 얼마나 중요한지 깨달았다.특히, 브라우저 캐시나 CDN이 내부적으로 어떻게 이미지를 빠르게 찾아내는지를dev-jiwonpark.tistory.com Tree라는 자료구조를 생각했을때 바로 떠오르는건 DOM 그리고 라우팅 구조였다. 생각해보면 프론트엔드 개발자가 매일 다루는 것들이 사실 전부 트리 구조 위에서 동작하고 있었다.그래서 이 글에서는 ..

Stack과 Queue, 뭐가 다를까?두 자료구조의 핵심 차이는 데이터를 꺼내는 순서이다.넣는 방식은 동일하지만 꺼내는 방향이 정반대이다. StackLIFO(= Last In, First Out) 나중에 넣은 것이 먼저 나온다. 책을 쌓아두고 맨 위부터 꺼내는 것과 같다.핵심 연산(1) push - 맨 위의 요소 추가시간 복잡도 O(1)(2) pop - 맨 위 요소 제거시간 복잡도 O(1)(3) peek - 맨 위 요소 확인 (제거하지 않음)시간 복잡도 O(1)(4) isEmpty - 비어있는지 확인.시간 복잡도 O(1) Stack의 핵심 연산 시간복잡도가 모두 O(1)인 이유는 크기와 상관없이 항상 고정된 위치(Top)만 접근하기 때문이다.추가로 탐색도, 이동도, 재정렬도 없기 때문에 모두 같은 시간..

React로 상태 관리를 하거나, 라우터 히스토리를 다룰 때 우리는 이미 매일 자료구조를 쓰고 있다.하지만 어떤 자료구조로 쓰고 있는지 메모리의 동작 원리까지 제대로 알고 있어야 잘 다룰 수 있지 않을까?!그래서 이번 글에서는 Array 와 Linked List를 같이 다뤄볼 예정이다. 1. Array - 연속된 메모리배열은 메모리 상에 연속된 공간을 미리 잡아두는 구조이다.각 요소는 동일한 크기의 공간을 차지하기 때문에, 첫번째 요소의 주소만 알면 n번째 요소의 주소를 덧셈 한 번으로 바로 계산할 수 있다.인덱스 = 시작 주소 + (인덱스 x 타입크기) 라는 수식으로 계산할 수 있다. 예를 들어 아파트로 비유를 들어보자!배열을 번호가 붙은 아파트 동이라고 상상해보자. 101호, 102호, 103호, 1..

코딩 테스트를 준비하기 전에 자료구조부터 제대로 정리하고 싶어 자료구조 부터 알고리즘 까지 공부하는 과정을 블로그에 기록하기로 했다! 그냥 외우는 것이 아니라 왜 이런 구조가 존재하는지, 언제 써야 하는지, 직접 코드로 구현하면서 공부하기로 결심했다. 그래서 미래에 나를 위한 레퍼런스이니까 한번 잘 정리해보려고 한다. 자료구조란 무엇인가?위키백과 정의를 보면 이렇게 나온다. 자료구조는 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히는, 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 뜻한다.쉽게 말하면 이렇다. 데이터를 어떤 모양으로, 어떤 규칙으로 담느냐가 자료구조이다.프론트엔드 개발을 하면서 이미 자료구조를 쭉 써왔다. 눈치..

자바스크립트의 실행 컨텍스트를 공부하다 보면 콜 스택(Call Stack) 이라는 개념이 꼭 등장한다.처음엔 단순히 함수가 쌓였다가 빠진다 정도로만 이해했는데, 그 구조를 제대로 이해하려면 결국 스택(Stack) 이라는 자료구조 자체를 알아야 한다는 걸 깨달았다.이번 글에서는 실행 컨텍스트를 지탱하는 기반 구조인 스택 자료구조를 공부해보려고 한다.Stack이란?스택은 후입선출(Last In, First Out = LIFO) 구조의 자료구조다.나중에 들어온 데이터가 먼저 나가는 구조를 가진다. 스택은 보통 3 가지 핵심 연산으로 구성된다.push(item)새로운 데이터를 스택의 맨 위(top)에 추가pop()스택의 맨 위 데이터를 제거하고 반환peek()스택의 맨 위 데이터를 제거하지 않고 확인 간단한 자..

이미지 최적화 공부를 하다가 문득 ‘데이터를 효율적으로 저장하고 꺼내는 방법’이 얼마나 중요한지 깨달았다.특히, 브라우저 캐시나 CDN이 내부적으로 어떻게 이미지를 빠르게 찾아내는지를 이해하려면 자료구조의 기본 원리를 알아야 했다.그중에서도 해시 테이블(Hash Table) 은 데이터를 ‘빠르게 찾는 구조’의 대표적인 예라서, 이번엔 그 원리를 정리해보기로 했다.1. 해시 테이블 이란?해시 테이블(Hash Table) 은 데이터를 (Key, Value) 형태로 저장하는 자료구조이다.핵심 원리는 다음과 같다.데이터를 단순히 순서대로 저장하는 대신, Key 값을 해시 함수(Hash Function) 에 넣어배열의 인덱스(Index) 로 변환하고, 그 인덱스 위치(=버킷, 슬롯 이라고 부른다.)에 값을 저장한..