알고리즘매일매일

https://www.acmicpc.net/problem/1655

값이 계속 들어올 때마다 중간값을 출력해주어야 하기 때문에 매번 정렬을 해서 가운데 값을 출력해주면 시간 초과가 발생한다. 따라서 이 문제는 최대 힙(Max heap)과 최소 힙(Min heap) (우선순위 큐)을 사용하여 풀 수 있다.

1. 최소 힙의 값들은 모두 최대 힙보다 크도록하고

2. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하며 값을 넣는다.

3. 값을 넣어준 후 최대 힙과 최소 힙의 top 값을 비교해서 최소 힙의 top보다 최대 힙의 top이 더 크다면 값을 교환해준다.

그러면 최대 힙의 top값이 중간값이 된다.

문제의 예제 중 마지막 값인 5를 6으로 수정해서 예를 들어봤다.

1 5 2 10 -99 7 6

위와 같은 값들을 순차적으로 입력받는다고 하면

처음에 들어온 1은 max heap에 들어간다. 중간 값은 1

max heap : 1

min heap : 

다음에 5가 들어오면 max heap의 크기가 더 크므로 min heap에 값이 들어간다.

max heap : 1

min heap : 5

이때, max heap의 top보다 min heap의 top이 크므로 값의 변경은 일어나지 않고, 중간값은 max heap의 top인 1이다.

그다음에 2가 들어오면 크기가 같으므로 max heap에 들어가고 2는 5보다 작으므로 값의 변경은 일어나지 않는다.

max heap의 top인 2가 중간 값이다.

max heap : 1, 2

min heap : 5

다음으로 10이 들어오면 min heap의 크기가 더 작으므로 min heap에 들어가고 중간 값은 max heap의 top값인 2이다.

max heap : 1, 2

min heap : 5, 10

-99는 두 heap의 사이즈가 같으므로 max heap에 들어가고 중간 값은 2이다.

max heap : -99, 1, 2

min heap : 5, 10

7은 min heap으로 들어간다. 중간 값은 그대로 2이다.

max heap : -99, 1, 2

min heap : 5, 7, 10

마지막으로 6은 두 heap의 사이즈가 같으므로 max heap에 들어간다.

max heap : -99, 1, 2, 6

min heap : 5, 7, 10

이때, max heap의 top인 6이 min heap의 top인 5보다 크므로 두 값을 교환해주어야 한다.

max heap : -99, 1, 2, 5

min heap : 6, 7, 10

교환해주고 나면 max heap의 top인 5가 중간값이 된다.

c++에서 우선순위 큐는 기본적으로 최대 힙이기 때문에 최대 힙은 그냥 우선순위 큐를 하나 만들어주면 되고

최소 힙은 functionl을 include 해준후

 priority_queue<int, vector<int>, greater<int>> minheap;

이런 식으로 greater를 이용해서 만들어주면 된다.

처음에는 minheap에 값이 없으므로 top값을 가져올 수 없으므로 maxheap에만 값을 추가하고 다시 다른 값을 입력받도록 처리해주어야 한다. 아니면 top값을 비교할 때 minheap이 비어있는지를 검사해줘도 된다.

https://www.acmicpc.net/problem/17143

(수정)

이전의 풀이가 재채점 후에 시간 초과로 바뀌어서 다시 풀었다...

속력 s만큼 이동하면 안되고 결국 똑같은 범위 안에서 왔다 갔다 하는 것이므로 % 연산을 사용하여 이동을 단축시킬 수 있다. 즉 상하로 움직이는 경우에는 (r-1) * 2 , 좌우로 움직이는 경우에는 (c-1) * 2  만큼 움직일 때 원래 자리로 돌아온다.

//상하로 움직이는 경우

  if (d <= 2) {

        s = s % ((R-1) * 2);

  }

  else { //좌우로 움직이는 경우

        s = s % ((C-1) * 2);

  }

s만큼 이동하기 전에 이렇게 추가해줘서 pass하였다.

시뮬레이션 문제인데 상어들이 같은 곳에 있을 때의 처리를 해주는 게 어려웠다.

