IT LAB

조성호 님의 "쉽게 배우는 운영체제" 책을 정리한 포스팅 입니다 1. 개요프로그램 vs 프로세스구분프로그램프로세스정의어떤 데이터를 사용하여 어떤 작업을 할지 절차를 적어놓은 것작업이 진행되고 있는 프로그램상태정적인 상태 (저장장치에 저장됨) 동적인 상태 (메모리에 올라와 실행 중)저장 위치디스크(SSD, HDD) 등에 저장됨RAM(메모리)에 적재되어 실행됨실행 여부실행되지 않음실행 중인 상태예시myapp.exe (실행 파일)myapp.exe가 실행되어 프로세스 ID를 가지고 동작하는 상태 프로세스로의 전환프로그램을 메모리에 로드PCB 생성구분설명정의프로세스를 관리하기 위한 핵심 데이터 구조주요 정보- PID (Process ID): 프로세스의 고유 식별자 - Process state: 현재 상태 (실행,..

1. Prefix Sum0~i까지 구간의 합 2. Suffix Sumn~i까지 구간의 합 3. Target SubtotalKadane's Algorithm최대 부분 배열 합을 효율적으로 찾기 위한 알고리즘 동적 프로그래밍i번째 까지 원소의 최대 배열 부분 합을 관리dp[i-1] + 현재 방문한 원소 or 현재 방문한 원소 대소 비교를 통해 dp[i]를 갱신해감 시간복잡도O(n)최대값을 선형으로 찾을 수 있음  출처Wiki - Prefix SumWiki - Maximum subarray problem

1. Edit Distance두 문자열 간의 최소 편집 거리를 계산하는 문제입니다.한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 연산의 수를 의미합니다. 연산삽입: 문자 삽입삭제: 문자 삭제교체: 한 문자를 다른 문자로 교체DP 테이블 정의dp[i][j]i~j까지 최소 편집 연산 수 점화식A[i-1]  == B[j-1]dp[i][j] = dp[i-1][j-1]문자가 같으므로 편집 필요 없음 A[i-1]  != B[j-1]삽입, 삭제, 교체 중, 최소값을 선택삽입A에 문자를 삽입하여 B와 같아지게 함 dp[i][j-1] + 1삭제A에 문자를 삭제하여 B와 같아지게 함 dp[i-1][j] + 1교체A의 문자를 다른 문자로 교체하여 B와 같아지게 함dp[i-1][j-1] + 1  출처Wiki -..

1. Longest Palindrome Substring (LPS)주어진 문자열의 부분문자열에서 가장 큰 팰린드롬 문자열의 길이 구하기 Dynamic Programming시간 복잡도: O(n^2)공간 복잡도: O(n^2)더보기public static void main(String... args) throws IOException { br = new BufferedReader(new InputStreamReader(System.in)); bw = new BufferedWriter(new OutputStreamWriter(System.out)); input = br.readLine().toCharArray(); size = input.length; isPalindrome = new..

3. 모듈러컴퓨팅에서 한 숫자를 다른 숫자로 나눈 후, 나머지를 반환한 값 a mod n(유클리드 나눗셈의) 나머지a: 피제수n: 제수a mod b = a - b * (a/b) 성질덧셈 법칙뺄셈 법칙곱셈 법칙분배 법칙 응용큰 수 연산암호학해시 함수: 데이터를 고정된 크기의 값으로 매핑할 떄 사용됨주기성 확인: 반복되는 패턴을 찾는 데 사용됨 고급페르마의 소정리소수로 모듈러 연산하였을 때 결과를 구하는 공식소수 p와 p에 나누어 떨어지지 않는 정수 a가 있을 때a^(p) = a (mod p)a^(p-1) = 1  (mod p)a^(p-2) = 1/a  (mod p)a^(p-2)는 a의 모듈러 역원a * a^(p-2) = 1 (mod p) 이므로 a^-1 (mod p) = a^(p-2) (mod p) 확장 ..

1. 약수어떤 수를 나누어 떨어지게 하는 수 입니다.약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다. 2. 소인수주어진 자연수를 나누어 떨어뜨리는 약수중에서 소수인 약수​ 소인수분해합성수를 소인수들만의 곱으로 나타내는 것\[n = p_1^{a_1} \,\cdot\, p_2^{a_2} \,\cdot\, \cdots \,\cdot\, p_k^{a_k}\] 약수의 합n의 모든 양의 약수를 더한 값✅ 소인수분해 형태로 표현\[1 + p + p^2 + \cdots + p^a = \frac{p^{a+1} - 1}{p - 1}\]\[\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{\,a_i + 1} - 1}{p_i - 1}\] 3. 최대공약수 (GCD)두 개 이상의 정수의 공통된 약수 중에서..

1. Floyd-Warshall모든 정점 쌍 간의 최단 경로를 찾는 알고리즘 입니다. 가중치가 양수 혹은 음수인 그래프에서 사용됩니다. (단, 음의 사이클에는 사용 불가) Dynamic Programming인접행렬을 사용하여 각 정점 쌍 간의 최단 거리를 반복적으로 갱신합니다. 2. 동작 원리모든 정점을 경유지로 설정하고, 최단 경로가 경유지를 거쳐 더 짧아질 수 있는지 확인하며 최단 경로 갱신 초기화모든 정점 쌍에 대해, 직접 연결된 경로의 거리 초기화자기 자신으로 가는 경로 = 0연결되지 않은 경로 = infinit 경유지 검사i->j 로 가는 최단 경로가 i -> k -> j로 가는 경로를 통해 더 짧아질 수 있는지 검사 (정점 k를 경유지로 설정)모든 정점에 대하여 반복 3. 구현int[][] d..

1. Activity Selection Problem (활동 선택 문제)한 사람이 참여할 수 있는 최대 활동 수를 구하는 문제입니다.한 사람이 동시에 두 가지 활동을 참여할 수 없습니다. 해결 방법가장 먼저 끝나는 활동부터 선택합니다. 탐욕적 선택 속성현재 선택이 다음 선택의 기준에 영향을 미치지 않습니다.선택할 수 있는 가능 시간을 최대화하여, 남은 활동들을 선택할 수 있는 여지를 최대화합니다. 최적 부분 구조먼저 끝나는 활동을 선택하고, 남은 시간에 대해서도 동일한 방식을 적용할 수 있습니다.

1. Sliding Window선형 자료구조에서 특정 크기의 연속된 구간을 찾는 알고리즘 입니다.일정한 크기의 구간을 움직여 찾습니다. 동작 원리윈도우 설정: 초기 윈도우 구간을 설정함윈도우 이동: 한 번에 한 요소씩 이동시킴 (왼쪽 끝 제거 + 오른쪽으로 이동)조건 확인: 각 윈도우가 특정 조건을 만족하는지 확인 최대 구간 합) 고정 크기 더보기public int maxSumK(int k) { int sum = 0; for (int i = 0; i 최대 구간 합) 가변 크기 + 부분 합 제한더보기public int longestLenSumLt(int S) { int n = arr.length; int l = 0, sum = 0, ans = 0; for (int r = 0; ..

1. Redis Cluster 101수평 확장 및 복제를 위한 공식 구조항목설명Auto Sharding데이터가 여러 노드에 자동 분산 저장됨 (수동 분할 불필요)Partial Failure Tolerance일부 노드에 장애가 생기거나 통신이 끊겨도 클러스터는 일정 수준의 작동을 유지함전체 장애 시 중단마스터 노드의 과반수가 다운되면 → 전체 클러스터가 중단됨→ 클러스터는 최소 다수의 마스터가 살아있어야 운영 가능 TCP ports포트 종류설명클라이언트 포트- 일반 Redis 명령 처리용 포트 (예: 6379)- 클라이언트가 명령을 보내는 포트- 클러스터 간 키 마이그레이션 시에도 사용됨클러스터 버스 포트- 노드 간 내부 통신 전용 포트- 기본값: 클라이언트 포트 + 10000 (예: 16379)- 바이너..