TIL(today i learned)
-
LCS(Longest Common Subsequence - 최장 공통 수열) 알고리즘TIL(today i learned) 2023. 7. 27. 14:28
Longest Common Subsequence 그리고 Longest Common Substring LCS에는 최장 공통부분수열(Longest Common Subsequence)과 최장 공통 문자열(Longest Common Substring)을 말한다. 문자열 ABCDEF와 GBCDFE를 이용하여 차이점을 예시로 들어보면 위 그림처럼 Subsequence은 연속적일 필요 없이 문자를 뛰어넘어도 되지만 Substring 같은 경우에는 문자가 아예 일치해야만 한다. 이를 토대로 각각 점화식을 만들어보면 다음과 같다. Substring if (A[i] == B[j]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = 0; Subsequence if (A[i] == B[j..
-
LIS(Longest Increasing Subsequence - 최장 증가 수열) 알고리즘TIL(today i learned) 2023. 7. 25. 17:02
해당 알고리즘은 배열중 가장 긴 증가수열을 찾는 알고리즘이다 예를 들어 1 4 2 5 3 2 라는 배열이 있다고 가정해 보자 1 2 3 4 5 2 {1,2,3}, {4,5}, {2}중에서 가장 긴 증가수열을 찾으면 {1,2,3}이다. 이러한 문제를 해결하고자 나온 것이 LIS(Longest Increasing Subsequence - 최장 증가수열) 알고리즘이다. 기본적으로 DP를 사용하면 N^2이 걸리고 이분탐색사용 시 NlogN의 시간이 걸린다. 예시 코드) for (int k = 0; k < n; k++){ length[k] = 1; for (int i = 0; i < k; i++){ if(arr[i] < arr[k]){ length[k] = max(length[k], length[i] + 1); ..
-
알면 도움되는 bitmaskTIL(today i learned)/알고리즘 2023. 7. 20. 21:15
https://www.acmicpc.net/problem/17497 17497번: 계산기 첫 번째 줄에 버튼을 누른 횟수 K (0 ≤ K ≤ 99) 를 출력합니다. 누른 횟수를 최소화 하지 않아도 됩니다. 단, 누른 횟수가 99번을 넘으면 안됩니다. 만약 99번 안에 N을 만드는 방법이 존재하지 않는 www.acmicpc.net 2진수 연산 특징 a)2를 곱하면 현재 비트뒤에 단순히 0이추가된다. b)현재비트의 맨뒤가 0이면 짝수,1이면 홀수 이다. c)(X & 1)연산은 홀수이면 1 짝수이면 0
-
Chapter 5: CPU SchedulingTIL(today i learned)/운영체제 2023. 4. 10. 13:13
다중프로래밍의 목적은 CPU의 사용률을 극한으로 끌어올리는 것이다. 프로세스의 실행은 I/O대기상태와 CPU실행을 왔다갔다 한다. CPU가 유휴상태가 될때마다 운영체제는 준비 큐에 있는 프로세스하나를 선택하고 실행하여야 되는데 이는CPU스케줄러에 의해 결정된다. CPU 스케줄링 결정이 발생하는경우 1.프로세스가 running에서 wait상태로 들어갈때 2.프로세스가 running에서 ready상태로 들어갈때 3.프로세스가 wait에서 ready상태로 들어갈때 4.프로세스가 종료할때 스케줄링방법에는 선점 스케줄링방법과 비선점 스케줄링 방법이 있는데 선전형 커널에는 공유 커널데이터 구조에 액세스 할 때 경쟁 조건을 방지하기위해mutex락 과 같은 기법이 필요하다. 디스패처는 스케줄링의 기능에 포함된다. 디스..