swea의 미생물 격리(?) 문제랑 살짝 비슷한 것 같다(미생물 격리가 더 어려움)

문제에서 주어지는 상어의 좌표, 속력, 방향, 크기의 정보와 추가적으로 살아있는지 여부를 확인할 bool변수를

구조체로 저장하여 관리하였다.

또한, 배열을 만들어서 상어의 위치에 상어의 인덱스를 저장하였다.(상어의 인덱스는 입력받은 순서다)

예를 들어 두 번째 상어의 좌표가 (1,3)이었다면 map [1][3] = 2

이런 식으로 저장하고 이동하거나 죽으면 다시 0으로 바꿔줬다.

이 배열을 활용하면 낚시왕이 상어를 잡을 때 낚시왕이 서있는 열만 배열에서 쭉 확인해주면 되므로

쉽게 구현할 수 있다.

두 마리 이상의 상어들이 같은 곳에 위치할 때에도 이 배열을 확인하였다.

이동할 좌표에 대해 다음과 같이 나눠서 처리해주었다.

r, c로 이동한다고 가정했을 때,

• map[r][c] = 0 인 경우 ( 다른 상어가 없다)
  • 바로 map[r][c]에 현재 상어의 인덱스를 저장하면 된다.
• map[r][c] > i 인 경우 ( 이전 인덱스의 상어가 와 있는 경우 ) // 인덱스 순서대로 진행하지면 동시에 일어나는 일이다!!
  • 현재 이동(같은 시간)에서 와 있는 상어이므로 크기를 비교 후 더 큰 상어가 해당 위치에 남아있게 된다.
• map[r][c] < i 인 경우 ( 다음 인덱스의 상어의 번호가 있는 경우) 이전 이동(이전 시간)에서의 상어의 위치이다.
  • 다음 인덱스의 상어는 어차피 좀 이따 이동시켜줄 것이므로 그냥 첫 번째 경우처럼 바로 저장해주면 된다.

좀 더 자세한 설명은 코드의 주석 참고!

https://www.acmicpc.net/problem/17406

회전 연산을 사용하는 모든 경우를 구해주고 배열을 회전시켜줘야 하는 문제이다.

즉, 완전 탐색 + 시뮬레이션이다.

회전 정보는 구조체로 만들어서 벡터에 저장하여 관리하였다.

그리고 문제에서 (1,1)부터 시작하므로 r과 c 좌표는 각각 1씩 빼주었다.

정답의 최댓값은 행의 최대길이 50 * 칸의 최댓값 100으로 5000정도이지만 그냥 안전하게 10000 정도를 초기값으로 넣어놨다.

 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

라는 문제 조건에 따라 사용할 회전 연산 순서를 모두 정해준다.

순서를 정할 때마다 새로운 배열을 만들어서 배열을 회전시켜준 상태로 넘겨준다.

그리고 k개 만큼 순서를 모두 정했다면 그때의 배열의 값(행의 합 중 최솟값)을 구해준다.

회전을 시킬 때는 밑의 그림에서 파란 네모로 묶인 애들을 각각 for문을 사용해서 옮겨줬다.

즉 for문을 4번 사용하여 회전시켰다.

(r-s, c-s)를 시작점으로 배열을 회전시켜줄 건데 이 부분의 값은 따로 빼놓는다.

그리고 첫번째 for문에서 밑의 칸들을 하나하나 올려준다.

그리고 다시 두 번째 for문에서 오른쪽 칸들을 옆으로 하나하나 옮겨준다.

옮겨주다가 맨 윗줄을 이동시켜줄 때는 마지막 칸을 옮기면 안 되고 처음에 빼놨던 (r-s, c-s) 값을 넣어줘야 한다.

s가 2인 경우에는 2인 경우와 1인 경우 모두 구해줘야 하기 때문에 s 값을 줄여가면서 배열을 모두 돌려주면 된다.

2부터 시작해서 r-2, c-2를 시작점으로 배열을 회전시키고 난 후에 s 값을 1 감소시켜서

