5주차 개념 정리아래의 내용을 코드 블럭 우측 상단의 Copy 버튼을 눌러 복사한 뒤, 퀴즈 로봇의 프롬프트에 붙여넣기하면 핵심 개념들에 대한 퀴즈를 풀어볼 수 있습니다. 퀴즈 로봇을 제작해 주신 신명훈 학우님께 감사드립니다. □ BST와 B-treeBST와 B-tree는 정렬된 데이터를 빠르게 탐색하기 위한 트리 형태의 자료구조이지만,메모리 중심의 BST와 디스크 중심의 B-Tree는 구조와 성능 유지 방식에서 큰 차이를 보인다.■ BST (Binary Search Tree)왼쪽 서브트리의 모든 값이 부모 노드보다 작고, 오른쪽 서브 트리의 모든 값이 부모 노드보다 큰 메모리 기반 이진 트리▶ 핵심 특징노드 구조: 각 노드는 최대 2개의 자식을 가짐균형 보장: 불가 (→ 편향 트리가 되어 성능이 저하될..

동적 메모리 할당과 관련 함수(malloc, calloc, realloc, free)프로그램 실행 중 필요한 만큼 메모리를 할당받는 방식을 동적 메모리 할당이라고 하는데요. 주로 Heap 영역에서 메모리를 할당하며, 크기가 정해지지 않은 배열이나 구조체 등을 유연하게 다룰 수 있게 해줍니다.정적 메모리 할당: 컴파일 시 크기 고정 (int arr[100])동적 메모리 할당: 실행 시 크기 결정 (malloc 등 사용) 동적 메모리 할당 함수 malloc, calloc, realloc, freemalloc(memory allocation): 초기화 없이 메모리를 할당하는 함수calloc(clear allocation): 0으로 초기화된 메모리를 할당하는 함수realloc(re-allocation): 할당된..

GCC(GNU Compiler Collection)GCC는 GNU 프로젝트에서 만든 자유 소프트웨어 컴파일러 모음입니다. 원래는 C 언어 전용 컴파일러였지만, 지금은 C, C++, Objective-C, Fortran, Ada, Go 등 다양한 언어를 지원하는 다중 언어 컴파일러 도구 모음으로 발전했습니다. GCC의 주요 특징다양한 언어 지원: C, C++, Fortran, Go 등플랫폼 독립성: 리눅스, 윈도우, macOS 등 다양한 운영체제에서 사용 가능최적화 기능: 코드 실행 속도 향상을 위한 다양한 최적화 옵션 제공오픈소스: 누구나 자유롭게 사용, 수정, 배포 가능 GCC의 주요 역할전처리(PreProcessing): #include, #define 등을 처리컴파일(Compiling): C코드 ..

보이어-무어(Boyer-Moore) 문자열 탐색 알고리즘보이어-무어 알고리즘은 텍스트(text) 안에서 패턴(pattern) 을 탐색할 때, 비교 횟수를 줄여 효율적으로 문자열을 찾는 문자열 탐색 알고리즘입니다. 문자열 탐색 알고리즘 중 하나인 KMP보다도 빠른 평균 시간 복잡도를 자랑하며, 특히 패턴이 길고 텍스트가 클 때 효율적입니다.최악 시간 복잡도: O(N * M) (두 문자열 길이의 곱)평균 시간 복잡도: O(N + M) (두 문자열 길이의 합. 다만 KMP보다 훨씬 빠름.) 보이어-무어 알고리즘의 핵심 아이디어오른쪽에서 왼쪽으로 패턴을 비교하면서, 불일치가 발생했을 때 최대한 많이 건너뛰기 위한 두 가지 규칙을 사용합니다.Bad Character Rule (나쁜 문자 규칙)불일치한 문자가 패턴..

KMP(Knuth-Morris-Pratt) 알고리즘문자열 탐색에서 효율성을 극대화할 수 있는 알고리즘 중 하나가 KMP(Knuth-Morris-Pratt) 알고리즘인데요. 이 글에서는 KMP의 핵심 개념과 그 중심에 있는 실패 함수에 대해 간단하게 정리해봅니다. KMP 알고리즘이란? KMP는 문자열 A(텍스트) 안에 문자열 B(패턴)가 포함되어 있는지를 두 문자열의 길이의 합인 O(N + M)의 시간복잡도로 탐색하는 알고리즘입니다. 기존의 브루트포스 방식은 패턴이 중간에 틀릴 때 처음부터 다시 비교하지만, KMP는 틀린 위치까지의 정보를 활용해 불필요한 비교를 줄입니다. 이를 가능하게 해주는 핵심 도구가 바로 실패 함수(Failure Function)입니다. 실패 함수패턴 문자열의 접두사 == 접미사..

가상화(Virtualization)가상화(Virtualization)는 하나의 물리적인 시스템 자원을 마치 여러 개인 것처럼 나누어 사용하는 기술입니다. 즉, 컴퓨터 시스템의 리소스를 추상화하고 격리하여, 다양한 환경을 독립적으로 구성할 수 있게 해줍니다. 가상화를 쉽게 비유하면 '샵인샵(shop-in-shop)'이라고 할 수 있는데요. 대형 마트(물리 서버) 안에 여러 브랜드 매장(가상 머신)이 독립적으로 입점해 운영되듯, 하나의 서버 안에 여러 가상 환경이 서로 간섭 없이 운영될 수 있게 해주는 것이죠.  가상화를 사용하는 이유자원 활용도 향상: 서버 한 대로 여러 서비스를 운영운영 환경 격리: 테스트/배포 환경을 독립적으로 유지보안 및 장애 격리: 한 가상 환경의 문제가 다른 환경에 영향을 주지 않..

스택과 레지스터스택(Stack)정의프로시저 호출 시 지역 변수와 매개 변수를 저장하기 위한 메모리 공간. 선언되는 순서와 반대로 메모리가 해제되는 LIFO(Last In First Out) 구조를 가지고 있다.용도함수의 로컬 변수 저장: 각 함수 호출 시 그 함수의 지역 변수들을 저장함수의 제어 흐름 관리: 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보를 저장장점동적으로 메모리를 할당/해제할 수 있다.구현이 간단하며, 메모리 관리 오버헤드가 낮다.레지스터(Register)정의프로세서 내부에서 데이터를 저장하는 초고속 저장장치. 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용된다.용도중간 연산 결과의 저장: 연산 중 생성되는 중간 값을 빠르게 저장하고 ..

CSAPP[CSAPP 3장 완전정복] 시리즈 참고 (링크: 3.1절 핵심 정리)https://just-live.tistory.com/entry/CSAPP-3%EC%9E%A5-%EC%99%84%EC%A0%84-%EC%A0%95%EB%B3%B5-31-%EC%96%B4%EC%85%88%EB%B8%94%EB%A6%AC-%EC%96%B8%EC%96%B4%EC%99%80-%EC%B9%9C%ED%95%B4%EC%A7%80%EB%8A%94-%EC%B2%AB-%EA%B1%B8%EC%9D%8C [CSAPP 3장 완전 정복] 3.1 어셈블리 언어와 친해지는 첫 걸음어셈블리 언어와 친해지는 첫 걸음우리는 이미 자바, 파이썬 등 편리하고 생산적인 고급 언어를 사용해 프로그램을 개발하고 있습니다. 그렇다면, 도대체 저 먼 옛날에..