190822 알고리즘 스터디 숙제

190822_백준 숙제 공부

BOJ #10775 (1-C)

Disjoint set을 이용한 문제. 지난번에 세그먼트 트리로 푼 문제임.

자기 부모가 0(존재하지 않는 게이트, 1번까지 다 돌아도 더 이상 넣을 수가 없음)이 아니면, 게이트를 도킹하면 된다.

맨 처음에 자기 부모는 자기 자신을 해두고, 자기 부모가 0이 아니면 자기 부모랑 자기부모-1(아마 빈칸이겠지)을 union해서 그 앞에 빈칸이 아니면 자기부모-1의 부모를 또 찾으러 가니까 어쨌든 가장 마지막에 비어있는 1~N 사이의 칸을 찾아 주는 것.

==> 결국 부모-1과 union하는 이유는 결국 항상 부모 = 빈칸이 되도록 하기 위해서

뭔가 좀 생각하기 복잡하지만 코드는 그냥 disjoint set 쓰면 됨

 

스터디 오늘의 목표

1) H

- 부모 저장 배열 만들기

각자 자신의 2^i번째 조상을 저장하는 배열을 ac[MAX_NODE][20]으로 저장. 왜 20이냐고 하면 2^17 = 131072라서 여기까지하면 모든 부모를 다 나타낼 수 있기 때문임. 배열은 넉넉하게 20으로 잡아줌. 그래서 MAX_NODE에 log2를 씌워주면 log2(100000) = 16.6이 나와서 여기서 버림해주면 16(버림 안해줘도 상관은 X)

- depth 저장하기(lca를 위함) : depth[MAX_NODE]로 저장

==> 부모 저장 배열을 DFS를 통해서만 드는데 DFS를 통해서 자기 자신의 부모가 누군지 전달을 받고 그와 동시에 자기 부모의 정보를 바탕으로 ac배열을 만듬. dfs를 계속 해 나가다보면 그게 됨.

깊이가 같아질 때까지 계속 올려보고 깊이가 같아지면, 이제 그들의 조상들을 max_level부터 찬찬히 살펴보면서 같은 노드를 가리키기 직전의 노드에서 멈출 수 있도록 한다.(2^i단위로 하니까 일단 조상 같다가 달라지는 시점에서 애들을 올리고, 결국맨 마지막에는 lca 직전 노드까지 가서 lca는 그거의 ac[a][0]가 돼서 출력이 되는 구나.

- 어쨌든 LCA를 구하고 나서 쿼리 문제를 풀어보면, 1번 쿼리는 u~v까지 총 비용을 다 더하는 것이므로 시작점에서부터의 거리를 다 알고 있는 weight[u] + weight[v] - 2*weight[lca]로 구할 수 있음.

- 2번 쿼리의 경우, k를 이진수로 나타냈을 때를 생각해서 k미만의 level들을 다 올라가면서 k에서 2^i를 빼주고(1<<i) k를 올라가면 됨. 단, c~ lca ~ d사이로 갈 때 c~ lca 사이에 k가 있으면 그냥 k-1번만 올려주면 되지만, lca ~ d 사이에 있을 때는 전체 경로 – (k-1)을 해주어야 하므로 전체 경로 길이는 depth[u] + depth[v] - 2*depth[lca]로 구할 수 있으니 그렇게 해서 ac배열을 이용해서 원래 수를 (k-1)번 올려버리면 끝.

 

2) E

결국 bfs 하되 dp라는 게 이전 상태 기준으로 하는 거임! 어이없게 문제 조건 숫자를 잘못 입력해서 한 30분 더 헤멨다..

 

3) G

그냥 솔직히 구현이 약간 노가다스러운 것 빼고는 아무것도 안어려웠음. 뭔가 문제가 길다고 해서 어렵게 생각하지 않아도 되는 것 같다. 그냥 9중 포문(N(N-1)(N-2)*16*16*16)을 다 해주면 되는 거. 이걸 통해 얻은 수확은 vector 다차원 배열 선언, 복사하는 방법을 복습함.

- 3차원 벡터 선언 vector<vector<vector<int> > > a(10, vector<vector<int> >(5, vector<int>(5, 0)));

- c++식 배열 복사 방법 copy(a1.begin(), a1.end(), a2.begin());

- rotation할 때 식은 (i, j) → (j, 3-i)로 mapping.

 

숙제 until 수요일 & 공부할 것들

- D번 디버깅해서 오기

- 앳코더 E, F 도전해보기 & 좀 더 생각해보기

-백준 세그먼트 트리 문제 풀어보기 & 구현 다시 공부하기(나 아직도 세그먼트 트리를 확실하게 이해한 기분이 안든다.)

-묵혀왔던 숙제하기(코드 포스)