BOJ27 BOJ 1306 : 달려라 홍준 문제 링크 : https://www.acmicpc.net/problem/1306 언뜻 봐서는 Sliding Window + Segment Tree 또는 Multiset 로 보인다. 구간이 1칸씩 바뀌기 때문에 구간이 바뀔 때마다 Segment Tree 또는 Multiset 으로 O(log N) 쿼리를 하면 총 시간복잡도는 O (N log N) 이다. 하지만 이보다 훨씬 빠른 O(N) 풀이가 있다. deque 를 활용하면 O(N) 만에 매우 간단하게 코드를 짤 수 있다. deque 에 들어갈 것은 기본적으로 (값, index) 순서쌍, 즉 pair 이다. 현재 우리가 처리하는 구간의 인덱스가 [L, R] 이라 해보자. A[L], ..., A[R] 까지의 최댓값을 구하는 것이다. Sliding Window .. 2022. 8. 14. BOJ 1017 : 소수 쌍 문제 링크 : https://www.acmicpc.net/problem/1017 보는 순간 바로 이분매칭이 떠오른다. 하지만 이분매칭은 기본적으로 이분그래프에서 이루어져야 하기 때문에 한 번 막혔었다. 서로 다른 두 수의 합으로 생성된 소수는 무조건 홀수가 될 수 밖에 없다. 또한, 홀수는 무조건 (홀수 + 짝수) 로 만들어질 수 밖에 없다. 따라서, 이 문제는 홀수 / 짝수로 이분그래프를 형성하여 풀면 된다. 다만, 타 문제들과는 달리 첫 수와 매칭될 수 있는 수를 찾아야하기 때문에, 2 ~ N 번째 수와 1번째 수를 수동으로 매칭시킨 후 이분매칭을 실시하면 된다. 2022. 8. 14. BOJ 17167 : A Plus Equals B 문제 링크 : https://www.acmicpc.net/problem/17167 편법으로 파이썬을 쓴 문제... long long 범위의 두 자연수 A, B 가 주어졌을 때 A += A, A += B, B += A, B += B 의 네 연산을 적절히 써서 A == B 가 되게 만들라는 문제다. 이 때, 주의할 점은 꼭 최소 횟수일 필요가 없다는 것이다. A와 B가 같게만 되면 된다. 일반성을 잃지 않고, 마지막에 A 가 커져서 B와 같아졌다고 해보자. 그렇다면, A += A 가 무조건 마지막 연산이 되어야 한다. A += B 를 했는데 B 와 같아질 수 없기 때문. 여기서 조금만 더 나아가면, 마지막은 A += A 가 1번 이상 반복된 형태여야 함을 쉽게 알 수 있다. 즉 A 가 1번 이상 2배가 된다.. 2022. 8. 14. 이전 1 2 3 4 5 다음