전체 글 썸네일형 리스트형 알고리즘 정리 http://gooddaytocode.blogspot.kr/2016/04/blog-post_27.html http://wondy1128.tistory.com/category/PSNote/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%A0%95%EB%A6%AC%ED%95%B4%EB%B4%8A?page=2 감사합니다. 더보기 2018-01-26 DPBFSDFS에라토스테네스의 체유클리드 호제법다익스트라벨만포드SPFA플로이드오일러 트레일/서킷LCA크루스칼disjoint-set위상정렬간선의 종류행렬의 곱셈피보나치 행렬분할정복비트마스크머지소트힙 더보기 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 ··· 31 32 33 34 35 36 37 ··· 61 다음