알고리즘 썸네일형 리스트형 13549번 13549번 - 숨바꼭질3 이 문제는 각 점을 정점으로 하고, 가중치가 다르기 때문에 BFS가 아닌 다익스트라 알고리즘을 이용해서 풀 수 있다. 나는 우선 순위 큐를 이용한 다익스트라를 이용해서 문제를 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include#include#includeusing namespace std; const int INF = 987654321;int main(){ int n, k; scanf("%d%d", &n, &k); vector dist(100001, INF); priority_queue .. 더보기 13398번 13398번 - 연속합 2 고민하다가 결국 인터넷을 뒤적이며 점화식을 보고 문제를 풀었다. 인터넷에서 본 점화식에서는 n번째 원소를 선택한다 라는 설명이 없어서.. 처음에 많이 헤매다가 slack 에 물어보고 알아냈다. 일단 점화식은 D[n][0] = n번째 원소를 선택하고, 하나도 삭제하지 않고 얻은 수열의 최대값.D[n][1] = n번째 원소를 선택하고, 하나를 삭제하고 얻은 수열의 최대값. D[n][0] = max( D[n-1][0]+v[n-1] , v[n-1] )D[n][1] = max( D[n-2][0]+v[n-1], D[n-1][1] + v[n-1]) 라는 점화식으로 문제를 풀 수 있었다. 따라서 모든 D 배열을 비교해서 최대값을 찾아야 하낟. ##실수한 점 D에 음수가 들어갈 수 있을 때! .. 더보기 11438번 11438번 - LCA2 이 문제는 저번에 풀다가 질문 게시판에 올렸는데, N의 max 값을 잘못봐서 계속 틀렸었다. LCA 2 문제는 기존의 LCA 알고리즘보다, DP를 이용해서 문제를 푸는 방식으로 속도가 향상된다. P[i][j] =노드 i 의 2^j번째 부모 라는 점화식을 세우면, P[i][j] = P[P[i][j-1]][j-1] 이라는 식을 세울 수가 있다. ( 2^4=(2^2)*(2^2) ) 과 비슷한 원리! 따라서 로직은 1. 양방향 간선으로 입력을 받기. 2. 입력받은 값을 토대로, 임의의 루트(여기선 1)를 지정하고 BFS를 이용해서 트리를 만든다.(이때, depth 값들을 저장, p[i][0] 은 parent[i] 와 같으므로 초기화를 시켜준다) 3. DP값을 바텀업 방식으로 채워준다. .. 더보기 2143번 2143번 - 두 배열의 합 완전 탐색에서 투 포인터를 이용해서 문제를 푸는 방식. 각각의 배열의 부분합을, 각각의 sum1, sum2 에 저장한 후에, 이분탐색(upper_bound, lower_bound) 를 이용해서 문제를 풀 수 있었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include#include#includeusing namespace std;vector sum1;vector sum2;void makeAll(vector X,int k,int goal){ int left = 0, right =.. 더보기 2632번 2632번 - 피자 판매 이전에 풀었던 문제와 비슷하다. 연속된 부분합의 합의 문제라고 할까? 일단 각 피자의 연속된 합을 모두 구하였다. 그래서 sum1 , sum2 배열에 저장하였다. 연속된 합이기 때문에, N제한이 1000 이므로 충분히 담을 수 있다고 생각했다. 그래서 구해진 두 연속된합의 수열을 하나씩 뽑아서 목표로 하는 값이 되도록 하면 됐다. 또한 각 피자 하나에서도 만들 수 있는 값들이 있기 때문에 , sum1,sum2 에 0을 추가해줘서 하나의 피자에서도 값이 나올 수 있다면 정답을 체크 하도록 하였다. ### 나는 풀 때 모든 조각을 구하는 makeAll 함수에서 실수가 발생했다. 피자 전체 한판을 구하는게 중복이 되게도 짜는 등 실수를 많이 했다.. 구하고자 하는 값이 크면 더 구할 .. 더보기 1208번 1208번 - 부분집합의 합2 굉장히 까다로운 문제였다. 일단 N제한이 40이다 보니, 부분집합의 갯수만 2^40 이므로 시간제한을 피해갈 수 없었다. 그래서 이 문제는 수열을 두개로 나눠서 문제를 풀어야 했다. (7453번과 비슷) 수열을 두개로 나누고 각 수열에서, 부분집합의 합을 모두 구했다. 최대 N이 40이므로 , 반절은 2^20= 백만 정도 되기 때문에 문제를 푸는데 큰 차질이 없었다. 그 다음 합이 s를 만족하도록 두 수열에서 수를 찾으면 된다. 이때 lower_bound 와 upper_bound를 이용했다. 처음에 공집합에 대한 부분때문에 문제를 계속 틀렸다. 부분집합의 합을 구할 때, 공집합을 빼고보니 나중에 다시 갯수를 구할 때 예외처리를 해줘야 할 사항이 발생했다. 그래서 그냥 공집합.. 더보기 1644번 1644번 - 소수의 연속합 1806번과 비슷한 문제인데, 소수라는 점만 바뀌었다. 소수를 구하는 방법은 에라토스테네스의 체를 이용해서 구했다. 그 다음 left , right 를 이용해서 필요없는 계산을 최대한 줄여서 경우의 수를 구했다. 실수한 점 -> 처음에 에라토스테네스의 체의 첫번째 for문을 i*i 더보기 1806번 1806번 - 부분합 이 문제는 쓸모없는 계산을 줄여서 시간을 줄이는 완전탐색을 연습하는 문제 인 것 같다. 그냥 2중 for문으로 break 문을 넣어줘도 AC를 받긴했지만, 아래 방법으로 푸니까 속도가 10배이상 줄어들었다. 아무래도 2중 for문으로 풀 때는 sum값을 계속해서 재계산 했는데, 이 방법은 sum 값을 계속 유지하기 떄문에 그런 것 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include#includeusing namespace std;const int INF = 100001;int main(){ int n, m, ans = INF; scanf("%d%d", &n,&m); vec.. 더보기 이전 1 ··· 19 20 21 22 23 24 25 ··· 46 다음