본문 바로가기

PS - 알고리즘

 (48)
13537 - 수열과 쿼리 1 step 1더보기원래 있는 수열을 쿼리로 변환해 봅시다.그럼 문제는 다음과 같이 바뀝니다. 길이 $N$인 수열이 주어집니다. 처음 수열의 값은 전부 0입니다.$1 i k$ : 수열 $i$번째 위치에 $k$를 추가합니다.$2 i j k$ : $A_i, A_{i+1}, ..., A_j$로 이루어진 부분 수열 중에서 $k$보다 큰 원소의 개수를 출력한다.step 2더보기$2 i j k$를 봅시다. 수열에서 $k$ 이하인 숫자들은 아무 의미가 없습니다. $k$ 초과인 숫자들은 $k$보다 크다는 것이 중요하지 그 숫자의 값은 중요하지 않습니다.그럼 이 쿼리들을 $k$가 큰 순서로, $k$가 같으면 2번 쿼리가 먼저 나오도록 정렬해 봅시다. 세그먼트 트리를 하나 만든 다음 1번 쿼리고 오면 $i$에 1 추가, 2번..
1055 - 끝이없음 step 1더보기max - min은 대략 100만큼 차이 납니다. 그럼 "i번째 문자가 무엇인가"라는 문제를 i가 min, min+1, ..., max일 때까지 해서 총 100번 물어보면 됩니다. 앞으로의 설명에서는 i번째 문자를 구하는 데에 집중하겠습니다.step 2더보기$ 기호가 1개일 때와 2개일 때로 나눌 수 있습니다. $가 1개일 때 먼저 처리하겠습니다. S를 $ 기준으로 앞과 뒤로 나눌 수 있습니다. $ 앞을 (1), $ 뒤를 (2)라고 하면 (1) (1) (1).... (1) (1) (입력) (2) (2) (2)... (2) (2) 로 만들어 집니다. (1)과 (2)는 (실행시킨 횟수)만큼 반복됩니다. (1)과 (2)의 길이를 구해두면 쉽게 풀 수 있습니다.step 3더보기N번 실행시켰을 때..
6549 - 히스토그램에서 가장 큰 직사각형 step 1더보기정답이 되는 직사각형은 위, 아래, 좌우로 더이상 확장이 불가능한 상태여야 합니다.히스토그램의 각 막대에 대해서 '해당 막대를 완전해 포함할 때 직사각형의 최대 면적'을 구한 다음 그 중 가장 큰 것을 고르면 됩니다.step 2더보기막대가 정해졌다면 사실 높이가 정해진 것과 같습니다. 그럼 좌, 우로 얼마나 확장 가능한지만 남아 있습니다. 오른쪽으로만 확장한다고 생각해 봅시다.스택을 하나 만든 다음 왼쪽부터 오른쪽으로 쭉 보면서 다음 규칙에 따라 스택에 막대를 넣고 뺍니다.스택의 가장 위 막대의 높이가 지금 보고 있는 막대의 높이보다 크다면 스택에 있는 막대는 오른쪽으로 더이상 확장하지 못한다는 뜻입니다. 해당 막대를 스택에서 빼고 그 막대가 오른쪽으로 얼마나 확장했는지 기록합니다.스택의..
MCMF(min cut max flow) 어떤 그래프가 있고 해당 그래프의 간선에 가중치가 있다고 해봅시다. 이 그래프에 대해 다음 두 문제를 생각해 봅시다.  그래프가 하나 주어집니다. 주어진 그래프에는 $N$개의 정점과 $M$개의 파이프가 있습니다. 각 파이프는 물을 한쪽 방향으로만 흘릴 수 있습니다. 각 파이프의 흐를 수 있는 양은 다릅니다. 시작 정점과 끝 정점이 주어졌을 때, 시작 정점에서 끝 정점으로 최대한 많은 양의 물을 보내고자 합니다. 얼마나 보낼 수 있습니까? 그래프가 하나 주어집니다. 주어진 그래프에는 $N$개의 정점과 $M$개의 간선이 있습니다. 각 간선은 한쪽 방향으로만 지날 수 있습니다. 각 간선에는 해당 간선을 끊는 데 드는 비용이 있고 이 비용은 다릅니다. 시작 정점과 끝 정점이 주어졌을 때, 최소한의 비용으로 간선..
8155 - Postering step 1더보기더보기가로 폭이 얼마든 상관 없습니다. 전부 1로 생각합니다.만약 모든 빌딩의 높이가 다르다면 답은 $N$입니다. 결국 높이가 같은 것들을 한번에 처리하는 것이 중요합니다.step 2더보기더보기만약 어떤 두 건물의 높이가 같고 그 사이에 있는 모든 건물이 이 건물의 높이보다 크다면 두 건물은 하나의 포스터로 처리할 수 있습니다. 이 과정은 스택을 이용해서 처리할 수 있습니다. 지금 보는 건물이 현재 스택의 top보다 크면 넣고 작으면 스택을 pop해줍니다. 만약 스택의 top과 지금 건물의 높이가 같다면 이 두 건물 사이 모든 건물이 두 건물보다 높다는 뜻입니다. 이러한 건물의 개수를 세고 $N$에서 빼주면 됩니다.코드더보기더보기#include #include #include #inclu..
네트워크 플로우 네트워크 플로우 알고리즘은 직관적이지도 않고 증명도 어렵고 플로우를 사용하는 문제인 걸 알아도 "이게 플로우라고?"라는 생각이 드는 알고리즘입니다. 최대한 직관적으로 이해할 수 있도록 해 보겠습니다.그래서 뭐하는 알고리즘인가?다음과 같은 문제를 생각해 보겠습니다.그래프가 하나 주어집니다. 주어진 그래프에는 $N$개의 정점과 $M$개의 파이프가 있습니다. 각 파이프는 물을 한쪽 방향으로만 흘릴 수 있습니다. 각 파이프의 흐를 수 있는 양은 다릅니다. 시작 정점과 끝 정점이 주어졌을 때, 시작 정점에서 끝 정점으로 최대한 많은 양의 물을 보내고자 합니다. 얼마나 보낼 수 있습니까? 예를 들어 다음 그래프 같은 경우(s부터 e까지) 다음과 같이 물을 흘리면 15만큼 흘릴 수 있습니다. 시간복잡도 같은 것들을 ..
백준 30481 - Forward and Backward 문제 번역하나의 숫자 $N$을 입력받습니다. $N$을 $X$진수로 변환했을 때, 팰린드롬이 되는 모든 $X$값을 출력합니다. 만약 이러한 $X$값이 없다면 *을 출력합니다.step 1더보기$N$이 2일 땐 *을 출력합니다. 그 외의 경우에는 $N-1$진수로 변환하면 항상 $11_{(N-1)}$이 나오므로 답이 1개 이상 존재합니다.변환 결과가 2자리인 경우와 3자리 이상인 경우로 구분해 보겠습니다. 3자리 이상인 경우부터 해결하겠습니다.3자리 이상인 경우에는 직접 계산합니다. $X$를 2부터 시작하여 $X$진수로 변환한 후 팰린드롬 여부를 확인합니다. $X>=\sqrt{N}$ 일 때 2자리가 되므로 이 과정은 $O( \sqrt{N} )$만큼 걸립니다.step 2더보기2자리인 경우 $X>=\sqrt{N}$..
백준 1118 - 색칠 2 step 1더보기색칠되지 않은 면적을 구하는 것이지만 전체에서 색칠된 영역을 빼는 것으로 생각하고 색칠된 영역의 면적을 구하겠습니다.$K \le 50,c[i] \le 1000$입니다. $K$를 잠시 무시하고 한번만 색칠한다 했을 때 만들어지는 영역들을 생각해 봅시다. 영역의 개수가 최대한 많아지도록 만든다면 다음과 같이 $1001 * 2$개의 영역이 만들어 질 것입니다.각 영역의 경계를 생각해 봅시다. 세로축과 평행한 경계가 4개, 가로축과 평행한 경계가 2002개 만들어 질 것입니다. 이를 세로 경계, 가로 경계라고 하겠습니다. $K$가 50이므로 전부 색칠하면 최악의 경우 세로 경계 200개, 가로경계 100100개가 만들어집니다. 이제 $200 * 100100$로 이 문제를 해결하면 됩니다. ste..
백준 31749 - 조작 step 1더보기$N$이 홀수일 때는 답이 0입니다.$a_1, a_2$를 조작하여 $a_1$을 $0$으로 만듭니다.$a_2, a_3$를 조작하여 $a_2$을 $0$으로 만듭니다.이런 식으로 $a_{n-1}$까지 $0$으로 만듭니다. 그럼 $a_n$에만 값이 들어있을 것입니다. 이제부터 나머지 숫자들을 $a_n$에 맞출 것입니다.$a_{n-2}, a_{n-1}$을 조작하여 두 숫자를 $a_n$로 만듭니다.$a_{n-4}, a_{n-3}$을 조작하여 두 숫자를 $a_n$로 만듭니다.이런 식으로 $a_1, a_2$까지 조작해서 모든 숫자를 $a_n$으로 만듭니다.step 2더보기위의 3번 과정까지 따라 하면 마찬가지로 $a_n$에만 값이 들어 있습니다. 백준 예제입력에 위 과정을 적용하면 0 0 0 0 0 1..
백준 31741 - 구간 덮기 step 1 더보기 선분을 1개, 2개, 3개 쓰는 경우에 대해 각각 답을 구하고 그 중 가장 좋은 것을 출력하면 됩니다. 1개를 쓰는 경우 : 전체를 다 덮는 선분이 있어야 합니다. 이 경우 답은 0입니다. 선분들을 (A)시작점을 포함하는 것, (B)시작점과 끝점 사이에 있는 것, (C)끝점을 포함하는 것 3 종류로 나눌 수 있습니다. 지금부터 (C)에서 고른 선분을 $C$, 그 선분의 시작점을 $C_x$, 끝점을 $C_y$ 이런 식으로 쓰겠습니다. 2개 쓰는 경우 : (A)와 (C)의 조합으로 만들 수 있습니다. $C$ 기준으로 $A$를 찾는다고 할 때 (A)에 있는 선분들 중 끝점이 $C_y$보다 큰 선분들 중 끝점이 가장 작은 선분이 최적의 선분입니다. set에 A의 끝 점을 전부 넣어두면 쉽게 ..

티스토리툴바