개발/알고리즘 & PS
-
[백준] 30022번: 행사 준비 - C++개발/알고리즘 & PS 2024. 9. 2. 01:43
https://www.acmicpc.net/problem/30022 $N$개의 물건을 적절하게 분배해서 가장 저렴하게 구매해야 한다. 예를 들어 두 상점이 각각 $1$, $5$원에 팔고 있다고 해보자. 1번 상점에서 사면 $4$만큼 이득을 볼 수 있다. 따라서 두 가격의 차이가 "잠재적인 이득"이 된다. 그리디하게 가장 큰 이득을 얻으려면 차이가 가장 큰 물건부터 우선적으로 구매해주면 된다. 따라서 차이가 큰 순서대로 정렬하고 최대한 저렴하게 구매하면 된다. #include "bits/stdc++.h"using namespace std;struct Cmp { bool operator()(pair &a, pair &b) { int g1 = abs(a.first - a.second); ..
-
[백준] 2900번: 프로그램 - C++개발/알고리즘 & PS 2024. 8. 27. 01:23
https://www.acmicpc.net/problem/2900 문제 구현을 그대로 구현하면 답을 얻을 수 있다. 하지만 시간복잡도가 굉장히 커지기 때문에 시간 초과를 받게 된다. something 함수를 호출 하는 과정에서 $O(KN)$, 합을 구하는 과정에서 $O(QN)$의 시간복잡도가 필요하다. 하지만 $N, K, Q$가 최대 $10^6$까지 커질 수 있으니 시간 제한을 만족시킬 수 없다. 구간 합구간의 합은 누적합을 사용하면 $O(1)$에 구할 수 있다. 따라서 누적합을 적용하면 $O(Q)$에 처리가 가능하다. something 호출매번 입력이 주어질 때마다 갱신하면 연산을 여러 번 반복하게 된다. 예를 들어 첫번째 원소는 항상 1씩 증가한다. 따라서 매번 업데이트 하지 말고 각 입력이 주어진 ..
-
[백준] 27583번: Hunt the Wumpus - C++개발/알고리즘 & PS 2024. 8. 27. 01:09
https://www.acmicpc.net/problem/27583 영어 문제니 간단하게 요약해보면 $10 \times 10$ 크기의 그리드에 4개의 Wumpus 가 있다.정수 $s$를 규칙에 맞춰 업데이트하고, 아래 2자리를 각각 $x, y$좌표로 삼는다.주어진 입력의 좌표로 이동했을 때 wumpus가 있다면 wumpus를 잡았다고 출력한다.가장 가까이 있는 wumpus의 맨해튼 거리를 (있다면) 출력한다.조심해 주어야 할 부분은 "The first four distinct numbers generated" 즉, $s$에서 wumpus의 위치를 만들 때 똑같은 위치가 나오면 안된다는 것이다.(당연한 건데 이걸 놓쳐서 정답률 100% 문제였는데 오답을 제출해 버렸다 ㅜㅜ). wumpus 위치 구하기$s$..
-
[BOJ] 20365 블로그2 - C++개발/알고리즘 & PS 2024. 4. 7. 13:24
https://www.acmicpc.net/problem/20365 20365번: 블로그2neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한www.acmicpc.net 아이디어번갈아가며 나오는 색을 가장 적은 횟수로 칠해야 한다. 색을 다시 덧칠할 수 있음을 이용하면 된다. 연속해서 같은 색을 칠하는 부분을 하나로 생각하고 총 $m$개의 구역으로 나눌 수 있다고 하자. 빨간색과 파란색은 $\frac{m}{2}$내지 $\frac{m}{2} + 1$개의 구역을 가질 것이다. 첫 시도에 둘 중 많은 색을 칠하고 $\frac{m}{2}$번의 색을 칠하는 경우가 최소가 된..
-
최소 신장 트리 (MST)개발/알고리즘 & PS 2024. 4. 4. 20:26
최소 신장 트리(Minimum Spanning Tree)를 이해하기 위해선 신장 트리에 대해서 알아야 한다. 신장 트리 (Spanning Tree) 그래프의 모든 정점이 이어져 있지만 사이클이 없을 때 신장 트리(스패닝 트리)라고 한다. 이름처럼 트리이기 때문에 순환관계 없이 최소한의 간선으로 연결되어 있다. 정점이 $n$개라면 $n-1$개의 간선으로 모두 이을 수 있다. 최소 신장 트리 (MST) 스패닝 트리 중 간선의 가중치 합이 가장 작은 트리이다. MST를 구하는 알고리즘은 대표적으로 크루스칼(Kruskal), 프림(Prim)알고리즘이 있다. 크루스칼 알고리즘 (Kruskal Algorithm) 순환이 생기지 않는 선에서 최대한 가중치가 작은 간선을 위주로 선택하는 알고리즘이다. 간선들을 가중치가..
-
[BOJ] 2143 두 배열의 합 - C++개발/알고리즘 & PS 2024. 4. 4. 11:28
https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 아이디어 두 수열 $A_n$, $B_m$의 연속한 원소들의 합을 $T$가 되도록 만들면 된다. 누적합을 통해 연속한 원소의 합을 빠르게 구할 수 있고 이분탐색을 통해 가능한 경우의 수를 빠르게 셀 수 있다. 부분합은 $1$부터 $i$까지의 합이고 이번 문제에서는 $i$부터 $j$까지의 합이 필요하므로 미리 나올 수 있..
-
[BOJ] 15970 화살표 그리기 - C++개발/알고리즘 & PS 2024. 4. 3. 22:30
https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 아이디어 같은 색의 점 중 가장 가까운 점을 찾아서 이으면 된다. 당연히 완전탐색으로는 시간을 맞출 수 없고 정렬을 이용하면 된다. (색, 위치) 순서로 저장해 정렬하면 같은 색끼리 원점에서 멀어지는 순서대로 모이게 된다. $n$번째 점에서 가장 가까운 점은 $n-1$번째나 $n+1$번째 점일 것이다. 코드 #include #include using namespace std; int ma..
-
[BOJ] 11508 2+1 세일 - C++개발/알고리즘 & PS 2024. 4. 1. 13:16
https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 아이디어 최소한의 값을 지불하려면 무료로 받는 제품의 가격을 최대한 크게 만들어야 한다. 다만, 무료로 받을 수 있는 제품은 3개 중 가장 싼 제품이기에 다른 두 제품이 비쌀수록 큰 할인을 받을 수 있다. 따라서, 내림차순으로 정렬한 후 3개씩 묶어 사면된다. 코드 #include #include using namespace std; int main() { cin.tie(nullptr)..