다시 r-1, c-1을 시작점으로 다시 배열을 회전시켜주면 된다.

마찬가지로 s가 더 큰 값일 경우에도 s 수만큼 배열을 회전시키면 된다.

https://www.acmicpc.net/problem/2468

안전 영역을 구해줄 것이므로 물에 잠기지 않는 부분에 대해서 BFS를 해준다.

그리고 BFS를 한 횟수가 안전영역의 수가 된다.

지역의 높이 범위가 1부터 100인데 시간을 줄이기 위해서 지역의 정보를 처음에 입력을 받을 때 지역 높이의 최댓값을 구해놓는다.

그리고 1부터 높이의 최댓값 -1 까지만큼 비가 오는 경우를 모두 구해주면 된다.

높이의 최댓값 이상으로 비가 오는 경우는 안전 영역이 0이 되기 때문이다.

그리고 각 경우에서의 안전 영역을 정답(최댓값)과 비교해서 저장한다.

주의할 점은 

아무 지역도 물에 잠기지 않을 수도 있다.

라고 문제 밑부분 노트에 쓰여있는데 이 경우는 안전 영역이 1이므로 정답의 초기값은 0이 아닌 1로 해놓아야 한다.

https://www.acmicpc.net/problem/2573

BFS를 이용해서 푸는 문제이다.

인접한 칸이 바다인 경우에는 그 개수를 세주어서 빙산의 높이에서 빼주면 된다.

바다가 아닌 빙산인 경우에는 큐에 넣어주고 해당 빙산에 대해서도 탐색을 이어가면 된다.

BFS는 연결된 모든 칸을 방문하기 때문에 연결되지 않은 칸에 방문하기 위해서는 BFS를 새로 시작하여야 한다.

즉, bfs횟수가 1회일 때는 아직 모두 연결되어 있는 한 덩어리라는 뜻이므로 계속 시간을 늘려가며 bfs를 진행하고

BFS 횟수가 1번이 넘을 때는 빙산이 두 덩어리 이상이 됐음을 의미하므로 그때 시간을 출력해주고 탐색을 종료한다.

만약 다 녹았는데 빙산이 분리되지 않은 경우를 처리하기 위해서는 flag 변수를 둬서 bfs탐색이 한 번도 일어나지 않은 경우에 0을 출력해주고 종료하도록 해줬다.

https://www.acmicpc.net/problem/2234

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

를 구하는 문제이다. 이 문제는 bfs와 비트 마스크를 사용해서 풀었다.

먼저 1번과 2번문제에 대한 답을 먼저 구하였다.

방문하지 않은 모든 칸에 bfs를 사용하여 방문하고 bfs가 시작될 때마다(새로운 방이므로) 방 개수를 늘려준다.

그리고 bfs탐색을 할때마다 방문하는 칸의 개수를 세줘서 방의 넓이를 구하여 방의 넓이 중 최댓값을 구할 수 있다.

이 문제에서 bfs를 할 때 중요한 부분은 벽인지 아닌지 알아내야 한다.

벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

라고 문제 입력에서 주어지는데 이 부분이 힌트인 것 같다. 그림으로 나타내면 아래와 같다.

문제에서 주어진 예시 그림(맨 위 그림)의 왼쪽 끝칸(0,0)을 예시로 들어보면 아래 그림과 같다. 서쪽, 북쪽, 남쪽에 벽이 있기 때문에

1+2+8 = 11로 11이 문제 입력에서 주어진다. 11은 다시 이진수로 1011로 나타낼 수 있으므로 이를 이용해서 비트 마스크로 검사를 한다.

int dx[] = { 0,-1,0,1 };

int dy[] = { -1,0,1,0 };

먼저 방향 배열을 서, 북, 동, 남 순서로 해놓아야 한다. 그래야 1 << 0을 했을 때의 값이 1이므로 서쪽을 표현할 수 있고 1<<1 은 2로 북쪽을 표현할 수 있다.

