알고리즘

오랜만에 알고리즘을 풀었습니다.이런 류의 Union-Find 문제가 종종 보이길래 빠르게 포스팅합니다.  문제 접근이번 문제의 경우 처음부터 알고리즘을 보고 풀었습니다.. 클래스 5의 문제들 중 비트마스킹이 너무 많습니다.이분탐색, 분리집합 스타트였다는 점 참고해주세요. 우선 풀면서 '공항' 문제와 매우 유사함을 느꼈습니다. 이진탐색인데 뭔가 체킹을 필요로 하는?(기존에 이 문제 못풀었습니다) 시간 단축의 핵심은 Target K 숫자보다 큰 수 중 가장 작은 수를 이진 탐색으로 간단히 찾고그 수가 아직 사용하지 않은 수면 좋겠으나만약 사용된 경우에는 그 수보다 큰 수들 중 사용되지 않은 가장 작은 수를 빠르게 찾는 것에'분리 집합' (Union Find) 알고리즘을 사용하는 것이라고 생각했습니다. 한칸씩..

문제 접근 가장 긴 증가하는 부분 수열1에서 N 조건이 크게 증가한 문제입니다.  N이 10**6이므로 시간복잡도 N^2의 경우 꿈도 꿀 수 없습니다.사실 처음엔 기존에 풀었던 스카이라인 문제처럼 스택을 이용해야 하나? 라는 생각으로 접근했는 데, 위치 정보(특히 가장 최근의 정보)를 사용할만한 그렇다할 이유가 없었습니다.  그래서,, 알고리즘 분류라는 힌트를 봤더니 이분탐색을 사용해야 한다고 하더군요. N*logN 풀이 인것은 알고 있었습니다만, 이걸 바탕으로 이분 탐색이라는 풀이 방법을 생각해내진 못했습니다. 각설하고, 이분탐색을 어떻게 이용해야 할까?  저 같은 경우 풀이를 할 때, 극단적인 케이스에서 풀이 방법을 도출하는 걸 좋아하는 데 이번 문제의 경우10 20 1 2 3 30 이라는 케이스를 ..