🧩 [Data Structure] 대규모 데이터에서의 게시글 목록 조회

Data Structure · 2025-02-03

🧩 [Data Structure] 로그 시간(logarithmic time)이란?

🧩 [Data Structure] 로그 시간(logarithmic time)이란? 🍎 Intro. 로그 시간(logarithmic time)은 시간 복잡도를 분석할 때 사용하는 용어로, 어떤 알고리즘이나 연산이 수행될 때 입력 크기(N)에 따라 작업 시간이 입력 크기의 로그 값에 비례하는 경우를 의미합니다. ✅1️⃣ 로그 시간의 정의. 로그 시간은 입력 크기 N이 증가하더라도 연산 시간 증가가 매우 느린 경우를 나타냅니다. 시간 복잡도를 표현할 때 O(log N)으로 나타냅니다. ✅2️⃣ 로그 시간의 의미. 만약 입력 크기 N이 2배로 늘어나도, 연산 시간은 1회 정도만 추가되는 방식으로 증가합니다. 이는 로그(logarithm)의 성질에 기인하며, 효율적인 알고리즘의 특징입니다. ✅3️⃣ 로그 시간의 예시. 1️⃣ 이진 탐색(Binary Search) - O(log N) 이진 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용됩니다. 배열을 절반으로 나누는 방식으로 탐색하므로, 입력 크기 N에 대해 시간 복잡도는 O(log N)입니다. 📌2️⃣ 예시. 배열 크기: N = 16 비교 횟수: 첫 번째 비교 ➞ 크기 16 ➞ 8로 줄어듦. 두 번째 비교 ➞ 크기 8 ➞ 4. 세 번째 비교 ➞ 크기 4 ➞ 2. 네 번째 비교 ➞ 크기 2 ➞ 1에서 종료. 총 비교 횟수: log₂(16) = 4 3️⃣ B-Tree와 B+ Tree 검색 - O(log N) B-Tree와 B+ Tree는 데이터베이스와 파일 시스템에서 사용되는 효율적인 데이터 구조입니다. 트리의 높이가 log에 비례하므로, 검색과 삽입/삭제 연산 모두 O(log N)의 시간 복잡도를 가집니다. 📌4️⃣ 예시. 데이터 개수: N = 1,000 B+ Tree에서 최대 100개의 자식을 가진다면, 트리의 높이는 log₁₀(1,000) = 3 검색 시간은 3단계만에 원하는 데이터를 찾을 수 있습니다. 4️⃣ 이벤트 처리와 분할 정복 알고리즘. Merge Sort와 같은 분할 정복 알고리즘에서도 로그 시간이 나타납니다. 문제를 절반으로 나누어 재귀적으로 처리하므로, 깊이는 log N에 비례합니다. 병합 과정의 시간은 O(N), 따라서 전체 시간 복잡도는 O(N log N)입니다. ✅4️⃣ 로그 시간의 특징. 1️⃣ 효율성: 로그 시간 복잡도는 대규모 데이터를 처리할 때 매우 효율적입니다. 데이터 크기 N이 기하급수적으로 증가하더라도, 작업 시간은 느리게 증가합니다. 2️⃣ 적용 사례: 검색 알고리즘 : 이진 탐색(Binary Search), B-Tree, AVL Tree, Hash Table 등. 정렬 알고리즘 : Merge Sort, Heap Sort 등. 파일 시스템 및 데이터베이스 : 인덱스 검색(B+ Tree). 3️⃣ 기본 수학: 로그 시간은 log₂(N) 또는 log₁₀(N) 같은 수학적 로그 함수의 성질에 기초합니다. 🚀5️⃣ 정리 로그 시간(logarithmic time)은 O(log N)의 시간 복잡도를 의미하며, 데이터 크기가 증가해도 연산 시간이 느리게 증가합니다. 이는 이진 탐색, 트리 기반 구조, 분할 정복 알고리즘 등에서 나타나는 효율적인 시간 복잡도입니다.

Data Structure · 2025-02-02

🧩 [Data Structure] B-tree와 차수(Degree)란 무엇일까요?

