1. 왜 이걸 알아야 할까?백엔드 서버, 컨테이너, 마이크로서비스를 운영할 때 시스템이 느려지는 원인을 파악하려면 CPU가 어떻게 태스크를 선택해서 실행하는지 알아야한다.top, htop, pidstat, pref 등 시스템 모니터링 도구에서 나오는 load average, context switch, CPU 사용률은 결국 스케줄링 알고리즘의 결정 결과값이다.멀티스레딩, 병렬처리, 비동기 서버 개발 시 스케줄링 정책의 특성을 모르면 CPU 낭비, starvation, 성능 저하 발생이 이어진다.📌 즉, CPU 알고리즘은 성능 디버깅, 병렬 시스템 설계, 실시간 서비스 운영을 위해 꼭 알아야 한다.2. 어떤 알고리즘이 있고, 리눅스에는 어떤걸 쓸까?이해의 출발을 위해 고전 알고리즘을 알아보자알고리즘특징F..

개념DFS(Depth-First Search,깊이 우선 탐색) 는 그래프나 트리와 같은 자료구조에서 탐색을 진행할 떄 사용하는 대표적인 알고리즘입니다.특정 노드를 시작점으로 잡고 최대한 깊은 경로까지 탐색하다가, 더 이상 탐색할 곳이 없으면 백트래킹을 통해 돌아오며 탐색하지 않은 경로를 다시 탐색합니다.즉, 깊게 먼저 들어가며 탐색하는 방식입니다.DFS의 핵심 원리하나의 노드를 선택해 방문한 후, 인접한 노드를 따라 갈 수 있는 곳까지 깊이 들어갑니다.더 이상 이동할 곳이 없으면 이전 노드로 돌아와서 다시 탐색을 시작합니다.방문한 곳을 기록해, 이미 방문한 노드는 재탐색하지 않습니다.즉, “한쪽 방향 끝까지 먼저 파고든다”라는 생각하면 직관적으로 이해할 수 있습니다.DFS 탐색 순서 예시 1 (..

개념창문을 한칸 씩 이동해서 문제가 요구하는 조건을 체크하는 것입니다.가이드 순서는 아래와 같습니다.윈도우에 담을 기존 원소(데이터)를 확인합니다.윈도우의 left, right 포인터를 0부터 시작합니다.left는 윈도우의 왼쪽 끝, right는 왼도우의 오른쪽 끝을 나타냅니다.조건에 따라 시작 지점은 변경합니다.right를 하나씩 증가시키면서 배열을 순회합니다.right가 증가할 때마다 기존 데이터를 기반으로 새로운 원소(데이터)를 반영합니다.윈도우에 추가된 원소를 문제의 조건에 맞춰 처리합니다.left ~ right를 순회해서 처리합니다.예 빈도수 계산, 함계 계산, 최댓값/최솟값 업데이트 등문제의 조건을 벗어나면(right 로직 마지막) 조건을 만족할 때까지 left 포인터를 오른쪽으로 이동시킵니다..

알고리즘을 처음 공부할 때, 많은 사람들이 어려워하는 개념이 바로 "동적계획법(DP)"입니다. 이 글에서는 DP를 어떻게 접근하고, 어떤 기준으로 적용할지 명확히 이해할 수 있도록 안내하겠습니다. 📌 동적계획법(DP)이 어려운 이유DP는 문제를 작은 문제로 나누고, 그 결과를 활용하여 큰 문제를 해결하는 방식입니다. 하지만 처음부터 DP가 적용된다는 것을 떠올리기 쉽지 않죠. 문제를 보면 막막하게 느껴지기 때문입니다.📌 DP를 명확히 적용하는 3가지 기준다음의 기준을 보고 DP 적용 여부를 쉽게 판단해보세요.반복되는 부분 문제가 있는가?배수, 비율 등 간단한 규칙으로 최적이 가능한가? (그리디로 해결 가능)작은 문제의 해답을 큰 문제에서 활용할 수 있는가? (점화식 판단)이 기준을 충족하면 DP로 접..

알고리즘을 성능 최적화하기 위해서는 수학적으로 증명된 기능을 사용하는 것이다.아래는 증명된 수식을 어떻게 로직을 구현하는지 정리한 내용이다.계속 추가될 예정이다.소수점 올림(ceil)ceil(X/Y) -> (X + Y - 1) / Yex)ceil(60/30) -> (60 + 30 -1) / 30 = 89 / 30 = 2소수점 내림(floor)나누기 자체가 내림 수foor(X/Y) -> X / Yex)floor(69/30) -> 69 / 30 = 2소수점 반올림(round)나누려고 하는 값의 절반을 올려줌으로 0.5 이상이면 반올림 효과 발생round(X/Y) -> (X + Y/2) / Yex)round(7/2) -> (7 + 2/2) / 2 = 8 / 2 = 4round(7/3) -> (7 + 3/2)..

