9. 프로세스 구조와 프로세스간 커뮤니케이션
프로세스 구조프로세스 구조는 4가지 영역으로 나뉜다. 스택 : 최상단 스택 주소를 가리키는 EBP, 함수 결과를 반환해줄 주소(return address), 함수와 관련된 인자나 변수를 저장하는 영역 힙 : 동적으로 할당된 메모리를 저장하는 영역. (ex. malloc) 이 영역의 메모리 주소를 통해 힙에 저장된 내용을 다른 영역에서 사용! 데이터 : 선
Home
13. 다이나믹 프로그래밍-3(LCS 문제)
LCS(최장공통부문자열) 문제부문자열은 문자열에서 0개 이상의 문자를 제외하고 남은 문자열을 의미YANG에서 A를 제외한 YNG같이… 하지만 AGY는 안된다! 공통 문자열은 두개의 문자열의 부문자열이 동일한 것을 말한다!이 문제는 가장 긴 길이의 공통부문자열을 찾는 문제이다! Xn 을 x1, x2, x3, … xn 즉 n개의 글자를 갖는 문자열이라고 하고,
8. 선점형 스케쥴러와 인터럽트
선점형 스케쥴러하나의 프로세스가 다른 프로세스 대신에 프로세서(cpu)를 차지할 수 있다!어떤 프로세스가 running 중에 스케쥴러가 이를 중단시키고, 다른 프로세스로 교체가능! 비선점형 스케쥴러하나의 프로세스가 끝나지 않으면 다른 프로세스는 cpu 사용할 수 없음…자발적으로 wait으로 되거나, 혹은 실행이 끝났을 때만 다른 프로세스로 교체 가능!즉 c
12. 다이나믹 프로그래밍-2(행렬 곱셈 문제)
행렬 곱셈 문제 n개의 행렬 곱셈을 최소 비용으로 푸는 문제 만약 무지성으로 pXq , qXr 인 두 행렬을 3개 for루프로 풀면, O(pqr)번 연산이 필요하다.이때 여러개의 행렬이 주어졌을 때는, 행렬을 어느 순서로 곱하느냐에 따라 기본 연산 횟수가 달라진다.a = 1x2, b=2x3, c=3x4 일때, (ab)c와 a(b
11. 다이나믹 프로그래밍-1
다이나믹 프로그래밍문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법. divde and conquer와 차이점은? 큰 문제의 답이 작은 문제의 답들의 식으로 표현되지만,그 답을 얻을 때 재귀적으로 얻는게 아니라 미리 계산하여 기록해 놓은 값을 재귀 식에 따라 계산! 즉 원래 문제의 답을 작은 문제들의 재귀 식으로 표현하는 것이 핵심!!!!점화
10. Merge 정렬 알고리즘
Merge 정렬 알고리즘퀵 소트가 피벗을 어떻게 선택하냐에 따라 속도가 달라지는 단점을 상쇄하는 알고리즘 배열은 반으로 나눠 재귀적으로 정렬하고 정렬된 두 배열을 원소 하나씩 비교해서 병합하는 방식.주어진 배열만큼 새로운 배열을 사용해야 하기 때문에 not in-place 알고리즘이다. 먼저 중간 인덱스를 찾는다. 중간 인덱스를 기준으로 나눠서 두 배
7. 프로세스 상태와 스케줄러 알고리즘의 관계
멀티 프로그래밍과 waitwait : 프로세스가 실행 중임에도 불구하고 cpu를 사용하지 않고 기다리는 시간멀티 프로그래밍은 wait 때문에 발생하는 비효율을 줄이는 스케쥴링 알고리즘!그렇다면 이렇게 효율적으로 하기 위해서는 어떻게 해야할까?어떤 시점에 어떤 프로세스를 실행시켜야 될지 판단해야 하는데.. 이때 중요한게 프로세스 상태다!프로세스 상태 run
9. Quick 정렬 알고리즘
퀵 정렬 알고리즘이론적으로는 빠르지 않지만(O(n^2)), 실제로는 가장 빠른 정렬 알고리즘quick selection과 비슷한 원리임. not in-place quick sort algorithm 어떤 list A를 퀵 정렬 하려면… 피벗을 A[0]으로 잡고, S,M,L 세가지 배열을 선언함 A에 있는 모든 수들이 피벗보다 크면 L, 작으면 S, 같으
8. 기본 정렬 알고리즘
파이썬에서 제공하는 정렬 123A = [3,1,2,-5]A.sort() #[-5,1,2,3]A.sort(reverse = True) #[3,2,1,-5] 정렬 알고리즘의 두 가지 특성 stable vs unstable만약 [2,5,2,7]을 오름차 정렬했을 때 ,[2,2,5,7]로 정렬이 될 텐데, 이 두 개의 2가 입력 순으로 정렬되면 stable하
10. 최단경로 알고리즘(벨만포트, 다익스트라)
최단 경로 알고리즘아주 중요한 그래프 문제.엣지에 가중치가 부여된 상황에서 특정 노드에서 다른 노드로 가는 최적의 경로를 찾는 문제. 특징 노드 s에서 v까지 최단 경로 중 엣지(u, v)가 포함되면, 이 경로에서 s부터 u까지 부분도 역시 최단 경로다.M(v)를 s에서 v까지 최단 경로라고 길이라고 하면,M(V) = M(u)+min(u,v)