Data Structure · 2025-02-01

🧩 [Data Structure] 자료구조와 재귀

🧩 [Data Structure] 자료구조와 재귀 ✅1️⃣ 자료구조와 재귀. 📌 Intro. ↘︎ 재귀: ‘내 안의 나를 찾는 것’ ↘︎ 즉, 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것. ✅2️⃣ 자료구조와 재귀의 예시. ↘︎ 팩토리얼(Factorial) ↘︎ 1부터 n까지 곱하는 n!(n 팩토리얼)은 $n!\ =\ 1\ ×\ 2\ ×\ 3 \ × ﹒﹒﹒\ × \ (n-1)\ ×\ n$ 이다. ↘︎ 여기서 맨 끝에 n만 제외하면 $1\ ×\ 2\ ×\ 3 \ × ﹒﹒﹒\ × \ (n-1)$인데 이것은 (n-1)!이다. ↘︎ n!은 여기에 n만 더 곱하면 된다. ↘︎ “즉, $n!\ =\ n\ ×\ (n-1)!$” ↘︎ 크기가 n인 팩토리얼은 크기가 n-1인 팩토리얼을 포함하고 있다. ↘︎ 즉, 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러낸 것이다. ↘︎ 이처럼 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 “재귀적 구조”를 갖고 있다고 말한다. ✅3️⃣ 자료구조와 알고리즘 그리고 재귀의 관계. ↘︎ 대부분의 프로그래밍 언어는 함수 내부에서 자신을 호출하는 자기호출(재귀) 기능을 제공한다. ↘︎ 자료구조와 알고리즘은 관계 중심의 사고방식을 훈련하는 도구이기도 하다. ↘︎ 재귀는 학부에서 알고리즘을 다룰 때 명시적으로 40% 정도, 명시적으로 드러나지 않지만 재귀적 성격을 갖고 있는 것 까지 합하면 80% 정도나 차지하는 주제다. ↘︎ 자료구조에서도 상당히 높은 비율을 차지한다. ↘︎ 재귀를 모르고 자료구조와 알고리즘을 공부할 수 없다. ↘︎ 재귀는 컴퓨터 과학 이론의 근간을 이루는 중요 개념으로, 어렵거나 특별한 주제가 아니다. ↘︎ 컴퓨터 과학을 공부하다 보면 재귀는 끊임없이 다양한 얼굴로 출현한다. ↘︎ 따라서 이 주제에 대해 숨 쉬듯이 자연스럽게 받아들여야 한다.

Data Structure · 2025-01-16

🧩 [Data Structure] 재귀 구조의 예(1) - 수열

