본문 바로가기
반응형

알고리즘

 (136)
[백준] 17140번 이차원 배열과 연산 17140번 이차원 배열과 연산 1. 이해하기 처음은 크기가 3x3인 배열로 시작한다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열의 모든 행에 대해서 정렬을 수행한다. 행의 개수 >= 열의 개수인 경우에 적용된다. C 연산: 배열의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다. 정렬하는 방법은 다음과 같다. 각각의 수가 몇 번 나왔는지 센다. 수의 등장 횟수가 커지는 순으로, 이것이 여러가지면 수가 커지는 순으로 정렬한다. 배열에 정렬된 결과를 다시 넣어준다. 넣어줄때 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다. 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다. (r,c)에 들어있는 값이 k가 되기 위한 ..
[백준] 17143번 낚시왕 17143번 낚시왕 1. 이해하기 격자판의 각 칸에는 상어가 최대 한 마리 들어있을 수 있다. 1초 동안 일어나는 일은 다음과 같다. 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다. 상어가 이동한다. 상어가 이동하려고 하는 칸이 격자판의 경계인 경우에는 방향을 반대로 바꿔서 이동한다. 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 때, 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다. 2. 구현하기 이 문제의 핵심 포인트는 상어의 움직임이다. 상어가 움직여서 원래 있던 자리까지 오는데의 거리는 가로 방향으로 움직였다면 2(R-1), 세로 방향으로 움직였다면 2*(C-1)이다. ..
[백준] 17144번 미세먼지 안녕! 17144번 미세먼지 안녕! 1. 이해하기 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에 미세먼지가 있다. 이때 1초 동안 일어나는 일 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. 미세먼지는 인접한 네 방향으로 확산된다. 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다. 확산되는 양은 (미세먼지 양)/5이고 소수점은 버린다. 그 자리에 남은 미세먼지 양은 (미세먼지 양)-(미세먼지 양/5)*(확산된 방향의 개수) 이다. 공기청정기가 작동한다. 공기청정기에서는 바람이 나온다. 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다. 바..
[백준] 16236번 아기 상어 16236번 아기 상어 1. 이해하기 가장 처음에 아기 상어의 크기는 2이고, 1초에 상하좌우로 인접한 한 칸씩 이동할 수 있다. 아기 상어는 자산의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기는 먹을 수 없지만 지나갈 수는 있다. 아기 상어가 어디로 이동할지 결정하는 방법 더 이상 먹을 수 있는 물고기가 없을 때 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다. 거리가 가까운 ..
[백준] 16235번 나무 재테크 16235번 나무 재테크 1. 이해하기 처음에 모든 칸에는 5만큼의 양분이 들어있다. 사계절마다 일어나는 일이 다르다. 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 이때 나무는 심어져있는 칸의 양분만 먹을 수 있다. 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 땅에 양분이 자신의 나이만큼 이상이 없다면 나무는 죽는다. 여름에는 봄에 죽은 나무가 양분으로 변한다. 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다. 가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 한다. 번식은 인접한 8개의 칸에 나이가 1인 나무로 번식된다. 겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 2. 구현하..
[백준] 16234번 인구 이동 16234번 인구 이동 1. 이해하기 모든 나라의 크기는 1x1이고, 각 나라의 인구수는 맵에 나와있는 숫자이다. 각 나라에 인접한 나라 사이에는 국경선이 존재한다. 인구 이동이 시작되는 방법 국경선을 공유하는 두 나라의 인구 차이가 L이상, R 이하이면, 국경선을 하루동안 연다. 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있는 나라는 연합이라 부른다. 연합을 이룬 나라들의 인구수는 (연합의 인구수)/(연합을 이루고 있는 칸의 캐수)가 된다. 소수점은 버린다. 연합을 해체하고, 모든 국경선을 닫는다. 인구 이동이 몇 번 발생하는지 알아낸다. 시뮬레이션 문제이다. 2. 구현하기 인접한 국가와의 인구수 차이가 L 이상, R 이하인지 살펴보고 맞으면 연합으로 포함한다. bfs를 이용하여 구한..
[백준] 5373번 큐빙 5373번 큐빙 1. 이해하기 큐브를 돌려가면서 그때의 윗 면의 색상을 구하는 문제이다. 큐브를 돌렸을 때 돌린 면을 포함, 다른 면들이 어떻게 변하는지 구현하는 시뮬레이션 문제. 2. 구현하기 각 면에 대해 그 면을 시계 방향, 반시계 방향으로 돌렸을 때 어떻게 되는지 구현. 그림을 그려서 이해하면 이해하기 쉽다. void temp_to_cube(char temp[3][3], char cube[3][3]) { for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { cube[i][j] = temp[i][j]; } } } void rotate_clock(char cube[3][3]) { char temp[3][3]; for(int i = 0; i < 3; i..
[백준] 15686번 치킨 배달 15686번 치킨 배달 1. 이해하기 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. (r1,c1)과 (r2,c2) 사이의 거리는 |r1-r2|+|c1-c2|이다. 치킨집 중에서 최대 M개를 고르고, 나머지는 폐업시킨다고 할 때 도시의 치킨 거리가 가장 작게 되는 값을 구하는 문제. 모든 치킨집에 대해서 구해보는 완전탐색 문제. 2. 구현하기 각 집에 대해서 치킨 거리를 구한다. int get_chicken_distance(vector chicken, int x, int y) { int ret = get_distance(chicken[0].x,chicken[0].y,x,y); int size = chicken.size(); for(int i = ..

티스토리툴바