알고리즘 문제 풀이

히스토그램에서 가장 넓은 직사각형을 구하는 것은, Range query로 히스토그램의 특정 구간의 가장 짧은 직사각형의 높이를 찾아 구간의 너비를 곱하는 것과 같다. 따라서 Segment Tree를 이용해 트리의 각 노드가 가장 짧은 직사각형의 높이를 저장하도록 구현하고, 구간으로 가능한 모든 경우에 대해 구간 질의하며 직사각형의 최대 넓이를 찾아 해결할 수 있는 문제이다. => Range query 결과가 해당 구간에서 가장 짧은 직사각형의 높이이므로, 쿼리 결과 x 구간 너비로 직사각형의 넓이를 구한 뒤 최대값을 갱신해 해결할 수 있다. 그러나 build에는 O(n) 시간이 걸리므로 문제 없지만, range query에 O(log n) 시간이 걸리므로 구간으로 가능한 모든 경우에 대해 구간 질의하기엔..

M개의 숫자를 가지는 N개의 원판을 K번 돌리는 기능을 T번 반복할 때의 최대 연산 횟수를 50x50x50x50라고 생각했을 때, 각 반복에서 아래 조건을 구현하기 위해서 사용할 수 있는 시간복잡도는 최대 O(log n)이다. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다. 따라서, push_back과 push_front를 이용해 원판을 돌리는 기능을 O(1) 시간에 구현할 수 있고 random access에도 O(1)의 시간복잡도를 갖는 deque를 사용하면 문제를 풀 수 있을 것이다. [ 풀이 방법 ] 1..

최대 반복 횟수는 1000, 체스판의 최대 크기는 12x12, 말의 최대 개수는 10이므로 탐색에만 약 1000만 번의 연산이 필요하다. 따라서 각 반복별로 말의 이동을 처리하는 기능을 위해 O(n)의 시간만 추가로 사용할 수 있을 것이다. [ 풀이 방법 ] 1. 말을 순서대로 이동시키는 기능 - 1~K - 말의 이동방향을 저장해 사용할 수 있어야 한다. -> vector를 이용해 말의 좌표와 이동 방향을 저장하는 구조체를 저장하고, 말의 순서는 index로 처리 2. 말이 이동하려는 체스판의 칸 색깔에 따라 이동을 다르게 처리하는 기능 1. 흰색: - 말을 이동시킨다. - 이동하려는 칸에 이미 말이 있을 경우 가장 위에 올려놓는다. - 말의 위에 다른 말들이 올려져 있을 경우, 말의 위에 있는 말들도 ..

배열의 크기가 최대 1000000이므로, 배열의 구간 합에 대한 Range query와 배열의 한 원소에 대한 Point update가 O(n log n) 시간 안에 처리되어야 한다. 따라서 Segment Tree 또는 Binary Indexed Tree를 사용하여 풀 수 있는 문제로 볼 수 있다. 원소의 절대값의 크기가 최대 | 263-1 | 이므로 long long 자료형을 사용해 원소와 구간 합 결과를 저장해야 한다는 점을 주의해야 한다. [ 풀이 방법 ] 세그먼트 트리(Segment Tree) 세그먼트 트리는 이진 트리의 일종으로, 트리의 leaf 노드가 원래 배열의 원소에 대응하는 값을 저장하고 나머지 노드는 구간 질의를 처리하기 위한 정보를 담고 있다. O(log n) 시간복잡도를 갖는 jsy..

2차원 배열의 최대 크기가 20x20이므로 x, y, d1, d2로 가능한 모든 경우를 탐색해도 20x20x20x20보다 적은 연산 횟수를 가질 것이기 때문에 완전 탐색으로 풀 수 있을 것이라 생각했다. [ 풀이 방법 ] 1. x, y, d1, d2를 조건에 맞게 정하고, 경계선을 만드는 기능 - 4중 for문을 이용해 x, y, d1, d2로 가능한 모든 경우를 탐색한다. - 경계선의 위치와 선거구 구역을 저장하기 위해 2차원 배열인 area를 만든다. - x, y, d1, d2를 정한 뒤, 문제에서 주어진 경계선 조건을 사용해 경계선에 해당하는 칸을 5로 채운다. 2. 만들어진 경계선과 문제에서 주어진 선거구 구역 조건에 따라 각 선거구를 나누고 인구를 세는 기능 - 만들어진 경계선 바깥쪽 칸에 대해..

간선에 음수가 아닌 가중치가 주어질 때 최단 경로를 찾는 문제이고 O(E log V)의 시간복잡도를 갖는 알고리즘으로 해결할 수 있으므로, 다익스트라 알고리즘을 사용하여 해결할 수 있는 문제임을 알 수 있다. 다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 알고리즘(Dijkstra's algorithm)은 Weighted graph, 즉 간선에 가중치가 있는 그래프가 주어졌을 때, 하나의 고정된 특정 노드에서 시작해 다른 모든 노드로 가는 최단 경로를 찾는 알고리즘이 jsyeo.tistory.com 따라서 위 링크에서 구현했던 다익스트라 알고리즘을 사용해 문제를 해결하였다. [ 정답 코드 ] #include #include #include #include using namespace..

어떤 위치 x로 가기 위한 가중치가 0(순간이동) 또는 1(걷기)이고, x로 가능한 위치는 0~100000으로 100001개이다. 따라서 0-1 BFS를 이용하여 가중치에 따라 deque의 앞, 뒤에 이동 후의 위치와 시간을 push하여 더 빠른 시간에 x에 도달한 경우가 더 먼저 탐색될 수 있도록 하고, visited 배열을 이용해 방문한 위치를 체크해서 x위치를 중복 탐색하지 않도록 하여 100001번 이상 탐색되지 않도록 구현했다. [ 풀이 방법 ] 1. 공통 - 걷거나 순간이동한 위치가 이동 가능한 위치인지 체크 - 이미 방문하지 않은 위치인지 체크, 방문했다면 다시 방문 X - 이동한 위치가 동생이 있는 위치라면 탐색 종료 후 결과를 출력 1. 수빈이가 걷는 경우 - 시간을 1초 늘리고 deq..

시간제한이 0.25초로 짧았으나, 2차원 배열의 최대 크기가 50x50 = 250이고 바이러스의 최대 개수가 10개이기 때문에 10개 중 M개를 고르는 경우의 최대값은 10C5 = 252이기 때문에, 모든 조합에 대해 BFS로 탐색해도 시간초과가 발생하지 않을 것이라 생각했다. [ 풀이 방법 ] 1. 재귀 함수를 이용해 문제에서 제시된 바이러스의 위치 중 M개를 골라 저장한다. 2. M개의 위치를 모두 우선순위 큐에 넣고 BFS를 시작한다. - 바이러스가 확산된 시간 순서대로 탐색될 수 있도록 우선순위 큐를 사용했다. - 2차원 배열을 만들고 -1로 초기화 한 뒤, 바이러스가 확산되어 각 칸에 도착할 때까지 걸린 시간을 저장했다. 3. BFS가 종료된 후 2차원 배열을 확인하여, 배열에서 가장 큰 값과 ..