🧩 [Data Structure] 재귀 구조의 예(1) - 수열 ✅1️⃣ 수열. 1. 초항(First Term) ↘︎ 정의 : 수열에서 첫 번째 항을 의미함. ↘︎ 기호 : 일반적으로 초항은 $a_1$ 또는 $a$로 나타냄. ↘︎ 예시 : 수열: 2, 4, 6, 8, … 초항: $a_1 = 2$ 2. 공차(Common Difference) ↘︎ 정의 : 등차수열에서 연속된 두 항의 차이를 의미함. ↘︎ 기호 : 일반적으로 공차는 $d$로 나타냄. ↘︎ 공식 : ↘︎ $d = a_{n+1} - a_n$ ↘︎ 예시 : ↘︎ 수열 : 2, 4, 6, 8, … ↘︎ 공차 : $d = 4 - 2 = 2$ 3. 점화식 (Recurrence Relation) ↘︎ 정의 : 수열의 각 항을 이전 항(또는 몇 개의 항)을 이용해 표현한 식임. ↘︎ 기호 : 보통 $a_{n+1} = a_n + d$ 형태로 나타남. ↘︎ 예시 : ↘︎ 수열 : 2, 4, 6, 8, … ↘︎ 점화식 : $a_{n+1} = a_n + 2$ 4. 등차수열 (Arithmetic Sequence) ↘︎ 정의 : 연속된 항들의 차이가 일정한 수열. ↘︎ 일반항 공식 : ↘︎ $a_n = a + (n-1)d$ ↘︎ $a$ : 초항 ↘︎ $d$ : 공차 ↘︎ $n$ : 항의 번호 ↘︎ 예시 : ↘︎ 수열 : $2, 4, 6, 8, …$ ↘︎ 초항 : $a = 2$ ↘︎ 공차 : $d = 2$ ↘︎ 5번 째 항 : $a_5 = 2 + (5-1) \cdot 2 = 10$ ✅2️⃣ 재귀적 구조 알고리즘 예시. 📌 등차수열 ↘︎ $a_n = a_{n-1}+3, a_1 = 1$ ↘︎ 초항이 1, 공차가 3인 등차수열의 점화식. ↘︎ 수열의 n번째 원소는 자신과 성격이 똑같지만 순서가 하나 작은 $(n-1)$번째 원소에 3을 더한 것임. ↘︎ 첫 번째 원소는 1. ↘︎ 이것을 재귀 알고리즘으로 구현하면 아래와 같다. seq(n): if (n = 1) return 1 else return seq(n-1) + 3 ↘︎ 알고리즘 seq(n)은 seq(n-1)을 호출, seq(n-1)은 seq(n-2)를 호출. ↘︎ seq(n-2)는 seq(n-3)을 호출… seq(2)는 seq(1)을 호출하고, seq(1)은 1을 리턴하고 끝남. ↘︎ seq(1)이 끝나면 역순으로 진행됨. ↘︎ seq(2)는 seq(1)의 리턴 값을 받아 3을 더해 리턴 ↘︎ seq(3)은 seq(2)의 리턴 값을 받아 3을 더해 리턴 ↘︎ seq(4)는 seq(3)의 리턴 값을 받아 3을 더해 리턴 ↘︎ seq(n)은 seq(n-1)의 리턴 값을 받아 3을 더해 리턴하면서 전체가 끝남. ↘︎ 등차수열은 결과를 바로 계산할 수 있는 식이 있어 굳이 이렇게 구할 필요가 없지만 그 속에 재귀적 구조가 있음을 말하려는 것이다. ↘︎ 재귀 알고리즘은 반복해서 호출하다가 언젠가 끝나야 하는데 이를 위한 경계 조건을 항상 갖고 있어야 한다. ↘︎ 위 알고리즘에서는 if(n=1)이 경계 조건이다 ↘︎ 수열의 초항에 해당한다. 📌 피보나치 수열 ↘︎ 피보나치 수열은 다음과 같다. ↘︎ 첫 두 항은 1이고, 나머지 항은 각각 직전 두 항을 더한 값이다. ↘︎ $f_n = f_{n-1} + f_{n-2}, f_1 = f_2 = 1$ ↘︎ 이것을 재귀 알고리즘으로 구현하면 다음과 같다. fib(n): if (n = 1 or n = 2) return 1 else return fib(n-1) + fib(n-2) ↘︎ 이는 재귀 알고리즘으로 구현한 치명적인 예다. ↘︎ 시간이 너무 많이 걸리기 때문이다. ↘︎ 지수함수적으로 증가한다는 느낌이다. ↘︎ 이렇게 엄청난 시간이 걸리는 이유는 한 번 계산해놓은 결과를 계속 호출하여 지수함수적인 중복을 일으키기 때문이다. ↘︎ 이 문제를 아래와 같이 계산하면 fib_fase(100)은 천만 분의 1초도 걸리지 않는다. fib_fast(n): f[1] ← f[2] ← 1 ◀︎ "f[2] ← 1"과 "f[1] ← 1"을 한꺼번에 적어놓은 것 for i ← 3 to n f[i] ← f[i-1] + f[i-2] return f[n] ↘︎ 재귀는 문제를 해결하는 유용한 도구이지만 잘못 쓰면 치명적이다. ↘︎ 자료구조와 알고리즘에서는 주로 재귀가 유용할 경우에 사용한다.

Data Structure · 2024-12-31

🧩 [Data Structure] 자료구조와 재귀

