190818 알고리즘 스터디

1. 3시간동안 정해진 문제 풀기(1:50~4:50) (3/8 풀기 성공)

- 스터디 내용

- A번 문제의 경우 해설 듣고 외적을 통해 쉽게 풀 수 있었다. 외적 복습하자.

- 그냥 각각 x, y, z에서 자기 빼고 나머지를 순서대로 곱하고 뺀다는 느낌으로 기억하면 됨. 반시계가 +, 시계가 –임.

- B, F번 문제는 정말 쉬운 수학 문제였으므로 패스(그냥 에라토스테네스의 체, 피보나치)

- C번 문제는 나는 segment tree로 구해서 풀었는데, Disjoint set을 이용해서 부모 업데이트 하는 식으로 다시 풀어봐야 함

- D번 소각로는 특정 구간의 값을 0으로 바꾸는 맨 첫 번째 연산을 lazy propagation으로 구해야 한다고 함. 이거 공부해야 함. 그거 말고 나머지는 queue로 구현. 구현이 좀 까다로운 문제임.

- E번은 내가 2시간동안 붙잡고 못풀었는데 이미 방문한 상태를 체크할 때 DP를 써줘야 함. DP를 써서 다시 풀어볼 것.(각 칸마다 초, 중, 종성으로 쓰일 때 제일 적게 쓰이는 글자 수를 저장해두면 됨.)

- G번은 brute force문제. 5x5에 4x4짜리 재료를 넣는 경우의 수가 4개이고, 이걸 90도씩 rotate한다고 생각해보면 총 16가지 경우의 수가 나오고 maximum 10개의 아이템이 나오는데 그 중 3개의 순서 조합을 생각하면 16X9X8가지의 경우의 수가 나온다. 총 300만 정도라서 시간 초과는 안걸림.

- H번은 LCA 문제임. 2^17까지 자기 위에 부모를 저장하면 됨. 내 2^i번째 위 부모를 저장하는 방법은 2번 위는 1번위의 1번위와 같고 4번 위는 2번위의 2번 위와 같다 이런 식으로 해주면 총 18번만 부모를 업데이트해주면, 모든 노드의 1,2,4,...,2^18위의 부모를 체크할 수 있음. 그 부모까지 가는 데 필요한 weight도 동시에 더해서 저장한 후 LCA를 이용해서 u->v까지의 weight = u->LCA, v->LCA까지의 weight의 합으로 구할 수 있음. k번째 노드를 구하는 방법으로는 u와 v의 LCA보다 k가 작으면 u에서부터 O(logn)으로 올라가서 구하고, k가 더 크면 v에서 O(logn)으로 올라가서 구하면 됨.

 

2. 9시 앳코더(#138)

- 처음 앳코더 풀어봤는데 코포보다 깔끔한 문제 스타일이 마음에 듬. 문제 설명도 더 직관적으로 되어 있고.

- A, B : 너무 쉬워서 패스

- C : n-1번 두 수를 뽑아서 avg시켜서 n개의 수를 합했을 때 최댓값을 구하는 거. 그리디 문제. 좀 고민했는데 avg할 때 보면 N=3일 때를 예로 들면,

니까 계속 더해지는 거 입장으로 보면 계속 최종 합에서 비중이 작아지는 걸 볼 수가 있음. 그래서 제일 작은 수부터 더한다는 게 포인트. 그래서 받은 배열을 sort한 후 순서대로 한 개씩 기존의 값과 같이 평균 내주면서 더해주면 정답!

- D : 트리가 간선 형태로 주어졌을 때 특정 노드를 root로 하는 subtree 값들은 모두 업데이트시킨 후 맨 마지막에 모든 노드를 출력하는 문제. 단순히 진짜 더하다가는 O(N*Q) = O(n^2)이라 n=10만이라서 무조건 시간초과나는 문제. 그러므로 합을 해줄 때 Lazy한 방법으로 더하는 것이 포인트.

1) 내가 사용한 방법 : Segment tree + Lazy Propagation

