하다보니

컴퓨터를 호스트라고 한다. cpu는 메모리에 올라와 있는 기계어를 처리한다. cpu안에 메모리 주소를 가리키는 레지스터가 있다.(program counter이다.) cpu는 메모리에 있는 instruction을 순차적으로 수행한다. cpu는 아주 빠른 일꾼이다. interrupt 들어온 것이 있는지 check 해서 하던 작업을 멈추고 누가 쓰고 있었던 상관없이 cpu 제어권이 운영체제한테 넘어간다. 해당 interrupt에 맞게 처리해야 할 일들이 운영체제 커널에 함수로 정의가 되어 있다. 인터럽트 벡터는 인터럽트 번호와 주소의 쌍을 가진다. cpu는 매번 program counter가 가리키는 곳을 실행하게 된다. 운영체제가 cpu를 가지고 있을 때는 mode bit이 0이다. io디바이스에 접근하는 ..

#include #define X first #define Y second using namespace std; string board[102]; bool vis[102][102]; int n; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; void bfs(int i, int j) { queue Q; Q.push({ i,j }); vis[i][j] = 1; while (!Q.empty()) { pair cur = Q.front(); Q.pop(); for (int i = 0; i < 4; i++) { int nx = cur.X + dx[i]; int ny = cur.Y + dy[i]; if (nx=n || ny=n)continue; if (vis[nx][ny..

#include #define X first #define Y second using namespace std; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; int main() { int T;//테스트 케이스 cin >> T; while (T--) { int m, n, k;//가로길이, 세로길이, 배추 위치 cin >> m >> n >> k; int board[52][52] = { 0 }; int vis[52][52] = { false }; int a, b; int cnt = 0; queue Q; for (int i = 0; i > a >> b; board[b][a] = 1; } for (int i = 0; i < n; i++..

/* 수빈이는 현재 n, 동생은 k에 있따. x+1,x-1가능, 2*x가능. 수빈이와 동생의 위치가 주어졌을 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인가. */ #include using namespace std; int dist[100002]; int main() { int n, k; cin >> n >> k; fill(dist, dist + 100001, -1); dist[n] = 0; queue Q; Q.push(n); while (dist[k] == -1) { int cur = Q.front(); Q.pop(); for (int i : {cur - 1, cur + 1, cur * 2}) { if (i 100000)continue; if (dist[i] != -..

DFS는 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘이다. BFS는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. BFS 과정 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 스택이 빌 때까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 n개일 때 O(n)이다. 위의 과정은 BFS의 과정과 다른 것은 다 똑같고 큐만 스택으로 바뀐 것이다. 큐를 쓰면 BFS이고 스택을 쓰면 DFS가 된다. #include using namespace std..

해시란 단방향 암호화 기법으로 해시함수(해시 알고리즘)을 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미한다. 해시 함수(짧게는 해시)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다. 쉽게 말해 아무리 큰 숫자를 넣어도 정해진 크기의 숫자가 나오는 함수이다. 이때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정을 해싱(hashing)이라고 한다. 이러한 해시 함수들을 적용하여 나온 고정된 길이의 값을 해시값이라고 한다. 해시값 자체를 index로 사용하기 때문에 평균 시간 복잡도가 O(1)로 매우 빠르다. 해시함수는 계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어 내는 함수..

#include #define X first #define Y second using namespace std; string board[1002]; int dist1[1002][1002];//불 전파 int dist2[1002][1002];//지훈이 이동 int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; int main() { int r, c; cin >> r >> c; queue Q1; //불 queue Q2; //지훈이 for (int i = 0; i < r; i++) fill(dist1[i], dist1[i] + c,-1); for (int i = 0; i < r; i++)fill(dist2[i], dist2[i] + c, -1); for (int i = ..

#include #define X first #define Y second using namespace std; int board[1002][1002]; int visited[1002][1002]; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,-1,1 }; int main() { int n, m; queue Q; cin >> m >> n; for (int i = 0; i > board[i][j]; if (board[i][j] == 1)Q.push({ i,j }); if (board[i][j] == 0)visited[i][j] = -1; } } while (!Q.empty()) { auto..

#include using namespace std; #define X first #define Y second string board[102]; int dist[102][102]; int n,m; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i > board[i]; for(int i = 0; i < n; i++) fill(dist[i],dist[i]+m,-1); queue Q; Q.push({0,0}); dist[0][0] = 0; while(!Q.empty()){ auto cur = Q...

그림판의 페인트 기능을 이용하면 물고기의 색을 바꿀 수 있다. 페인트의 기능은 외부 윤곽선을 따라서 구분되는 영역의 색을 한꺼번에 바꾸는 것이고 이런걸 flood fill이라고 한다. 이 기능을 어떻게 구현할 수 있을까. 일단 클릭한 칸의 상하좌우를 보며 색이 같은지를 확인하고 같은 칸에 대해서 또 상하좌우로 확인하고,,,좀 막연하다. 이 기능을 BFS 알고리즘으로 해결할 수 있게 된다. BFS란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 원래 bfs는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 여기서 말하는 그래프는 정점과 간선으로 이루어진 자료구조이다. BFS 과정 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 원소를 꺼내어 그 칸에 상하..