🧩 [Data Structure] 자료구조와 재귀. 📌 Intro. ↘︎ 재귀는 ‘내 안의 나를 찾는 것’이다. ↘︎ 즉, 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것이다. ✅1️⃣ 재귀의 예시. 1. 팩토리얼(Factorial) ↘︎ n! = n x (n-1)!이다. ↘︎ 크기가 n인 팩토리얼은 크기가 n-1인 팩토리얼을 포함하고 있다. ↘︎ 1부터 n까지 곱하는 n!(n 팩토리얼)은 n! = 1 x 2 x 3 x ... x (n-1) x n이다. ↘︎ 여기서 맨 끝에 있는 n만 제외하면 1 x 2 x 3 x ... x (n-1)인데 이것은 (n-1)!이다. ↘︎ n!은 여기에 n만 더 곱하면 된다. 즉, n! = n x (n-1)!이다. ✅2️⃣ 재귀적 구조. ↘︎ 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다. ↘︎ 자기 자신을 정의하거나 참조하는 구조를 의미한다. ↘︎ 즉, 어떤 개념, 함수, 데이터 구조, 알고리즘 등이 자신을 반복적으로 호출하거나 포함하는 방식을 말한다. ✅3️⃣ 재귀적 구조의 개념. ↘︎ 정의 : 자기 자신을 참조하거나 포함하는 구조. ↘︎ 주요 특징 : 문제를 더 작은 부분 문제로 나누고, 이 부분 문제를 해결한 뒤 결과를 결합하여 전체 문제를 해결함. ↘︎ 종료 조건(Base Case) : 무한히 반복되지 않도록 멈추는 조건이 반드시 필요함. ✅4️⃣ 재귀적 구조의 장단점. 장점 단점 문제를 논리적으로 표현하기 쉽다 반복 호출로 인해 스택 오버플로우 위험이 있다 복잡한 문제를 간결하게 표현할 수 있다 비효율적인 메모리 사용 가능성 종료 조건(Base Case)만 명확하면 구현이 쉽다 반복문(Iterative)보다 속도가 느릴 수 있다 ✅5️⃣ 재귀적 구조의 핵심 요소. ↘︎ Base Case (종료 조건) : 더 이상 재귀가 진행되지 않는 조건임. ↘︎ Recursive Case(재귀 조건) : 문제를 더 작은 단위로 나누고 자기 자신을 호출함. ↘︎ Stack 메모리 사용 : 재귀 호출마다 새로운 스택 프레임이 생성됨. ✅6️⃣ 프로그래밍과 재귀(Recursion) ↘︎ 대부분의 프로그래밍 언어는 함수 내부에서 자신을 호출하는 자기호출 기능을 제공한다. ↘︎ 영어로는 recursion이라고 하고 우리말로 보통 재귀라고 한다. ↘︎ 이런 의미에서, 자료구조와 알고리즘은 관계 중심의 사고방식을 훈련하는 도구이기도 하다. ✅7️⃣ 재귀와 자료구조 그리고 알고리즘. ↘︎ 재귀를 모르고는 자료구조와 알고리즘을 공부할 수 없다. ↘︎ 재귀는 컴퓨터 과학 이론의 근간을 이루는 중요 개념. ↘︎ 어렵거나 특별한 주제가 아님. ↘︎ 컴퓨터 과학을 공부하다 보면 재귀는 끊임없이 다양한 얼굴로 출현함.

Data Structure · 2024-12-30

🧩 [Data Structure] 자료구조의 추상데이터 타입

Data Structure · 2024-12-23

🧩 [Data Structure] 자료구조와 알고리즘

Data Structure · 2024-12-22

🧩 [Data Structure] 자료구조 무엇일까요?

