Little Jay

Memory Hierarchy 메모리는 CPU의 작업공간이다. Processor가 성능을 최대한으로 내려면 Memory의 속도 역시 중요하다. Memory는 장치의 특성에 따라 피라미드 형태로 계층구조를 그릴 수 있다. 위의 그림을 보면 레지스터, SRAM, DRAM, DISK, Secondary Memory의 순으로 피라미드 형태로 나눌 수 있는 모습을 볼 수 있다. 피라미드가 점점 내려가면서 가격적인 측면과 용량적인 측면에서 이득을 많이 볼 수 있지만, 반면 속도가 점점 내려가고 이에 따른 대역폭도 내려간다. 우리는 이러한 관계를 메모리 계층구조라고 부른다. 그러나 우리는 ideal하게 빠른 속도의 High Level Memory와 Low Level Memory의 가격과 용량을 얻고 싶다. 따라서 우..

간단했던 BFS 문제였는데 멍청하게 BFS 수행 조건을 잘못 줘서 30분동안 맞왜틀 하고 있던 문제였다. 특별한 로직은 따로 없었고 양의 수 > 늑대 수 일때만 양의 수를 업데이트 시키는 것만 잘 파악했다면 크게 거렵지는 않았다. #include #define endl '\n' using namespace std; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; char board[255][255]; bool visited[255][255]; int r, c; int wolves = 0, sheep = 0; void bfs(int x, int y) { queue q; q.push({ x, y }); visited[x][y] = tr..

Interrupt Mechanism Interrupt는 Processor Utilization은 높이는 기법이다. Interrupt 자체는 시스템 프로그래밍 파트에서도 설명을 했었는데 이제는 이 Interrupt가 어떻게 동작하는지 그 원리와 내부 구조, 이유에 대해 OS의 관점에서 정리하겠다. Interrupt를 사용하는 이유는 대부분의 I/O Device가 Processor보다 느리기 때문이다. 만약 Processor가 I/O Device와 바로 상호작용하기 위해서는 Processor는 Device의 작업이 끝날 때까지 기다려야 한다. 이는 Processor라는 자원을 놀리고 있는 것이고 이는 Resource에 대한 자원 낭비이다. 예를 들어서 Read Operation이 일어난다면 Processor..

좀 비효율적인 코드이긴한데 전체적인 로직에서 크게 다를점이 없다. 결과적으로 '-'가 언제 들어오는지가 관건이 된다. https://www.acmicpc.net/board/view/86898 여기에 반례가 정리되어 있는데 이 반례를 보면 결국 '-'가 한번 들어오고 '+'가 들어와도 괄호를 끝까지 쳐버리면 되고, '-'가 연속적으로 들어오게 된다면 그냥 괄호를 치지 않고 계속해서 빼기만 해주면 된다. 이 점만 좀 유의하면 한 번에 correct이 뜰 수 있었을텐데 아쉽다. 코드는 좀 지저분하고 비효율적이라 로직만 참고하시길 바란다. #include #define endl '\n' using namespace std; string s, num; int temp; int main() { ios::sync_w..

어느덧 마지막 파트에 다다랐다. Sys Level I/O를 다루기만 하면 시스템프로그래밍이라는 과목을 한번 다 돌아보게 되는 것이다. 이제는 UNIX I/O가 어떻게 작동하는지 알아보자. UNIX I/O Overview 파일은 Byte의 Sequence이다. 앞서서 배열, 구조체 등을 배울 때에도 잠깐 언급을 했었지만, 파일은 결국 Byte가 선형 배열로 놓여있는 것이다. 이를 Linear Array of Bytes라고 한다. 또한 모든 I/O Device는 파일로 편현이 된다. 예를 들어서 /dev/tty 라고 하면 터미널에 접근할 수 있게 된다. 그리고 각각의 파일은 시스템 내에서 수행하는 타입이 있다. Regular File : 임의의 데이터를 담고 있다. Directory:파일과 관련된 그룹의 I..

사실 내 힘으로 푼 문제는 아니다. 도저히 아이디어가 떠오르지 않아 다른 분들의 블로그를 참고했다. 식을 세우는데 어려움을 겪었는데 각 의상 종류별 + 1한 값의 곱에서 전체를 안입는 경우인 1을 빼주면 되는 식을 세우는 것이 결국 관건이었던 것 같다. 이거를 도출해낸다는게 쉽지 않았고 Silver 3문제였는데도 이 아이디어를 30분 넘게 고민하다가 안되서 결국 참고했다. #include #define endl '\n' using namespace std; int t, n; string name, cloth; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while (t--) { cin >> n; map mp; f..

처리해야하는 항목은 다음과 같다 문장의 맨 앞에 '_' 가 오는 경우 문장의 맨 뒤에 '_' 가 오는 경우 문장의 만 앞이 대문자인 경우 '__' 같이 언더스코어가 연속적으로 나오는 경우 대문자와 '_'가 복합적으로 나오는 경우 정도를 에러처리 해주면 나머지 구현은 쉽다. Python으로 풀면 더 간단할텐데 C++이라 코드도 길어지고 시간도 오래 걸렸다. toJava 함수에서 위험한 구간이 있는데 s[i + 1] == '_'인 경우를 체크해주는건데 메모리를 잘못 건드려서 seg fault가 날 수 있지 않을까를 생각해봤는데 그 경우의 수는 문장의 마지막에 '_'가 오는 경우이기 때문에 이미 체크를 해서 안전하게 넘어갈 수 있는 것 같다. #include #define endl '\n' using name..

이차원 배열을 사용해야하는 dp문제 #include #define endl '\n' using namespace std; int n, a, b; int minMul[501][501]; vector v; int matOrder(vector& v, int n) { for (int i = 1; i > a >> b; if (i == n - 1) { v.push_back(a); v.push_back(b); } else { v.push_back(a); } } cout

강연결요소는 DFS를 두번 실행해서 연결된 요소를 찾을 수 있다. stack에 방문한 순서가 아닌 finished 되는 순서로 넣어야하기 때문에 이 점을 주의해서 풀면 될 것이다. 정렬을 빡세게 수행했는데 이렇게까지는 안해도 될 것 같다. #include #include #include #include using namespace std; #define endl '\n' #define vvi vector #define vi vector #define vb vector int n, m; int follower[50001]; void first_dfs(int start, vb& visited, vvi& adj, stack& st) { visited[start] = true; for (auto next : a..

Termination Process는 세 가지 이유로 종료가 된다. 먼저 main 함수의 routine에 의해 자발적으로 종료가 되는 경우, exit함수로 자발적인 종료를 호출하는 경우, 마지막으로 종료를 수행하는 signal을 받을때이다. 다들 알고있겠지만 exit함수에 대한 간단한 소개를 하고 넘어가자면, exit함수는 말그대로 process를 terminate시킨다. 이 함수에는 번호가 들어가는데, 그 범위는 0~255까지 들어갈 수 있으며 0은 정상종료의 의미, 0이 아닌 경우에는 error상황이다. C의 stdlib.h 헤더파일에는 void atexit(void *(func) (void)); 가 들어가있다. 자세한 설명은 아래 링크의 블로그를 참조하면 되겠다. 이 함수는 exit할 때 다른 함수..