토랑님의 블로그

메모리 관리의 필요성1) 단순 메모리 관리 기법의 한계초기 운영체제에서는 단순한 연속 메모리 할당 방식을 사용했지만, 이는 단편화(Fragmentation) 문제를 유발하고, 프로그램이 커질 경우 메모리 할당이 어려워지는 문제가 있음2) 가상 메모리(Virtual Memory) 개념 도입현대 운영체제에서는 가상 메모리를 사용하여 실제 물리적 메모리(RAM)보다 큰 프로그램을 실행할 수 있도록 함가상 메모리는 페이지(Page) 단위로 관리되며, 프로세스가 필요할 때만 실제 물리적 메모리에 로드됨단편화단편화(Fragmentation)는 운영체제가 메모리를 효율적으로 관리하는 과정에서 사용할 수 없는 작은 메모리 조각들이 발생하는 문제를 의미단편화가 심해지면 메모리가 충분히 존재함에도 불구하고 새로운 프로세스..

CPU 스케줄링 알고리즘CPU 스케줄링은 운영체제가 프로세스를 효과적으로 처리하기 위해 CPU를 각 프로세스에 할당하는 메커니즘시스템 성능, 처리율(Throughput), 응답 시간(Response Time), 대기 시간(Waiting Time) 등을 최적화CPU 스케줄링의 기본 목표공정성(Fairness)모든 프로세스가 CPU를 공평하게 사용효율성(Efficiency)CPU가 최대한 사용되도록 유지반환 시간 최소화(Turnaround Time)프로세스가 완료되는 데 걸리는 시간을 최소화대기 시간 최소화(Waiting Time)프로세스가 CPU를 기다리는 시간을 줄임응답 시간 최소화(Response Time)사용자와 상호작용이 필요한 프로세스의 응답 시간 최소화주요 CPU 스케줄링 알고리즘비선점형(Non..

개념분할 정복(Divide and Conquer)은 문제를 더 작은 부분 문제로 분할한 뒤, 각 부분 문제를 재귀적으로 해결하고, 그 결과를 결합하여 원래 문제의 해답을 얻는 알고리즘 설계 기법주요 단계Divide (분할)문제를 동일하거나 유사한 더 작은 부분 문제로 나눔Conquer (정복)나눠진 부분 문제를 재귀적으로 해결부분 문제가 충분히 작아질 경우 직접 해결Combine (결합)부분 문제의 해답을 결합하여 원래 문제의 해답을 얻음특징재귀적 접근분할 정복 알고리즘은 재귀적으로 문제를 해결부분 문제의 독립성나누어진 부분 문제는 서로 독립적으로 해결할 수 있음효율성문제를 분할해 해결하므로 효율적인 시간 복잡도를 가질 가능성이 높음장점과 단점장점효율적문제의 크기를 줄여 효율적인 시간 복잡도를 가질 수 ..

백트래킹이란?백트래킹은 가능한 모든 경우의 수를 체계적으로 탐색하여 정답을 찾는 기법주로 재귀(Recursion)를 이용하며, 유망하지 않은 경우(해가 될 가능성이 없는 경우)를 빠르게 포기(Prune)하여 효율성을 높임주요 특징완전탐색 기반: 가능한 모든 해를 고려가지치기(Pruning): 유망하지 않은 경로를 조기에 제거재귀적 접근: 작은 문제를 해결하면서 전체 문제를 해결백트래킹은 "상태 공간 트리(State Space Tree)"를 탐색하는 알고리즘으로 생각할 수 있습니다. 각 노드는 현재까지의 선택을 나타내며, 가지(branch)는 가능한 다음 선택을 나타냅니다.더보기상태 공간 트리(State Space Tree)란?상태 공간 트리(State Space Tree)는 탐색 문제를 해결하기 위해 모..

특징현재 시점에서 가장 최적인 선택을 반복하여 최종 해답에 도달하는 알고리즘각 단계의 선택이 문제 전체에 대해 최적임을 보장할 수 있는 문제에서 사용일반적으로 최적해를 보장하기 위해 그리디 선택 속성과 최적 부분 구조 조건을 만족해야 함최적 부분 구조문제를 작은 하위 문제로 나누고, 각 하위 문제의 최적해를 조합해 전체 문제의 최적해를 얻을 수 있는 경우 그리디 선택 속성 각 단계에서 최적의 선택을 해도, 결과적으로 전체 문제에 대해 최적해가 되는 경우적용 여부 판단 질문문제를 하위 문제로 나누고, 하위 문제의 최적해를 조합해 전체 문제의 최적해를 얻을 수 있는가?각 단계에서 지역적으로 최적 선택을 하면, 전체적으로도 최적해를 보장할 수 있는가?그리디 선택을 할 때, 이후 선택들에 영향을 미치지 않는가?..

동적 프로그래밍 (Dynamic Programming)개념 설명복잡한 문제를 작은 하위 문제들로 나누고, 결과를 저장하여 동일한 하위 문제를 반복 계산하지 않도록 하는 방법론특징최적 부분 구조 (Optimal Substructure) : 문제를 작은 문제로 나누고 이를 결합하여 전체 문제를 해결할 수 있음중복되는 하위 문제 (Overlapping Subproblems) : 동일한 하위 문제가 여러 번 반복적으로 계산됨메모리 사용 : 하위 문제 결과를 저장하기 위한 메모리 사용 (메모이제이션 또는 테뷸레이션)상향식(Bottom-Up) 또는 하향식(Top-Down) 접근 방식 사용장단점장점중복 계산을 방지해 시간 복잡도를 줄일 수 있음탐욕 알고리즘이나 분할 정복으로 해결할 수 없는 문제를 해결 가능단점메모리..

선형 탐색 (Linear Search)특징배열이나 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 탐색데이터가 정렬되지 않은 경우에도 사용 가능장점구현이 매우 간단하고 직관적임정렬 여부와 상관없이 사용할 수 있음단점탐색 시간이 오래 걸림(특히 데이터가 많을수록 비효율적)최악의 경우, 모든 요소를 탐색해야 함시간 복잡도BestO(1) (찾는 값이 첫 번째에 있는 경우)Average/WorstO(n)Java 코드 예시더보기public class LinearSearch { public static int linearSearch(int[] arr, int target) { for (int i = 0; i  이진 탐색 (Binary Search)특징정렬된 배열에서 중간값을 기준으로 탐색 범..

기본 정렬 알고리즘1. Bubble Sort특징인접한 두 요소를 비교하며 크기에 따라 교환모든 요소를 여러 번 반복적으로 정렬하기 때문에 단순하지만 비효율적임장점구현이 간단이미 정렬된 데이터에서는 효율적단점대규모 데이터에서는 매우 비효율적데이터가 많을수록 처리 시간이 급격히 증가합시간 복잡도BestO(n) (이미 정렬된 경우)Average/WorstO(n^2)코드 예시SudoCode더보기BubbleSort(array): for i from 0 to length(array) - 1: for j from 0 to length(array) - i - 1: if array[j] > array[j+1]: swap(array[j], array[j+1]..

트라이(Trie)란?문자열을 문자 단위로 트리에 저장하는 자료구조각 노드는 문자열의 한 문자를 저장루트 노드는 비어 있으며, 문자열의 공통 접두사는 동일한 경로를 공유트라이는 접두사 기반 검색, 자동완성, 문자열 사전 구현 등에 널리 사용트라이의 주요 특징빠른 문자열 검색검색 복잡도: O(L) (L은 문자열의 길이)공통 접두사 공유동일 접두사를 가지는 문자열은 트리의 동일 경로를 공유공간 효율성중복된 문자열 저장을 줄여 공간 절약 가능(특히 공통 접두사가 많은 경우)주요 연산(1) 삽입 (Insert)문자열의 각 문자를 따라가며 노드를 생성하고, 문자열의 끝을 표시(2) 검색 (Search)루트에서 시작하여 문자열의 각 문자를 따라가며 탐색합니다. 문자열 끝에 도달하면 해당 문자열이 존재함을 확인할 수 ..

우선순위 큐(Priority Queue)란?각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조큐(Queue)가 선입선출(FIFO) 원칙을 따르는 반면, 우선순위 큐는 우선순위에 따라 요소의 처리 순서가 결정특징우선순위가 높은 요소가 먼저 처리됨동일한 우선순위를 가진 요소는 일반적으로 선입선출사용 사례작업 스케줄링다익스트라 알고리즘허프만 코딩예시 코드기본 우선순위 큐 구현import java.util.PriorityQueue;public class Main { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); // 요소 추가 pq.offer..