728x90 Algorithm Practice12 LZW(Lempel, Ziv, Welin) 압축 알고리즘 LZW 압축 알고리즘무손실 데이터 압축 알고리즘으로, 사전을 기반으로 하여 데이터의 반복 패턴을 효율적으로 인코딩한다.주로 이미지 포맷(GIF)나 파일 압축 유틸리티에서 사용한다. LZW 알고리즘의 핵심 개념1. 사전 기반 압축 - 데이터를 압축하기 위해 입력 데이터에서 패턴(문자열)을 찾아 사전에 저장한다. - 문자열을 직접 출력하지 않고 사전에 저장된 문자여르이 "인덱스"를 출력하여 데이터를 압축한다. 2. 적응형 사전 구축 - LZW는 입력 데이터에서 새롭게 발견되는 패턴을 사전에 추가한다. - 따라서 사전은 입력 데이터를 처리하는 동안 점점 확장된다. 3. 재귀적 표현 - 긴 문자열은 짧은 문자열의 조합으로 표현된다. 동작 원리1. 초기화 .. 2024. 12. 16. 페이지 교체 알고리즘(FIFO, LRU, LFU) 페이지 교체 알고리즘페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재(Page Fault)가 발생하여 새로운 페이지를 할당하기 위해현재 할당된 페이지 중 어느 것과 교체할지 결정하는 방법으로 페이지 교체는 제한된 크기의 물리적 메모리에 가상 메모리를 매핑하는 데 중요한 역할을 한다. 1. FIFO(First-In-First-Out)가장 오래 전에 메모리에 들어온 페이지를 교체한다.큐(queue)를 사용하여 페이지를 관리하며, 가장 먼저 들어온 페이지가 가장 먼저 제거된다. 1. 동작 방식 : 새로운 페이지가 참조되고, 프레임(메모리 공간)이 가득 차 있는 경우 - 큐의 가장 앞에 있는 페이지(가장 오래된 페이지)를 제거 -.. 2024. 12. 6. 슬라이딩 윈도우(Sliding Window) 알고리즘 1. 슬라이딩 윈도우란 배열, 문자열 또는 리스트와 같은 선형 데이터 구조에서 특정 범위나 구간을 효율적으로 처리하기 위한 기법으로,이 알고리즘은 고정된 크기의 범위를 유지하거나 가변적인 범위를 움직이며 데이터를 처리한다. 부분 배열을 어떠 조건하에서 계산하는 경우, 구간 합 구하기, 부분 문자열 구하기 등에 활용하며, 불필요한 계산을 줄이고 효율적으로 해결할 수 있게 해준다. 1. 윈도우 연속된 데이터의 부분집합으로, 일반적으로 배열의 인덱스나 문자열의 일부로 표현된다. 2. 윈도우의 크기 고정 크기 : 윈도우의 크기가 일정.가변 크기 : 윈도우의 크기가 문제의 조건에 따라 변함 3. 슬라이딩 윈도우의 시작 또는 끝을 한 칸씩 이동하며 데이터를 처리하고,이전 윈도우에서 계산한 결과를 활용해 중복 계산을.. 2024. 12. 2. 투 포인터(Two Pointers)알고리즘 투 포인터(Two Pointers)알고리즘1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 원하는 값을 찾을 때 까지 탐색하는 알고리즘배열의 양끝에서 시작하는 두 포인터를 점진적으로 이동시켜 문제를 해결하는 방식 시간복잡도는 O(n) 과정 1. 두개의 포인터를 사용해 하나는 배열의 왼쪽 끝(Start)에서 시작하고, 다른 하나는 배열의 오른쪽 끝(End)에서 시작한다.2. 두 포인터를 상황에 맞게 점진적으로 이동하여 문제를 해결3. 배열을 여러 번 반복하지 않고, 한 번의 반복으로 문제를 해결한다. 투 포인터 알고리즘은 주로 정렬된 배열인두 수의 합, 부분합, 가장 긴 부분 문자열 찾기에 사용된다. 코드 구현 예제주어진 정렬된 배열에서, 두 수를 더했을 때 특정한 값이 되는 인덱스.. 2024. 10. 24. 이전 1 2 3 다음 728x90
