https://www.acmicpc.net/problem/17144문제 읽고, 생각해보기문제를 읽어보다면, 특별한 점은 기존의 BFS에 공기 청정기가 하나 추가되고, 배열 내 값이 이동한다는 점이다.해당 사항의 대해 순서대로 어떻게 진행되는지도 친절하게 되어 있다.해당 문제에서 요구하는 기술은 BFS와 배열 회전이라고 생각된다.다만 해당 글을 쓰는 이유는 그 2가지를 제대로 못해서, 참회하고자, 기억하고자 적는다.먼저 문제에서는 공기 청정기에 대한 정의가 있다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 해당 내용을 통해 이후 회전 방법에 대해 고민될 부분이 조금 적어진다.그 다음은 미세먼지가 확산되는 방법은 기존 토마토? 관련되어 비슷하니 넘어가도 좋을 것 같다.(어차피 아..
https://www.acmicpc.net/problem/12851시간 복잡도 계산=> 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다N이 10^5 임으로 O(N^2) 해결할 수 없고, 그 하위로 풀어야 한다.BFS는 정점의 개수 10^5, 간선의 수 3개 O(V) 안에 해결 가능하다.visisted를 while 안과, for문 안 탐색할 때 처리가 가능한데, 이에 대한 이유를 알 수 있었던 문제라고 생각된다.#include#include#includeusing namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; c..
아기 상어 골3, 장애물 생각해보기
https://www.acmicpc.net/problem/16236상어가 사이즈가 1인 경우, 위 쪽 1과 아래쪽 1을 갈 수 있다. 이 때 문제에서 장애물에 대한 정의를 말하지 않았다.그렇기 때문에, BFS 문제라고 말했지만, 장애물이 없다는 사실에 착안해서 좌표끼리의 차이를 계산해서 거리를 계산했다.하지만 물고기가 장애물이라 사실을 몰랐다. 물고기가 좌표 사이에 있어서 무시하고 지나갈 수 있는 조건이 없기 때문에, 피해서 가야 한다. 그렇다면 피하기 위해서는 결국 해당 값을 확인해야 한다. 그렇기 때문에 좌표를 통해 직접 이동하지 않고 구할 수 있는 방법이 없었다.결국 BFS로 문제를 풀어야 하는 시뮬레이션 문제이다. 다시 BFS로 풀어야 겠다.
사전 순 최대 공통 부분 수열 성공 C++
https://www.acmicpc.net/problem/30805문제는 백준에서 읽을 수 있습니다.해당 문제는 solved.ac에서 4 클래스 문제를 다 풀기 위해서 문제를 해결하려고 했으나, 너무 오래 걸렸다.문제에서는 해당 부분을 주의 깊게 보면 좋다. 처음에 봤을 때 무슨 말인지 감이 안 왔다.예제 값과 문제의 설명을 함께 본다면, 무조건 큰 값이 앞에 오면 된다는 내용을 이해할 수 있다.그러니까 크게 문제의 시간 복잡도도 그렇게 높지도 않기 때문에 DP까지 갈 필요가 없는 문제이기도 하고, 무조건 공통 값 중 큰 값이 앞으로 오면 된다는 점을 착안해서 문제를 풀 수 있다.내가 오래걸린 문제일단 다른 사람들의 해결 방법을 보았을 때 살짝 어지러웠다. 문제에서는 공통 값 중 큰 값 순으로 나열하면 ..