본문 바로가기
반응형

알고리즘/SW EXPERT

4112. 이상한 피라미드 탐험 4112. 이상한 피라미드 탐험 BFS 문제였기 때문에, 각 노드간에 이동할 수 있는지 여부만 추려내면 되는 문제였다. 근데 나는 딱히 방법이 떠오르지 않아서 약간 노가다 식으로 진행했다. 일단 1인경우, 맨 왼쪽 대각선인 경우, 맨 오른쪽 대각선이 경우, 그외 이렇게 나누어서 문제를 풀었다. 중복계산을 피하기 위해 tc안에 들어가기 전에, 각 숫자들을 for문으로 돌면서 해당하는 라인과 왼쪽인지 오른쪽인지를 판단하도록 했다. 이때 1은 왼쪽,오른쪽 둘다 걸쳐 있다고 체크를 해줬다. 그리고 BFS를 돌면서, 다음 정점을 찾을 때는 1인지,왼쪽대각선인지,오른쪽대각선인지, 그 외 경우인지 나누어서 함수를 진행했다. 그리고 사실 이동할 때 1이상 1만이하인지를 체크해줘야 하는데 귀찮아서 배열을 아주 크게 만들.. 더보기
4111. 무선 단속 카메라 4111. 무선 단속 카메라 거리의 모든 합은 결국 정해져 있기 때문에, 가장 큰 값부터 없애나가면 된다고 생각했다. 즉 예제에서 1-3-6-7-9 에 카메라가 있다면, 그 사이의 거리는 2-3-1-2 가 된다. 이때 k값이 2라면, 2 3 1 2 중에서 3만을 제거하면 구간이 두개가 되고 2 , 1-2 가 되어 합 5가 정답이 된다. 이런식으로 정렬해서 k의 값에 따라 가장 큰 값을 차례로 제거해주면 된다. 따라서 1. 카메라가 있는 곳의 위치를 파악한다. 2. 중복 계산을 피하기 위해 다시 카메라의 위치를 통합하여 v 벡터에 담는다. 3. v벡터를 이용해서 카메라 사이의 거리 값을 모두 diff 벡터에 담는다. 4.diff를 정렬하여 k값에 따라 앞에서부터 더해간다 //배운점 처음에 size선언을 하.. 더보기
3124. 최소 스패닝 트리 3124. 최소 스패닝 트리 오랜만에 크루스칼 알고리즘을 사용해서 최소 스패닝 트리 문제를 풀어봤다. 최소 스패닝 트리는 간선을 가중치에 따라 오름차순으로 정렬하고, union-find 를 이용해서 추가할지 말지를 결정하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include#include#includeusing namespace std;int p[100001]; int find(int a){ if (a == p[a]) { return a; } else { return p[a.. 더보기
4050. 재관이의 대량 할인 4050. 재관이의 대량 할인 할인을 최대한 받기 위해서는 큰 값들을 할인 받아야 한다. 따라서 나는 가격을 정렬하고, 리버스 해서 가장 큰 값부터 3개씩 묶어나가는 방법으로 문제를 풀었다. 12345678910111213141516171819202122232425262728293031323334353637383940#include#include#includeusing namespace std; int c[100001];int n, ans;void init(){ ans = 0; memset(c, 0, sizeof(c));}int main(){ int tc; cin >> tc; for (int t = 1; t > n; init(); for (int i = 0; i > c[i]; } sort(c, c + n.. 더보기
4053. 전국민 건강 프로젝트 4053. 전국민 건강 프로젝트 시뮬레이션 문제 같은데 푸는데 꽤나 시간이 걸렸다.. 문제의 조건을 보니 시간초과를 해결하는게 가장 중요해 보였다. 맨 처음에는 -> 와 > tc; for (int t = 1; t > N >> T >> Q; for (int i = 0; i > per[i].p >> per[i].d; if (per[i].d == 2) { per[i].d = -1; } } // -> = p2) { if (i - 1 >= 0) { q.push(i - 1); } if (i + 1 = 0) { q.push(i - 1); } if (i + 1 더보기
3809. 화섭이의 정수 나열 3809. 화섭이의 정수 나열 나는 그냥 N이 1000개가 최대이기 때문에, 1000의 자리 수 이전에서 최소값이 무조건 발생한다고 생각했다. 즉, N=1000 이 되어 숫자가 1000개가 있을 때 숫자가 1000개가 생길 것이다. 그렇다고 할때 수가 1개인 예를 들어 0,1,2,3,4~,9 는 1000개가 나오게 된다. 수가 2개인 예를 들어 10,11,..,99 는 999개가 나오게 된다. 수가 3개인 100,101,...999 는 998개가 나오게 된다. 수가 4개인 1000,1001,...9999는 997개가 나오게 된다. 즉 수가 4개인 값들은 997개가 나와도 절대 1000~9999를 다 나타낼 수 없기 때문에 최소값이 무조건 발생하게 된다. 나는 이점을 이용해서 main 에서 for문을 4까.. 더보기
3503. 초보자를 위한 점프대 배치하기 3503. 초보자를 위한 점프대 배치하기 로직은 우선 점프대를 오름차순으로 정렬한다. 그리고 가장 낮은 점프대(0번째)를 가운데에 넣고, 양 옆으로 번갈아 가면서 오름차순의 점프대를 넣어주면 된다. 양옆으로 넣어줘야 하기 때문에 deque 를 사용해서 문제를 풀었다. 이렇게 푼 이유는 만약 점프대가 오름차순으로 있다면, 원형이기 때문에 결국 가장 큰 점프대와 가장 낮은 점프대의 차이가 답으로 나올 것이다. 하지만 가장 낮은값을 가운데에 넣고, 그 앞뒤로 순차적으로 삽입을 하면, 평균적인 차이가 가장 낮게 나올 것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657.. 더보기
3289. 서로소 집합 3289. 서로소 집합 union-find 를 이용해서 문제를 쉽게 풀 수 있었다. 같은 부모를 가지고 있으면, 1을 출력하고, 그렇지 않으면 0을 출력하면 되는 문제. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include#include#includeusing namespace std; int p[1000001];void init(){ for (int i = 0; i tc; for (int t = 1; t > n >> m; for (int .. 더보기
반응형

티스토리툴바