반응형 컴퓨터 사이언스/BOJ42 190822 알고리즘 스터디 숙제 190822_백준 숙제 공부 BOJ #10775 (1-C) Disjoint set을 이용한 문제. 지난번에 세그먼트 트리로 푼 문제임. 자기 부모가 0(존재하지 않는 게이트, 1번까지 다 돌아도 더 이상 넣을 수가 없음)이 아니면, 게이트를 도킹하면 된다. 맨 처음에 자기 부모는 자기 자신을 해두고, 자기 부모가 0이 아니면 자기 부모랑 자기부모-1(아마 빈칸이겠지)을 union해서 그 앞에 빈칸이 아니면 자기부모-1의 부모를 또 찾으러 가니까 어쨌든 가장 마지막에 비어있는 1~N 사이의 칸을 찾아 주는 것. ==> 결국 부모-1과 union하는 이유는 결국 항상 부모 = 빈칸이 되도록 하기 위해서 뭔가 좀 생각하기 복잡하지만 코드는 그냥 disjoint set 쓰면 됨 스터디 오늘의 목표 1) H - .. 2019. 8. 22. 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로 .. 2019. 8. 19. [c++] 백준 #1992 쿼드트리 https://www.acmicpc.net/problem/1992 이것 또한 분할정복 문제이다. 백준 1780 종이의 개수 문제를 풀었다면 아주 쉽게 한문제를 먹을 수 있다.주어진 0, 1로만 이루어진 행렬을 4등분하였을 때 똑같은 숫자(all 0 or all 1)로만 이루어지지 않았다면 4등분하는 식으로 진행된다.트리의 괄호는 4등분이 시작할 때마다 열어주고, 끝날 때 닫아주면 끝이다. 문제의 행렬이 공백없이 주어지니 getline을 쓰는 것을 잊지 말아야한다.(cin.ignore()은 덤!) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636.. 2018. 11. 11. [c++] 백준 #2263 트리의 순회 https://www.acmicpc.net/problem/2263 한참을 이게 왜 분할정복 문제인지 고민하면서 보다가 post order의 속성을 이용하면 된다는 것을 깨달았다. 그것이 큐이다! post order의 경우 left right root 순으로 읽기 때문에 post order를 거꾸로 읽으면 root에서부터 root -> right -> left 순이 된다. 즉, post order에서 뒤에서부터 값을 읽으면 root가 무엇인 지 알 수 있고, 이를 통해 in order로 받은 input을 root를 기준으로 그래프를 left와 right로 나눌 수 있다.(분할정복의 의미) 나는 문제를 풀 때 in order와 post order를 보고 그래프가 어떻게 생겼는지 유추하고 나서(...), pr.. 2018. 11. 11. 이전 1 ··· 7 8 9 10 11 다음 반응형