알고리즘/알고리즘 종류4 종류는 아니고.. 누적합, 역누적합 누적합, 역누적합 간단하다 a ~ b까지 합을 구하면된다.. 역누적합은 누적합하기전의 상태를 말한다. 배열에 a부터 b까지(어떤 배열의 누적합) k만큼 늘어난다. A[a] += k, A[b + 1] -= k 예 => 0 3 3 3 0 0 0 => 0 0 0 0 0 0 0 =>역 누적합.. => 0 3 0 0 -3 0 0 => update된 누적합 => 0 3 3 3 0 0 0관련 문제 태상이의 훈련소 생활 https://www.acmicpc.net/problem/19951 (태상이의 훈련소 생활) 소스 #include using namespace std; int n, m; int a[100000]; int b[100000]; int main() { cin >> n >> m; for (int i = 1; .. 2022. 1. 8. 파라메트릭서치 파라메트릭 서치 , 이분 탐색 다르다! 파라메트릭 서치는 딱 문장은 이렇다고한다 회적화 문제(최대, 최소를 구하는 문제)를 결정문제(답이 yes, no)로 바꾼 뒤 이분 탐색을 이용해 최적해를 찾는 알고리즘... 그그그그 이분탐색을 하는 le 2021. 12. 13. 트리, maxheap, minheap, 동적 배열, 해싱 정의 자식 부모 이렇게 트리를 형성하는데 트리에서 정의는 정점끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프입니다. 헷갈려던 개념 리프노드 리프노드는 자식노드인 줄 알았습니다. 그러나 자식을 갖고 있지 않은 노드를 의미합니다. 차수 자식의 갯수를 의미합니다 (특정 노드에 대해서) 이진트리 이진트리의 루트노드는 레벨이 1, .. , 레빌이 D인 이진트리의 노드의 갯수는 D 현재 노드랑 자식 노드들 중에서 가장 큰 값을 찾는다 자식이 더 큰 값이라면 현재 노드A와 자식노드 B랑 교체한다 교체 이후 다시 큰 값에서 다시 heapify를 진행한다 만약 현재노드가 가장 큰 값이라면 heapify 종료 n / 2 에서 1번노드까지 실행 힙만들기는 -> o(nlogn)이 걸린다 삽입 값을 삽입 할때는 일단.. 2021. 10. 23. dp.. 개념 개념 dp는 점화식의 정의를 잘 내려야한다 dp의 방식은 top -down, botton -up 방식이 있는데 top - down방식을 쓰면 점화식 조건을 그대로 쓸 수 있는 장점이 있다. dp는 어떤 것이 dp인가 -> 문제를 나눌때 문제가 겹치는 부분이 있을 수 있다 예를 들면 피보나치를 트리 구조로 나타내면 겹치는 부분들이 많다 이부분들을 메모이제이션 기법을 적용하면 빠른 시간 내에 구할 수 있다 시간복잡도 구하기 dp의 시간복잡도 구하기 -> dp 테이블의 크기(문제의 갯수) * 하나 푸는데 참조하는 부분문제의 갯수이다 2021. 8. 2. 이전 1 다음