그리고 검사할 칸과 & (1<<k)를 해서 해당 위치에 1을 가지고 있는지 검사한다. (k는 0부터 3으로 네 방향의 index)

1을 가지고 있는 경우(위의 연산 결과가 0이 아닌 경우)에는 벽이므로 해당 방향으로는 이동하지 않는다.

그리고 나중에 3번 문제를 해결하기 위해서플러드 필 알고리즘(연결 요소에 번호를 매김)을 사용한다. bfs를 할 때 현재 연결된 칸들에 방 번호를 매겨주고 각 방의 넓이 또한 cnt 배열에 저장해놓는다.

3번 문제를 해결하기 위해서는 다음과 같은 생각을 했다.

인접해있는 방과 현재 방의 넓이를 합쳤을 때의 최댓값이 하나의 벽을 제거했을 때의 결과와 마찬가지다.

아래 그림을 봤을 때 1번 방은 2번 방과 3번 방과 인접해있는데 3번 방과 인접해있는 벽 중 하나를 제거했을 때 최댓값을 얻을 수 있다.

코드로 구현하자면 다시 새로운 bfs를 이용한다. 이때 bfs에서는 아까 플러드 필 알고리즘을 사용하여 방 번호를 매긴 배열을 이용한다.

이동했을 때 같은 방인 경우에는 계속 큐에 넣고 방문 체크를 해주며 탐색을 이어가고 같은 방이 아닌 경우에는 현재 방의 칸수와 옆의 방의 칸수를 합친 값(위에서 저장한 cnt배열을 이용)을 저장하고 이 합쳐진 값들 중 최댓값이 정답이 된다.

1번 방에 대해 인접한 방에 대해서 모두 탐색을 해봤다면 다음 2번 방을 검사할 때는 다시 1번 방과 비교할 필요는 없다.

그러므로 bfs로 방문한 칸은 모두 다 체크해주면 된다.

역시 코드를 보는 게 가장 이해하기 쉬울 것 같다ㅎㅎ

순서는 main -> solve -> bfs 다음에 removeWall -> bfs2로 진행된다.

https://www.acmicpc.net/problem/11559

시뮬레이션 카테고리에 넣었지만 BFS도 이용하는 문제이다.

BFS는 상하좌우로 연결되어 있는 같은 색의 뿌요를 찾기 위해 사용한다.

먼저 연쇄가 몇 번 일어났는지를 알아내야 하는 문제이기 때문에 연쇄가 일어나지 않을 때까지 터뜨리기를 반복해야한다.

각 반복에서는 뿌요가 있는 모든 칸에 대해서 BFS탐색을 통해 상하좌우로 연결된 같은 색의 뿌요가 네 개 이상 있는지 체크해준다. 있다면 해당 칸의 뿌요들을 터뜨려주고(.으로 만들어 준다) 연쇄가 발생했다는 뜻으로 true를 리턴한다.

문제 조건에 따라 여러 그룹의 뿌요가 터졌더라도 연쇄는 한 번 일어난 걸로 간주한다.

예를 들어, 전체 칸을 탐색할 때 R이 4개 이상 모여있었고 다른 곳에서 G가 4개이상 모여있어서 두 그룹이 터졌다고 해도 같은 턴에 터지는 애들은 한번 일어난 걸로 count 해준다.

모든 뿌요에 대해서 탐색을 해줬는데 flag가 false라면 (한 번도 연쇄가 발생하지 않았다면) 반복문을 break 해주고 정답을 출력해주면 된다.

flag가 true라면(연쇄가 적어도 한 번 이상 발생했다면) 떠있는 뿌요들을 바닥에 내려주고 연쇄가 일어난 횟수(정답)를 증가시킨다.

https://www.acmicpc.net/problem/3190

이 문제에서 어려운 점은 뱀이 자기 몸에 부딪혀서 게임이 끝날때를 처리해주는 부분인 것 같다.

이 부분은 몸길이와 칸에 머리가 있었던 시간을 저장한 배열을 이용하면 쉽게 구할 수 있다.

(현재 시간 - 몸길이)가 이동할 칸에 이전에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다