🧩 [Data Structure] 자료구조 무엇일까요? 1️⃣ 자료구조는 데이터를 저장, 조직, 관리하는 방법. 자료구조 자료(데이터)에 효율적으로 접근하고 수정할 수 있도록 저장, 조직, 관리하는 방법에 관한 이론. 2️⃣ 자료구조는 문제 해결에 사용할 부품. 알고리즘 문제 해결 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어 내는 과정을 기술한 것. 자료구조 문제 해결 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어 내는 과정에서 부품의 역할. 자료구조 학습시 필요능력 자료구조는 프로그램으로 구현되고 사용되므로 자료구조를 학습하려면 프로그래밍 능력이 기본으로 필요. 자료구조를 구현, 사용, 결합하는 과정에서 수학적 사고도 크게 도움이 됨. 사고가 체계적일수록 자료구조를 사용한 결과물은 가명하고 관리하기 쉬워짐. 자료구조와 밀접한 관련이 있는 수학은 수열, 수학적 귀납법 등을 포함하는 이산 수학임. 아래 그림은 알고리즘, 자료구조, 프로그래밍, 이산 수학의 관계를 나타냄. 자료구조는 운영체제, 컴퓨터 네트워크, 인공지능, 시스템 프로그래밍, 컴파일러 등 컴퓨터 과학의 거의 모든 주제를 구현하기 위한 사고의 빌딩 블록을 제공함. 3️⃣ 자료구조는 생각하는 방법을 훈련하는 도구. 자료구조를 다루는 과정에 포함된 ‘생각하는 방법’도 매우 중요함. 자료구조를 구현하는 과정. 자료구조들을 이용해서 문제를 해결하는 과정. 문제를 해결하는 과정에서 논리의 골격이 구성되는 방법 또는 스타일 등 자료구조에서 시작되는 시 생각하는 방법은 자연스럽게 알고리즘으로 연결됨. 문제 해결을 위한 생각의 과정에서 ‘의미 단위를 잡는 일’은 매우 중요하다. ‘의미의 매듭을 만든다’고도 표현할 수 있다. 큰 프로젝트를 여러 모듈로 분해하면 각 모듈이 ‘의미의 매듭’이 된다. 또 각 모듈은 더 작은 모듈로 나뉠 수 있다. 즉, ‘의미의 매듭;은 여러 크기로 산재할 수 있다. 프로그래밍에서 어떤 작업을 함수로 만드는 것도 ‘모듈화의 일종’이다. 함수로 분리하면 강한 의미 단위가 된다는 뜻이다. ‘의미의 매듭;을 만드는 과정에서 ‘여러 가지 생각의 구조가 개입’될 수 있는데 ‘가장 중요한 구조’중 하나가 ‘재귀’다. 컴퓨터 과학 전반에 걸쳐 가장 중요한 사고 체계 중 하나 재귀 어떤 문제가 자신과 성격이 똑같지만 크기만 더 작은 문제를 포함하고 있는 구조를 말함. ‘큰 의미 매듭’이 ‘같은 모양의 더 작은 의미 매듭’을 ‘1개 이상 포함’하고 있는 것이라 할 수 있다. 아래 그림은 재귀적 구조의 시에르핀스키 삼각형 예로, 같은 구조가 계층적으로 반복되는 것을 볼 수 있다. 4️⃣ 자료구조의 종류와 자바의 컬렉션 패키지. 자료구조는 아래 그림과 같이 종류가 다양하지만 상황과 목적에 맞게 적절한 자료구조를 선택함으로써 효율적인 데이터 관리가 가능. 자바의 경우 클래스 종류별 패키지로 분류되어 있는데 그중 자료구조 관련 클래스를 모아둔 패키지가 아래 그림과 같은 컬랙션 패키지이다. 이 패키지에서 다양한 자료구조를 손쉽게 사져다 쓸 수 있어 같은 시간 동안 옛날보다 훨씬 큰 작업을 수행 가능. 이렇게 미리 만들어둔 것은 범용으로 사용할 수 있도록 지나치게 많은 기능을 제공하거나, 핵심에 집중하기 위해 최소한의 기능만 넣어 놓은 경우도 있음. 따라서 효율적인 코딩을 위해 직접 만드는 것이 더 바람직한 경우도 있음 자료구조를 직접 만들거나 만들어진 것을 목적에 맞게 잘 활용하려면 자료구조 내부의 작동원리를 이해하고 있어야 함.

Data Structure · 2024-12-21

devkobe24.com

Contact

Data Structure