기록공간

CPU를 가상화하기 위해서 운영체제는 여러 작업들이 동시에 실행되는 것처럼 보이도록 물리적인 CPU를 공유한다. 한 프로세스를 잠시 동안 실행하고 다른 프로세스를 또 잠깐 실행하고, 이런 식으로 계속해서 잠깐씩 실행시키면 된다. 이렇게 CPU 시간을 나누어 씀으로써 가상화를 구현할 수 있다. 그러나 이러한 가상화 기법을 구현하기 위해서는 몇 가지 문제를 해결해야 한다. 첫 번째는 성능저하이다. 시스템에 큰 오버헤드를 주지 않으면서 가상화를 구현할 수 있을 것인가? 두 번째는 제어 문제이다. CPU에 대한 통제를 유지하면서 프로세스를 효율적으로 실행시킬 수 있는 방법은 무엇인가? 운영체제의 입장에서는 자원 관리의 책임자로서 특히 제어 문제가 중요하다. 제어권을 상실하면 한 프로세스가 영원히 실행을 계속할 ..

한 시스템에 CPU와 GPU가 병렬로 실행되다 보니 동기화 문제가 발생한다. 예를 들어 그리고자 하는 어떤 기하구조의 위치를 R이라는 자원에 담는다고 하자. 그 기하구조를 위치 p1에 그리려는 목적으로 CPU는 위치 p1을 R에 추가하고, R을 참조하는 그리기 명령 C를 명령 대기열에 추가한다. 명령 대기열에 명령을 추가하는 연산은 CPU의 실행을 차단하지 않으므로, CPU는 계속해서 다음 단계로 넘어간다. 만약 GPU가 그리기 명령 C를 실행하기 전에 CPU가 새 위치 p2를 R에 추가해서 R에 있던 기존 p1을 덮어쓰면, 기하구조는 의도했던 위치에 그려지지 않게 된다. 이런 문제의 해결책은 GPU가 명령 대기열의 명령들 중 특정 지점까지의 모든 명령을 다 처리할 때까지 CPU를 기다리게 하는 것이다...

동적계획법(Dynamic Programming)을 사용하여 가장 긴 최장증가수열(LIS)을 구하는 문제이다. 동적계획법 : https://lipcoder.tistory.com/49 동적계획법(Dynamic Programming) 동적계획법 이란? 동적계획법(다이나믹 프로그래밍)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘 방법이다. 다이나믹 프로그래밍이란 명칭은 그냥 알고리즘 창조한 사람이 단지 이름이 멋지다는 이유로 붙여진.. lipcoder.tistory.com 최장증가수열 : https://lipcoder.tistory.com/50 최장증가수열 - LIS(Longest Increasing Subsequence) LIS(최장증가수열)는 동적계획법으로 풀 수 있는 알고리즘 문제 중 하나이다. 어떤 임..

행렬의 행(N)이나 열(M)의 크기가 하나라도 3보다 작은 경우에는 원소 뒤집기 작업(XOR)이 불가능하기 때문에 A와 B가 서로 같은지만 확인하면 된다. 만약 둘 다 3보다 큰 경우 1행부터 N - 3행까지 그리고 1열부터 M - 3열까지 A와 B가 특정위치에서 서로 같은지를 검사하며 다른 경우 그 위치에서부터 XOR를 진행한다. 모두 끝난 후에 행렬 A와 B가 같은지 확인하면 끝이 난다. 코드는 다음과 같다. #include #include #include using namespace std; void XOR(char** mat, int N, int M) { for (int i = N; i < N + 3; ++i) { for (int j = M; j < M + 3; ++j) { char temp = ..

K개의 부등호가 있을때 각각 최대값, 최소값이 되기 위해서는, 최대값은 9부터 9 - k까지, 그리고 최소값은 0부터 0 + k까지 차례대로 가지고 와야한다. 그리고 가지고 온 숫자들의 수열을 이용하여 입력한 부등호가 만족할때 까지 검사하면 각각 부등호에 맞는 최대값, 최소값이 나온다. 최대값은 현재 수열의 이전 수열을, 최소값은 현재 수열의 다음 수열을 차례대로 가져오며 검사를 진행해야 한다. 코드는 다음과 같다. #include #include #include using namespace std; bool check(char* num, char* symbol, int size) { for (int i = 0; i ': if ..

LIS(최장증가수열)는 동적계획법으로 풀 수 있는 알고리즘 문제 중 하나이다. 어떤 임의의 수열이 주어졌을때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장증가수열이라고 한다. 예를 들어 다음 수열이 주어졌다고 하자. 3 5 7 9 2 1 4 8 위 수열에서 몇 개의 수를 제거해 부분 수열을 만들었다고 하자. 3 7 9 1 4 8 (5, 2 제거) 7 9 1 8 (3, 5, 2, 4 제거) 3 5 7 8 (9, 2, 1, 4 제거) 1 4 8 (3, 5, 7, 9, 2 제거) 이들 중 세번째와 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다. 그리고 세번째와 같이 이러한 수열 중 가장 긴..

동적계획법 이란? 동적계획법(다이나믹 프로그래밍)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘 방법이다. 다이나믹 프로그래밍이란 명칭은 그냥 알고리즘 창조한 사람이 단지 이름이 멋지다는 이유로 붙여진 것이다(...). 분할정복(Divide and Conquer)과 다른 점 거의 비슷하지만 결정적인 차이점이 존재한다. 그것은 바로 나눠진 작은 문제에서 중복이 일어나는가 안일어나는가이다. 분할정복은 큰 문제를 해결하기 위해 그냥 작은 문제로 나누어 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 동적계획법은 작은 문제들이 반복되는것(단, 바뀌지 않음)을 이용해 풀어나가는 방법이다. 동적계획법의 방법 모든 작은 문제들은 꼭 한번만 풀어야 한다. 그러므로 작은 문제의 정답은 어딘가..

큐란? 큐(Queue)는 사전적인 정의로 '긴 열', '대기열'를 뜻한다. 길게 늘어져 있는 줄을 생각하면 편하다. 큐(Queue)는 일상생활에서도 자주 접하게 된다. 예를 들면 극장에서 표를 사려고 길게 늘어진 사람들의 줄, 또는 도로 위에서 신호를 기다리며 길게 늘어선 차들 등이 있다. 이러한 대기열에는 한 가지 중요한 특징을 가지고 있다. 그것은 바로 '선입선출(First-In First-Out : FIFO)'이다. 새치기라는 예외적인 상황을 제외하고 정상적인 경우라면 언제나 먼저 도착한 사람이 먼저 나가게된다. 자료구조에 사용되는 큐는 이러한 줄 서기의 특징을 그대로 가지고 있다. 큐는 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조이다. 먼저 저장된 데이터가 나중..