재원블로그 재원블로그

이 문제는 누적합을 이용해서 푸는 문제이다. 일단 board의 최대 크기는 1,000 * 1,000 이고, skill의 최대 길이는 250,000 이다. 최악의 경우에는 skill의 모든 값이 0,0 ~ 999,999까지를 변경하는 경우이고, 이 때 250,000 * 1,000 * 1,000 이기 때문에 당연히 시간 초과가 난다. 여기서 많은 경우를 생각해봤지만, 마땅한 알고리즘이 떠오르지 않아 해설을 봤고, 새로운 개념을 알 수 있었다. 바로 누적합을 이용하는 것인데, [n1, n2] 까지의 범위 안에서 일정 숫자를 더해주고자 할 때, 반복문을 돌려 갱신하면 O(n) 시간이 걸린다. 하지만 [n1, n2 + 1] 까지 0이 저장되어있는 배열에서 n1의 위치에 더할 숫자 x를, n2 + 1 위치에 -x를..

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 이 문제는 다이나믹 프로그래밍을 이용한 행렬 계산 수 줄이기에서 사용하는 테크닉과 매우 유사하게 풀 수 있다. 일단 입력 배열에서 짝수번 인덱스는 숫자를, 홀수번 인덱스는 연산자를 나타내는 것을 확인할 수 있고, 전역 배열을 두개를 놓아 따로 배치했다. 여기서 중요한 것은 예를 들어 0번째 숫자, 1번째 숫자에 대한 연산자는 0번 인덱스이고, 2번째 숫자, 3번째 숫자에 대한 연산자는 2번 인덱스라는 것이다. 가장 중요한 점화식을 나는 다음과 같이 간략하게 생각했다. f(s, e) : max { f(s, k) + f(k + 1, e) (0

이 문제는 이행적 폐포 (Transitive Closure) 를 이용해서 풀었다. 일단 이 문제에서 사람의 최대 수가 100명이므로 O(n^4) 알고리즘까지도 충분하다. 그리고 중요한 점은 경기 결과에 모순이 없다는 것인데, 이는 유향 그래프로 나타나지는 경기 결과에서 사이클이 없다는 소리와 같고, 이는 경기 결과에 대한 그래프가 DAG 임을 나타낸다는 것이다. 처음에는 DAG 하면 위상 정렬이 떠올라 위상 정렬로 풀려고 했지만, 마땅한 방법이 떠오르지 않았다. 그러다가 incoming edge와 outcoming edge의 수를 더한 값이 n - 1이면 순위가 확실해진다는 규칙을 찾았고, 대학교 알고리즘 수업 때 배웠던 transitive closure가 생각났다. 이행적 폐포란 a -> b 이고 b ..

이 문제는 맵을 이용해서 풀었다. 내가 처음에 구현하려고 생각했던 방법은 sellCnt를 처음에 미리 다 더해서 한번에 구하는 것이었는데, 이 방법은 오답이다. 왜냐하면 나머지를 계산하는 과정에서 버림이 발생하고, 이로 인해 2, 2 를 따로 하는 것과 4 한번에 하는 것이 다르게 나올 수 있기 때문이다. 그래서 sellCnt 를 벡터로 바꿔주고, 각 enroll에 대해 인덱스를 계산하여 해당 사람으로부터 solve를 호출하여 answer에 누적하도록 하였다. #include #include #include using namespace std; #define MAX 10000 map peopleIndex; int parent[MAX]; vector sellCnt[MAX]; vector answer; vo..

이 문제는 구현이 매우 어려운 문제였다. 일단 입력이 매우 작아 이차원 배열 최대 크기가 400이고, 400 ^ 3 까지도 가능할 정도로 넉넉한 알고리즘을 짤 수 있다는 얘기이다. 이 문제에서 핵심은 키와 자물쇠를 대볼때, 키의 인덱스와 자물쇠의 인덱스가 다르다는 것이다. 이를 해결하기 위해 dy와 dx를 생각했고, 이는 자물쇠의 y, x 좌표와 키의 y, x 좌표가 얼만큼 차이나는지를 나타낸다. 처음에는 예시에 따라 dy와 dx의 값 범위를 -M과 M 사이로 했는데, 이렇게 하면 세어지지 않는 범위가 생긴다. 이는 키의 길이가 더 짧을 수 있기 때문이다. 그래서 inRange 함수로 어차피 범위에 없으면 아예 세지 않기 때문에, 넉넉하게 -N부터 N까지를 세도록 했고, 정답을 받을 수 있었다. 이 문제..

이 문제는 스택을 이용해서 풀었다. 일단 입력 배열의 최대 길이가 100만이므로 O(n) 이하 알고리즘을 사용해서 시간 안에 풀 수 있다. 이 문제에서 핵심은 임의의 두 풍선을 선택했을 때, 결국 둘 중 하나만 터진다는 것이다. 즉, 만약 1,2,3,4,5 라는 풍선이 있고 둘 중 무조건 큰 풍선만이 터진다고 하면 순서에 상관없이 1이 나오는 것처럼, 숫자가 많거나 짝수거나 홀수거나는 중요하지 않고 결국 제일 작은 값이 남는다는 것이다. 이를 이용하면, a 배열에 대해 i 인덱스에서 왼쪽에 있는 수 중 작은 수가 존재하고, 오른쪽에 있는 수 중에도 작은 수가 존재한다면 한번만 작은 수의 풍선을 터트려서는 불가능하다. 그 다음은 이 원리를 구현하는 방법인데, 우선순위 큐, 이분 탐색 등 다양한 생각을 했지..

이 문제는 투 포인터와 맵을 이용해서 풀었다. gems 배열의 최대 크기가 100,000 이므로 O(n) 시간 이내의 알고리즘을 구상해야 한다. 구간에 대한 정답을 도출해야 하므로 투 포인터를 떠올렸고, 개수에 상관없이 종류가 모두 들어가야하므로 맵을 떠올렸다. 일단 투 포인터를 사용하는 방식에는 한쪽에서 모두 시작하는 것과 양쪽에서 서로 시작하는 것이 있는데, 최소 구간이 같을 경우 시작 진열대 번호가 같아야하므로 왼쪽에서 모두 시작하는 쪽이 더 직관적이라고 생각했다. 처음에는 구간을 찾고 모든 보석의 종류가 들어있는지를 확인하기 위해 mp을 순회하면서 개수를 세는 쪽으로 하려 했으나, 이 방식은 시간 초과가 날 것이다. 만약 입력 배열이 10만이고 각 원소가 모두 다른 보석이라면, 10만 * 10만의..

이 문제는 맵, 백트래킹, 정렬을 이용해서 풀었다. 일단 입력으로 주어지는 배열들이 매우 작으므로, 백트래킹을 사용해도 시간 초과가 나지 않는다. 이 문제는 단순히 문제에서 주어진 대로 구현하면 되지만, 몇 가지 주의할 사항이 있다. 첫번째로 백트래킹을 할 때, temp와 limit가 같아질 때 cnt 맵에 +1을 하게 되는데, 이 때 temp는 정렬되어 있어야 한다. 만약 temp가 XW인 경우에, WX가 카운트되어야 하는 것이다. 두번째로, 모든 연산이 끝난 후에도 answer 배열이 한번 더 정렬되어야 한다. 이 두개만 주의한다면 구현은 어렵지 않게 할 수 있다. #include #include #include #include #include using namespace std; map cnt; v..