백준

1. 문제 풀이문제를 대충 읽고 풀었더니 정말 오래 걸렸습니다. 너비우선탐색을 진행하면서 각 칸에 대한 거리를 구하고 자신보다 큰 물고기가 있는 곳은 탐색할 수 없고 크기가 같은 물고기는 먹진 못하고 지나칠 순 있습니다. 그리고 자신보다 크기가 작은 물고기의 위치에 대해서 가장 짧은 거리에 위치하면서 여러 개일 경우 상단 좌측에 있는걸 우선순위로 구해줍니다.그렇게 구한 물고기의 위치가 갱신되지 않았다면 루프를 종료하시고, 갱신되었다면 너비우선탐색으로 구한 거리값을 더해주고 빈칸으로 만들어줍니다. 이때, 상어의 크기만큼 물고기를 먹었다면 상어의 크기를 1 증가시킨 다음 물고기의 위치로 상어의 위치를 옮기고 루프를 반복하시면 됩니다. 2. 코드 #include using namespace std;typede..

1. 문제 풀이 배열을 { 값, 순서 } 형태로 저장합니다. 여기서 값은 배열의 실제 값이고, 순서는 해당 값이 배열에서 등장한 순서를 의미합니다. 이 배열을 값을 기준으로 내림차순으로 정렬하되, 값이 같다면 순서를 오름차순으로 정렬합니다. 정렬한 두 배열의 처음 값을 가리키는 포인터를 각각 두고, 두 포인터 중 하나가 배열의 끝에 도달할 때까지 비교를 진행합니다. 두 포인터가 가리키는 값 중 더 큰 값을 가진 포인터를 앞으로 이동시킵니다. 과정을 진행하다가 두 포인터가 가르키는 값이 서로 같아지면 해당 값이 지금까지 저장한 부분 수열의 마지막 값의 순서보다 나중에 등장한 값이라면 그 값을 부분 수열에 추가합니다. 그렇지 않다면 버리고, 계속 진행합니다. 여기서 중요한 점은, 부분 수열에 값을 추가할 때..

1. 문제풀이 문제 유형은 시뮬레이션입니다. 시뮬레이션은 복잡한 상황을 주어지고 이를 구현하여 풀이해야 하는 유형입니다. 속된 말로 빡구현이라고 합니다. 물론 이런 구현 과정에서 최적화가 필요하다고 생각되면 알고리즘을 적용하여 풀이할 수 있긴 합니다. 문제를 잘 읽고 미세먼지가 확산되는 로직과 공기청정기가 작동되는 로직을 구현하여 풀이하시면 됩니다.  2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typede..

1. 문제 풀이 이 문제의 경우 지문이 엄청 깁니다. 이를 요약하면 아래와 같이 정리할 수 있습니다.컴퓨터에서 실수를 부동소수점으로 표기할 때, 표기 방식에 의한 오차가 발생할 수 있습니다. 이러한 오차를 줄이기 위해, 문제에서는 기약분수의 형태로 수를 통분하여 정확하게 계산하도록 요구합니다. 그러나 여러 기약분수를 통분하여 계산하는 과정에서 값이 매우 커질 수 있으며, 이는 오버플로우를 일으킬 수 있습니다. 따라서 모듈러 연산을 이용하여 계산해야 합니다. 모듈러 연산에서 덧셈과 곱셈의 분배 법칙은 성립하지만, 나눗셈의 경우에는 분배 법칙이 성립하지 않으므로 직접적인 나눗셈이 불가능합니다. 이를 해결하기 위해 곱셈의 역원을 구해 나눗셈을 대체해야 합니다. 만약 모듈러 연산의 기준이 되는 값 (즉, MOD..

1. 문제 풀이오늘 풀어본 문제는 백준 18346번 수열과 쿼리 37입니다. 문제의 유형은 세그먼트 트리입니다. 세그먼트 트리를 이용해 짝수의 개수와 홀수의 개수를 구간별로 관리하면서 풀이했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef vector vti; typedef vector vtl;typedef vector..

1. 문제 풀이오늘 풀어본 문제는 백준 4195번 친구 네트워크입니다. 문제의 유형은 해시+유니온-파인드였습니다. 사람 이름을 index로 치환하기 위해 해시 자료구조를 사용하였습니다. 각 테스트케이스에서 관계가 최대 100'000개 나오므로 서로 다른 사람의 이름이 200'000개 나올 수 있음을 유의하면서 유니온-파인드를 구현하시면 됩니다. 평소 rank by 기법을 주로 사용하여 구현하였는데, 문제의 요구 사항을 구현하기 위해 집합의 크기를 사용하여 구현했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tupl..

1. 문제 풀이안녕하세요. 오늘 풀어볼 문제는 "백준 17352번 여러분의 다리가 되어 드리겠습니다!"입니다. 문제의 유형은 "disjoint-set"입니다. distjoint-set은 분리집합이라고 하며 이를 구현한 알고리즘을 union-find라고 합니다. 관련 알고리즘을 모르신다면. 유니온-파인드 알고리즘 링크를 클릭해서 내용을 공부하시고 풀어보시길 바랍니다. 정점이 N개이고 간선이 N-1개인 무방향 연결그래프에서 임의의 간선 하나를 삭제한 무방향 비연결 그래프가 주어졌을 때, 하나의 간선을 다시 이어 연결그래프가 되는 간선 하나를 아무거나 찾아 출력하면 됩니다. 입력으로 주어진 간선이 잇고 있는 두 정점 정보를 union 하게 되면 최종적으론 두 개의 집합이 됩니다. 그 두 집합에서 각각 아무 정..

1. 문제 풀이 안녕하세요 오늘 풀어본 문제는 백준 14950번 정복자입니다. 문제의 유형은 최소 신장 트리입니다. 그래프 이론 알고리즘은 문제의 설명을 읽으면서 어떤 그래프 형태인지 파악할 수 있어야 합니다. 이 문제의 경우, 무방향 가중치 연결 그래프임을 알 수 있습니다. 정복할 때마다 t만큼 모든 도로의 비용이 증가하지만 모든 도시를 정복해야 하므로 추가되는 비용은 정점의 개수에 따라 일정합니다. 따라서 최소 신장 트리가 되는 간선들의 가중치를 모두 더하고 정점의 개수에 맞추어 추가 비용을 더해주면 쉽게 구할 수 있습니다. 2. 코드 #include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pa..