보이어-무어(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 어셈블리 언어와 친해지는 첫 걸음어셈블리 언어와 친해지는 첫 걸음우리는 이미 자바, 파이썬 등 편리하고 생산적인 고급 언어를 사용해 프로그램을 개발하고 있습니다. 그렇다면, 도대체 저 먼 옛날에..

그리디 알고리즘(Greedy Algorithm)그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 반복하여 최종 해를 구하는 알고리즘입니다.  그리디 알고리즘의 특징그리디 알고리즘이 정확한 최적해를 보장하기 위해서는 다음 두 조건을 만족해야 합니다.Greedy Choice Property (탐욕 선택 속성)전체 문제의 최적해는 부분 문제의 최적해로 구성되어야 한다.즉, 지금 당장의 최선의 선택이 결국 전체에서도 최선의 선택이어야 한다.예) 활동 선택 문제 (Activity Selection)Optimal Substructure (최적 부분 구조)문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있어야 한다.즉, 문제를 작은 부분으로 나누었을 때, 이들 각각의 최적해를 합치면 전체 문제의 최적해가..

Knapsack Problem(배낭 문제)Knapsack Problem은 제한된 무게를 가진 배낭에 물건들을 넣을 때, 가치를 최대로 하기 위해 어떤 물건들을 선택해야 하는지에 대한 조합을 찾는 최적화 문제입니다. 이 문제에서는 각 물건마다 무게(weight)와 가치(value)를 지니고 있는데, 배낭이 버틸 수 있는 최대 무게(W)를 초과하지 않으면서 선택한 물건들의 가치 총합이 최대가 되어야 합니다.  Knapsack Problem의 유형0/1 Knapsack Problem각 물건을 한 번씩만 선택할 수 있다.선택하거나 하지 않거나(0또는 1)의 선택지만 존재한다.Fractional Knapsack Problem한 물건을 일부만 쪼개서 담을 수 있다.그리디 알고리즘으로 해결이 가능하다Unbounded..

LCS(Longest common subsequence, 최장 공통 부분 수열)LCS는 두 수열이 주어졌을 때, 순서를 유지하면서 공통적으로 나타나는 가장 긴 부분 수열을 찾는 문제입니다. 보통 문자열 비교에서 많이 활용됩니다. 가장 큰 특징은 부분 수열이기 때문에 연속해서 등장할 필요가 없고, 중간에 다른 값이 있더라도 순서만 맞는다면 공통 수열로 인정된다는 점입니다.  LCS 길이 구하기LCS는 DP(동적 계획법)으로 해결할 수 있는 대표적인 문제인데요. 아래와 같은 점화식을 세워 해결합니다.점화식두 문자열 A[1..i], B[1..j]의 LCS 길이를 dp[i][j] 라고 하면,if A[i] == B[j]: dp[i][j] = dp[i-1][j-1] + 1else: dp[i][j] = m..