전체 글
-
[BOJ] 9344번 : 도로 - C++개발/알고리즘 & PS 2024. 10. 6. 21:38
$N$개의 도시를 가장 적은 비용으로 이어야 합니다. 즉, MST를 구하는 문제입니다. 그런데 특정 도시 $p, q$를 연결하는 도로를 사용하면서 MST를 만들 수 있는지를 판단하는 문제입니다. 단순하게 접근하면 일반적인 MST를 수행하면서 p, q를 잇는 도로가 사용되는지를 판단하면 되는데, 만약 모든 간선의 비용이 같다고 생각해 봅시다. p, q 도로를 사용하지 않고도 같은 비용으로 MST를 만들 수 있습니다. 따라서 pq 도로와 길이가 같은 도로들 중에서 pq 도로가 우선적으로 사용되도록 해야 합니다. priority queue의 정렬 함수를 적절하게 바꿔 정렬하면 구현할 수 있습니다. 조심해야 할 부분은 priority queue의 정렬 함수는 sort에 사용하는 정렬 함수랑 반대라는 것입니다. ..
-
[백준] 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). 주어진 점들" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/15970" data-og-url="https://www.acmicpc.net/problem/15970" data-og-image="https://scrap.kakaocdn.net/dn/cqiasE/hyVJ7hmkbA/OR5E6rjpF7R1afl63zyEvK/img.png?width=2834&height=1480&face=0_0_2834_1480"> 15970번: 화살표 그리기직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른..