문제 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은 ..

문제 글로벌 비즈니스 센터(GBC, Global Business Center)는 현대자동차그룹 통합 사옥이다. 지하 7층, 지상 105층, 높이 약 570m의 규모로 2026년 하반기에 완공을 목표로 현재 공사 중에 있다. 이러한 초고층 높이의 빌딩에는 초고층 승강기가 들어가야 한다. 엘리베이터 정비공인 광우는 0m 부터 100m까지 일정 구간들의 엘리베이터 속도를 검사하는 업무를 맡게 되었다. 빌딩에서 운영되는 엘리베이터 구간은 N개의 구간으로 나뉘며 해당 구간의 제한 속도이 주어진다. 구간의 총 합은 100m 이며 각 구간별 구간의 길이와 제한 속도 모두 양의 정수로 주어진다. 예를 들어보자. 구간이 3이라고 할 때, ▶ 첫 번째 구간의 길이는 50m 이고 제한 속도는 50m/s ▶ 두 번째 구간의 ..

문제 남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다. 돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는? 제약조건 1 ≤ N ≤ 3×103 인 정수 1 ≤ Ai ≤ 108 인 정수 입력형식 첫 번째 줄에 돌의 개수 N이 주어진다. 두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다. 출력형식 첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라. 풀이방법 이 문제는 전형적인 dp 문제이다. dp 문제를 정말 오랜만에 풀어보는 것 같다. dp[n] = n번째 까지 오름차순으..

앞으로 여기에 논자시 공부 글을 업로드할 예정입니다 업로드가 안될시 논자시에 떨어져 전 노숙자가 될거에요 일단 오늘까지 알고리즘 책을 사고 올리도록 하겠습니다

문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으..