DBMS나 트랜잭션 시스템이 아닌 동시성 제어의 개념적인 패러다임에서 출발한 이론 다중 사용자/프로세스가 동일자원(DB row 등)을 동시에 읽고 쓰는 상황에서의 충돌을 방지하기 위해 등장해당 문제는 1970 ~ 1980년대 DBMS/OS 이론에서 활발히 논의됨비관적 락고전적인 RDBMS의 트랜잭션 동시성 제어 이론에서 등장했고 대표 기술로 2-Phase Locking(2PL)으로 트랜잭션이 자원을 모두 락으로 확보한 후 커밋합니다. 이 방식은 직렬화를 보장합니다.기본 아이디어는 “다른 놈이 반드시 충돌할 거야” → 그래서 미리 락을 걸고 진입을 통제합니다.적용방식으로 공유 자원(예: DB row)에 접근 전에 락을 선점합니다. 다른 트랜잭션은 대기하거나 실패합니다.주의 사항 & 병목 및 데드락 유..

링크: https://www.acmicpc.net/problem/1874문제스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을..

문제링크: https://www.acmicpc.net/problem/10816문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분..

컴퓨터 프로그래밍에서 숫자를 입력받는 것은 흔히 있는 일이지만, 그 내부의 원리를 정확히 이해하고 있는 사람은 많지 않습니다. 이번 글에서는 숫자 입력을 처리할 때 흔히 사용하는 공식인 n = n * 10 + (c - '0')의 원리와 수학적 의미를 상세히 다뤄보겠습니다.✅ 왜 이 주제를 다루는가?처음 이 공식을 접하면 직관적으로 이해하기 어렵습니다.저 또한 처음에는 “왜 갑자기 *10을 곱하지?“라는 의문을 가졌습니다.이 글은 저와 같은 고민을 한 분들에게 직관적인 이해와 명확한 설명을 제공하기 위해 작성되었습니다.✅ 기본 공식 (n = n * 10 + (c - '0')) 설명하기이 공식은 문자열로 입력받은 숫자를 정수형으로 변환할 때 사용되는 표준 알고리즘입니다.예시로 숫자 “371”을 살펴봅시다.읽..

핵심 개념Quicksort는 pivot 1개를 사용해 배열을 두 부분으로 나누지만, Dual-Pivot Quicksort는 pivot 2개를 사용해 배열을 세 부분으로 나눕니다.각 구간을 재귀적으로 정렬하는 고성능 분할 정복 기반 정렬 알고리즘입니다.Arrays.sort()에 사용되고 있습니다.분할 방식(Pivot 2개 → 3 구간)pivot1 배열을 다음 3개의 부분으로 나눔:arr[i] pivot1 ≤ arr[i] ≤ pivot2arr[i] > pivot2이 3개 구간을 각각 재귀적으로 정렬동작 절차 구현아래 소스는 이해를 위해 만든 로직입니다. Arrays.sort()와는 접근 방식이 다릅니다.결과값은 같습니다.void dualPivotSort(int[] arr, int left, int right..