본문 바로가기
반응형

알고리즘

 (136)
[백준] 14502번 연구소 14502번 연구소 1. 이해하기 연구소에 바이러스가 퍼지지 않도록 벽을 세워야 한다. 벽은 꼭 3개를 세워야 한다. 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다. 바이러스가 벽으로 인해서 퍼져나갈 수 없는 영역을 안전영역이라 한다. 안전 영역 크기의 최댓값을 구해야 한다. 2. 구현하기 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다. BFS를 이용하여 바이러스의 이동을 구현한다. void bfs(int r, int c) { queue q; q.push({r,c}); visited[r][c] = true; while(!q.empty()) { int x = q.front().x,y = q.front().y; q.pop(); for(int i = 0; i < 4; i++) { int nx = x+d..
[백준] 14501번 퇴사 14501번 퇴사 1. 이해하기 상담을 하여 가장 많이 받을 수 있는 금액을 얻는 방법. 모든 날의 상담을 할 수 있는 것이 아닌 최종 일전까지만 상담을 받을 수 있고 상담이 최종일까지 끝나야 한다. 완전탐색과 DP로 풀 수 있다. 2. 구현하기 완전탐색 방법 최종일을 넘는 경우에는 상담을 하지 못하므로 0을 반환한다. day+1을 넣어주는 경우는 그 날에는 상담을 하지 않고 다음 날에 상담을 하는 경우도 찾아주기 위해서이다. int solve(int day, int pay) { if(day > N) return 0; if(day == N) return pay; int ret = 0; ret = max(ret,solve(day+1,pay)); ret = max(ret,solve(day+schedule[d..
[백준] 14500번 테트로미노 14500번 테트로미노 1. 이해하기 가능한 테트로미노 5가지 모양을 종이 위에 놓아보며 테트로미노가 놓은 칸의 수들의 합의 최대를 구하는 문제. 테트로미노가 놓여질 수 있는 방법을 모두 구해서 값을 비교해보는 완전탐색 문제. 2. 구현하기 각 모양마다 나올 수 있는 방법을 모두 구해 합을 반환하는 함수 int get_max_sum(int x, int y) { int sum = 0; if(y+3 < M) { int temp = map[x][y]+map[x][y+1]+map[x][y+2]+map[x][y+3]; sum = max(sum,temp); } if(x+3 < N) { int temp = map[x][y]+map[x+1][y]+map[x+2][y]+map[x+3][y]; sum = max(sum,t..
[백준] 14499번 주사위 굴리기 14499번 주사위 굴리기 1. 이해하기 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다. 지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 주사위를 굴렸을 때, 이동한 칸에 쓰여있는 수가 0이 아니면 칸의 수가 주사위의 바닥면으로 복사되고 칸에 쓰여 있는 수는 0이 된다. 주사위를 지도의 바깥으로 이동시키는 명령은 무시하며 출력도 하지 않는다. 주사위가 이동할 때마다 주사위의 상단에 쓰여 있는 값을 출력하는 문제. 주사위를 직접 만들어 보거나 그려서 이해하는 시뮬레이션 문제. 2. 구현하기 주사위를 그려서 동쪽..
[백준] 13458번 시험 감독 13458번 시험 감독 이해하기 총감독관은 한 방에 오직 1명만 있어야 한다. 부감독관은 여러 명 있어도 된다. 각 시험장에 있는 응시생들을 모두 감시해야 할때 필요한 감독관 수의 최솟값 구하는 문제 구현하기 총감독관은 한명만 꼭 있어야 하므로 총감독관이 감시할 수 있는 인원수를 미리 빼놓는다. 남은 인원수를 바탕으로 부감독관이 감시할 수 있는 인원으로 나눈다. 이때 나머지가 있으면 부감독관 한명이 더 필요한 것이므로 한명을 더 더해준다. #include using namespace std; int a[1000000]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i = 0; ..
[백준] 3190번 뱀 3190번 뱀 이해하기 뱀의 처음 시작 위치는 맨위 맨좌측, 길이는 1, 오른쪽을 보고있다. 뱀은 몸길이를 먼저 늘려 머리를 다음칸에 위치시킨다. 이동한 칸에 사과가 있다면, 사과가 없어지고 꼬리는 그대로이다. 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 있던 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 게임이 끝나는 조건이 뱀이 벽 혹은 몸통에 부딪히면 일때 이 게임이 몇 초에 끝나는지를 계산하는 문제. 뱀을 이동시키면서 상태를 보는 시뮬레이션 문제. 구현하기 1초마다 뱀의 움직임 상태 반환 이동에 성공했으면 true를 반환, 실패했으면 false를 반환 실패는 몸통에 닿았거나 벽에 부딪혔을 때 뱀의 몸통 상태는 queue에 넣어서 관리 움직였을 때 사과가 있으면 꼬리 그대로, 없으면 꼬리 삭..
[백준] 12100번 2048(Easy) 12100번 2048(Easy) 이해하기 한 번의 이동은 보드 위에 있는 블록을 같은 방향으로 이동시킨다. 이동했을 때 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐진다. 같은 이동에서 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다. 최대 5번의 이동을 통해 만들어 질 수 있는 블록의 최대값을 구한다. 블록을 최대 횟수까지 이동시키며 상태를 보는 완전탐색 문제. 구현하기 한번의 방향으로 이동시키면서 같은 값의 블록이 충돌하면 두 블록을 하나로 합치고 이미 합쳐진 블록은 다른 블록과 합쳐지지 못하게 check배열을 이용한다. vector move(vector map, int dir) { vector ret(N,vector(N)); memset(check,false,sizeof(check));..
[백준] 13460번 구슬 탈출2 13460번 구슬 탈출2 이해하기 빨간 구슬과 파란 구슬이 보드를 움직일 때마다 동시에 움직인다. 빨간 구슬만 구멍에 빠져야 한다. 파란 구슬이 동시에 빠지는 경우는 실패한 경우로 생각한다. 성공한 경우에 구슬을 최소로 움직인 경우를 구한다. 구현하기 빨간 구슬과 파란 구슬이 동시에 움직이는 것 Point move(Point ball, int dir) { int nx = ball.x+dx[dir], ny = ball.y+dy[dir]; while(1) { if(map[nx][ny] == '#') { return {nx-dx[dir],ny-dy[dir]}; } else if(map[nx][ny] == 'O') { return {-1,-1}; } nx += dx[dir]; ny += dy[dir]; } } ..

티스토리툴바