data 영역이 아닌 함수 내의 스택 영역에 약 백만 개의 int 배열을 선언할 때 오류가 발생한다 함수 내에서 선언되어 사용되는 배열의 경우 배열 자체가 스택 영역에 생성되고 함수가 호출될 때마다 해당 배열을 위한 메모리를 새로 생성하고 초기화하는 작업을 하기 때문에 배열의 크기가 큰 경우에는 다른 방법을 사용해야 한다. 이론적으로는 지역변수의 영역 크기는 제한되어있지 않지만 시스템에 따라 하드웨어적인 제한이나 스택 운용의 효율을 높이기 위해 스택의 크기를 제한하기도 한다. 그렇게 때문에 함수 내에서 선언되는 배열의 크기가 과도하게 큰 경우 프로그램이 강제 종료될 수 있다. 그렇기 때문에 배열의 크기가 조금이라도 큰 경우에는 힙 영역이나 data 영역을 사용하는 것이 올바르다

대표적인 Disjoint-set 문제 문제: https://www.acmicpc.net/problem/1717 https://github.com/surinoel/boj/blob/master/1717.cpp

그리디 알고리즘으로 O(N)으로 최적화 (미제)

https://sarah950716.tistory.com/16?category=598483 1) (최솟값을 구하는 경우) 최솟값이 x라면, x이상의 값에 대해서는 모두 조건을 만족 2) (최댓값을 구하는 경우) 최댓값이 x라면, x이하의 값에 대해서는 모두 조건을 만족 1) 2)와 같이 연속적으로 조건을 만족한다면 이분탐색을 이용해 만족하는 변수값을 구할 수 있다

Union-find라고도 불리는 서로소 집합 알고리즘으로 두 노드가 같은 집합에 있는지 여부를 판별할 수 있다 Disjoint-set 문제는 두 노드의 연결 상태를 주고 마지막에 여부를 묻는다 부모를 집합의 가장 작은 번호로 기입한 후 재귀적으로 두 노드를 탐색해서 부모를 알아내고 비교할 수 있다 int getparent(int idx) { if(parent[idx] == idx) return idx; else parent[idx] = getparent(parent[idx]); } void uniongroup(int a, int b) { int ap = parent(a); int bp = parent(b); if(ap < bp) parent[bp] = ap; else parent[ap] = bp; }

우선순위 큐를 정렬하는 방법을 알아야 한다 삽입과 삭제는 O(logN)의 시간이 걸린다 문제: https://www.acmicpc.net/problem/11286 https://github.com/surinoel/boj/blob/master/11286.cpp