MungGu Story

백준 17171번, 집합의표현 문제 알아보기 1717번, 집합의 표현 문제는 disjoint-set, 서로소 집합 관련 문제입니다. 서로소 집합 개념은 MST문제을 풀때 자주 사용하는 크루스컬 알고리즘에서도 활용되는 유용한 개념입니다. 본 문제 난이도는 solved.ac기준, 골드4로 일반 코딩테스트 기준, 중후반대에 나올 수 있는 문제입니다. 시간제한은 2초, 메모리 제한은 128MB입니다. 초기에 {0}, {1}, {2}, .... {N}의 N+1개 집합이 있다고 할때, 이에 대한 합집합 연산, 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산을 출력하는 문제입니다. 이렇게까지만 문제를 보면 단순한 문제로 보일 수도 있지만, N의 입력범위가 최대 백만이란 점에서, disjoined-set 기반의 ..

백준 9421 소수상근수 문제설명 오늘은 백준 9421번, 소수상근수를 풀어보겠습니다. 소수상근수 난이도는 solved.ac기준 실버1입니다. 시간제한은 1초, 메모리제한은 256MB입니다. 본 문제의 요지는 상근수이자, 소수인 소수상근수를 출력하는 문제입니다. 상근수, 소수에 대한 사항은 위의 설명을 참고하시기 바랍니다. N이 입력되면, N보다 같거나 작은 모든 소수상근수를 오름차순으로 개행단위 출력하면 됩니다. 2 ~ N까지의 숫자 중 소수 중에서 상근수인 소수상근수를 구할때마다 출력하도록 할ㄹ 예정입니다. 여기서 눈여겨보셔야할 부분은 N의 범위입니다. N의 범이가 100만이므로, O(N^2)과 같은 시간복잡도로는 시간초과가 발생합니다. 저는 특정 범위 내의 모든 소수를 구할 수 있는 에라토스테네스의..