오늘 lazy propagation 방법이라는 걸 공부해야겠다고 했는데 때마침 사용할 기회가 와서 대회 중간부터 그냥 공부하는 걸로 노선을 바꿈.

(1) 우선 간선 형태로 주어지는 트리 정보를 Seg tree로 바꾸기 위해서는 dfs를 한 번 돌려줘야 한다. DFS의 parenthesis 구조 때문에 dfs 방문 시작 순서와 방문 끝 순서를 저장하면 항상 부모의 방문 시작과 끝 interval 안에 자식의 방문 시작과 끝 interval이 포함되게 된다. 그렇게 해서 input으로 부모 노드가 나오면 부모의 시작과 끝 구간 안에서 부분 합이나 그런 걸 적용할 수 있는 여지가 생기는 것임!

이후 자식 노드를 출력할 때는 자식의 시작 순서 값만 찍어서 가져오면 됨.

(2) Lazy propagation

Seg tree를 구간 단위로 동시에 업데이트 해야한다고 할 때 쓰는 방법! 곧바로 업데이트하지 않고 일단 Lazy라는 배열을 seg tree의 노드 개수만큼 만들어줌. 그렇게 하고 난 뒤 업데이트할 때 업데이트 해야하는 값을 a라고 하자. 해당 구간이 모두 포함되는 노드를 만나면 그 노드에는 a*(end-start+1)만큼 값을 업데이트하고 그 노드의 자식 노드(2i+1, 2i+2)의 lazy 값을 a라고 설정해줌.(자식 노드들은 업데이트가 안되는 거임!) 그리고 나서 그 위에 노드들은 tree[node] = tree[node*2+1] + tree[node*2+2]로 깔끔하게 업데이트. 자식 노드들에 남겨진 lazy값들은 실제로 쿼리할 때 업데이트시켜줌.

2)번 방법을 듣고 나니 너무 복잡하게 푼 것 같아서 눈물이 앞을 가리지만 그 전부터 레이지 propagation을 공부해야겠다는 생각은 이미 했었으니 좋은 기회였던 걸로!^^;

 

2) 그냥 단순 DFS에 lazy하게 적용하는 방식. 매우 깔끔하고 간단하게 할 수 있음.

트리의 노드에 대한 lazy 배열을 만든 후 어쨌든 쿼리를 한번에 받은 다음에 각 노드마다 lazy값이 있는데 dfs를 돌리면서(자기 부모가 누군지 알 수 있도록 argument로 넘겨줌) 자기 부모를 제외한 나머지 노드한테 자기 lazy 값을 +=해주는 식으로 하면 결국 O(n)으로 업데이트가 가능.

 

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

- 오늘 스터디 진행했던 거 다시 풀어보기 : C, D, E, G, H

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

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

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

 

다짐할 것

1) 느리더라도 확실하게 이해하기!

2) 안되는 문제는 꾸역꾸역 해내는 것이 중요하다!

 

느낀 것

1) 별건 아니지만 내가 생각한 로직대로 꼼꼼하게 푼 다음에 한번에 AC받을 때의 짜릿함을 느끼는 횟수가 훨씬 많아졌다! 여전히 뉴비지만 한번에 거의 통과하고 내 스스로 꼼꼼하게 점검하면서 정답률 자체는 좋아진 듯.

2) 대학원 준비 때문에 알고리즘을 복습하면서 사상누각같은 기분은 안듬. 이제 다양한 문제 풀고 오답노트 쓰면서 공부하면 될 듯. 기본 개념이 복습이 안되있어서 그 전이 좀 막막했던 듯. 이걸 이제 알았다니ㅠㅠ. 종만북 보지 말고 진작에 수업복습부터 쭉 하고 할 걸. 물론 종만북 보던 시간이 헛되었단 생각은 안듬.