DisjointSet4 BOJ3830 교수님은 기다리지 않는다 3830번 교수님은 기다리지 않는다 1번부터 N번까지의 샘플에 대해 두 샘플의 무게 차이 정보가 주어질 때 교수님이 요구한 두 샘플의 무게 차를 구할 수 있으면 출력하고 구할 수 없으면 UNKNOWN을 출력한다 Disjoint Set Union & Find를 이용하는 문제인데 edge에 cost가 있다. 분리집합 문제는 여러 개 풀었었는데 가중치가 있는 건 처음 풀어봐서 꽤 헷갈리고 오래 걸렸다. scanf,printf보다 cin,cout이 훨씬 빠르고 편했다. par[N] N개 샘플의 부모 (set number) w[N] N개 샘플의 set 내 무게 (부모 무게를 0으로 했을 때의 무게) ! a b c : b가 a보다 c그램 무겁다. a와 b를 union한다. 1. a,b의 부모 para,parb를 구.. 2021. 6. 19. 2019 카카오 개발자 겨울 인턴십 문제 ② 2019 카카오 개발자 겨울 인턴십 #4 징검다리 건너기 오래 고민하고 겨우 푼 다음 정확성 효율성 다 발리고 질문하기 참고해 이분탐색임을 깨달음...... 아효 이렇게 간단히 풀리는 것을 더보기 무려 스택을 이용해 풀어봤지만 효율성은 둘째치고 정확성이 해결되지 않앗음 흠 int l=1, r=INF; int mid=(l+r+1)>>1, cnt=0; while(l=mid) cnt=0; else { cnt++; if(cnt>=k) { ava=false; break; } } } if(ava) l=mid; else r=mid-1; mid=(l+r+1)>>1; } answer=mid; #5 호텔 방 배정 disjoint set으로 풀었는데 수의 범위때문에 hash한 번 해줬다. 처음엔 새로운 숫자에 대해 {인덱스.. 2021. 5. 5. KMP DP 트리 그래프 기하학 최근 푼 문제 1701 Cubeditor KMP idx(0~N-1)부터 N까지의 부분문자열에 대해 Pi를 구한다. idx에 대하여 최대 Pi값 - idx = 두 번 이상 나오는 가장 긴 부분문자열의 길이 * Pi를 구하는 시작점의 인덱스가 0이 아님에 주의해서 풀면 됨 16900 이름 정하기 KMP 주어진 문자열 S가 최소 K번 부분문자열로 등장하는 새로운 문자열 길이의 최솟값을 구한다. Pi를 구해 문자열 S에서 K-1번 반복해줄 부분 문자열을 구한다. 아래는 예시 S ada 3 pi 001 => (3-2)+2*3 S abc 2 pi 000 => (3-3)+3*2 S rr 5 pi 01 => (2-1)+1*5 S abcabcabca 3 pi 0001231234 => (10-3)+3*3 1509 팰린드롬 분할 DP 주.. 2021. 4. 16. 그래프 (1) 최근 푼 문제 아니,,블로그 정리를 어떻게 해야할지 모르겠다. 15559 내 선물을 받아줘 15886 내 선물을 받아줘2 2536 버스 갈아타기 5214 환승 15559 내 선물을 받아줘 → union find (Disjoint Set) 15886 내 선물을 받아줘2 → 문자열 내 EW의 개수 2536 버스 갈아타기 → BFS 가로/세로로 움직이는 버스를 나누어 갈아탈 수 있는 버스를 찾아내는 방법을 생각해낼 것 bfs 더보기 ver[N] ver[ i ] = x=i에서 세로로 움직이는 버스들 저장 hor[N] hor[ i ] = y=i에서 가로로 움직이는 버스들 저장 vis[N] vis[ i ] = i번째 버스를 타기까지 갈아탄 최소 횟수 int bfs() { // STEP 1. 시작점을 포함하는 버스 for (inf.. 2021. 3. 15. 이전 1 다음
