문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은..

1. 문제 크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 > r >> c >> k; for (int i = 0;i > arr[i][j]; } } while (1) { if (arr[r-1][c-1] == k) { break; } if (total > 100){ break; } if (r_cnt >= c_cnt) { row_cal(); } else { col_cal(); } total++; } if..

fsync 연산은 데이터와 데이터를 가리키는 direct node만을 쓴다. 따라서 fsync만으로는 데이터의 consistency를 보장할 수 없다. NAND 상에서 node write가 먼저 일어나고 data write이 일어나는 도중에 crash가 일어나는 상황을 가정해보자. 이 때 데이터의 consistency는 무너지게 된다. 이를 해결하기 위한 방법은 두가지가 있다. 1. roll forward recovery 2. fsync with strict mode 먼저 roll forward recovery를 보자. f2fs 파일 시스템은 시스템 크래쉬가 일어났을 때 roll-back recovery를 진행한 후에 roll-forward recovery를 진행한다. 롤백 리커버리는 체크포인트 팩을 보..

나는 연구할 때 항상 vim 을 쓴다. 그래서 clion, visual studio 와 같은 ide에는 익숙하지 않은데, 알고리즘 풀이를 할 때는 ide를 사용하는게 더 낫다고 생각한다. visual studio 가 가장 좋은 ide겠지만 맥에서 c++이 돌아가지 않으니까 visual studio code를 사용하고자 한다. visual studio code에서의 환경 구축은 다음과 같이 하면 된다. 1. Extension pack에서 c/c++ 설치한다 설치한 후에는 다시 reload를 해야한다 2. code runner를 설치한다 설치하고 enable 시키고 reload를 한다. 그러면 이제 setting을 눌렀을 때 code runner가 보이게 된다 3. Settings를 연다 여기를 누르면 Se..

0. 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는..

문병로 교수님의 '관계 중심의 사고법 쉽게 배우는 알고리즘 개정판'을 보고 작성합니다. 1. 연결리스트를 이용한 집합의 처리 연결리스트를 이용해 집합을 처리하면 각 원소당 하나의 노드를 만들고 이들을 연결리스트로 연결한다. 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두개의 포인터가 있습니다. 각 집합의 대표원소는 연결 리스트의 맨 앞에 있는 원소가 된다. 각 집합은 tail이라는 변수를 갖고 있다. 상호배타적 집합의 관리를 위해 세가지 연산이 필요하다. 1. Make-Set(x) : 원소 x로만 구성된 집합을 만든다 - 상수시간이 든다 2. Find-Set(x) : 원소 x를 가진 집합을 알아낸다 - 역시 상수 시간이 든다. (정상수) 왜 상수 시간이 드냐면 Find-Set은 ..