• [[정우 대회]]

리스트

• 10830 제출 (MOD 주의하자)
• 1300 제출 (long long 주의하자)
• 2261 line sweep으로 푼거 다시 제출 (시간복잡도 잘 생각하기)
• 1167 dfs 를 주의하면서 짜자
• 11725
• 12025 index_tree 로 풀어보기 (압축하는데 시간이 생각보다 많이드나? ㅠ 조금더 고민해보자)
• 1967 : 1167 하고 똑같네
• 1086 : 50자 때문에 삽질을 엄청 많이 했다.. 입력이 숫자라고 해서 항상 long long 으로 입력 받을수 있는 건 아니란걸 다시 상기하게 됬다. 이외에도 자리수를 셀때 모듈러 한걸 그 숫자라고 생각해서 삽질을 많이 했다.
• 2618 : 경찰차 - 2일 정도 고민했는데 도저히 모르겠어서 구글링해서 답지를 봤다. 나름 변명하자면, 전부 다 본건 아니고 dp 조건이 뭔지 봤다.(사실 이거면 다 본게 맞긴하지만) 처음 보는 형태여서, 답지를 본게 크게 후회되지는 않는다. 새로 배운걸 요약하자면, 굳이 dp table을 모두 채울 필요도 없고, 여러 index 중 1개가 우리가 구하는 조건일수 있다. ~~흠.. 머라 서술할지가 어렵네 ~~ 그리고 dp table 에 대해서 조금더 생각하게 됬고, dp index로 둔것끼리 중복된 역할을 하는지 의심해봐야된다는 것이다. dp 자체가 메모리를 적게 사용하는건 아니니, 결정하는 최소 조건만이 들어가야지 공간, 시간 복잡도가 안터진다.
• 13344 : Chess Tournament - 단순한 위상정렬 문제이다. solved.ac 에서 플레티넘 5로 책정됬길레 공부가 될것 같아서 풀었는데, 별 큰 도움 안됬다. 그냥 단순히 Union-Find + Indegree 문제라서, 골드 1로 측정되도 괜찮을것 같은데, 아마도 2개 섞인거라 다들 플레티넘 준듯… 큰 이득이 없었다.
• 11266 : 단절점 - 예전에 주변에서 공부하라고 했는데, 공부 안하다가 DFS Spanning Tree 문제에 크게 당한 이후로 공부해야 겠다고 생각만 하다가 오늘 문제를 풀어봤다. 개념만 보고 풀었는데 통과해서 다행이다.
• 11500 : 단절선 - 단절점에서 조금 더 공부하면 될것 같아서 적어둠 그냥 생각 조금만 틀면 되서 해결함. 문제 조건을 잘 봐야한다는걸 다시 깨달음. 정렬을 안해서 1번 틀림.
• 2150 : Strongly Connected Component - 강결합컴포넌트(SCC) 라고 불리는 문제이다. 코사라주(Kosaraju) 알고리즘을 배웠는데, 생각보다 구현이 간단하다고 생각해서 풀어봤다. 중간에 push_back(move(data))을 해줬는데, vector 의 deep copy가 일어날까봐 걱정한것 빼고는 크게 특별한게 없는 문제였다.
• 13510 : 트리와 쿼리 1 - 처음에 보고 한참동안 몰라서 초록책을 계속 뒤져보다가 트리 거의 마지막에 나와있길레, 이거다 싶어서 구현을 시작했다. 책만 보고 구현하는게 목표여서 점심시간, 모각코 시간마다 코딩했는데 계속 틀려서 30번 가량 틀렸다. 중간에 이걸로 푸는게 아닌가?? 하면서 다른 사람 구현체를 가져다가 채점해봤는데, 맞더라…. 구현이 틀렸다는걸 알고 다시 한번 읽어보니까 놓친 부분이 있더라
  • 사용하는 개념은 Heavy-Light Decomposition 이라는 건데, 예전에 아는 형이 알려줬던 트리 펼치기와 비슷하지만, 연속성 보장 등 측면에서 그 다음단계 알고리즘 인것같다. 아이디어가 굉장히 참신하다고 생각했다. 틀린건 Heavy Path 안에서 index의 연속을 보장하기 위해서, dfs 순서를 신경써줘야 되는데, 대부분의 구현체에서는 이를 edge의 0번 index가 항상 heavy 하도록 구현하는 것인데, 나는 괜히 heavy 배열을 만들어서 이를 해결하려다가 dfs 순서 보장이 안되서 틀렸었다.
• 14888 : 처음에는 dp로도 되겠는데? 라고 접근 했다가 한번 틀렸다. 곱하기나 나누기를 조금만 생각해보면 dp조건이 성립하지 않았다는 걸 알수 있었다. 그냥 전부 돌아보는 방법으로 해결했다.
• 15481 : 두번째로 큰 스페닝 트리를 도저히 못풀겠어서 파란책(하얀책이라고도 불림)을 뒤져봐도 두번째로 큰스페닝 트리의 시작복잡도는 O(VE)라고 나와있어서, 결국 검색해봤다. 생각보다 단순한 테크닉이여서 허무했다.
• 17412 : 네트워크 플로우 문제이다. 예전에 찾아둔걸 참고해서 제출했다. 그런데 백지상태에서 똑같이 코드를 짜보니까 flowing 함수를 잘 못짜겠어서 다시 공부해야한다.
• 1626 : 두번째로 작은 스패닝 트리- 15481 에서 단순히 그냥 2번째 값을 출력하면 될줄 알고 계속 시도하다가 많이 틀렸다. 코너케이스를 결국 못찾아서 검색해봤다…. 이런 간단한 것도 생각 못하다니 바보같다. maxEdge를 구할때 현재 추가 되고 있는 Edge와 같은 값이 경로상에서 나오면, 그 다음걸 선택해야하는걸 나중에 알게되었다. 처음에는 단순히 long long overflow 인줄 알았는데 ㅠ. 새로운 개념을 공부한다고 잘해지는건 아닌데 마치 잘해진것처럼 착각만 하고 있었다. 이런걸 생각해낼수 있도록 더 열심히 해야겠다.
  • 이거 틀렸었는데 통과됬었다…. 생각해보니 그냥 except이면 다른애를 선택하는게 아니라, 항상 모든 경우에 대해서 1, 2번쨰로 큰 애들을 고려해야하는데, 이게 고려가 안됬었다. 데이터 추가 요청 했다.
• 7966 - template : stl 사용법을 잘못 알고 있어서 한참을 틀렸다. multiset을 다시 공부해야겠다. 2주 넘게 고민하다가 결국 아는 형에게 도움을 청해서 풀었다. 그러고도 잘 모르겠어서 구사과 블로그도 참고했다. 나중에 꼭 다시 풀어봐야할 문제이다.
• 3878 - Separate Points

  보조정리 1. 임의의 두 볼록 다각형 A, B가 서로 분리가 가능하다면, 분리하는 임의의 선 중에 볼록 다각형 A 또는 B를 구성하는 변과 평행한 선분이 존재한다.
  보조정리 2. 제 1, 2사분면 위에 존재하는 임의의 볼록다각형 A의 꼭짓점 중, 가장 x축과 가까운 꼭짓점은 변의 기울기가 음수에서 양수로 되는 점들과, x축에 평행한 변들의 꼭짓점 중에 존재한다.
  정리. 임의의 두 볼록 다각형 A, B에 대해, 한 볼록 다각형 A의 임의의 변을 a 라 하고 a의 기울기를 a'라 할때, B 중 기울기가 a'이거나, a'와 가장 가까운 두변들의 꼭짓점들이 모두 변 a의 바깥쪽에 있다면 두 볼록다각형은 겹쳐져 있지 않다.
  

  • 지금 AC 받은 풀이는 convex hull + n^2 짜리 탐색인데, 슬랙에서 아시는분이 nlgn 도 가능할거라고 하면서 이해하는걸 도와줬다. 아직까지는 논리적으로 맞는거 같아서 구현해보고 제출해볼 예정이다.
• 11014 : 이분그래프인걸 알아차리는데 1시간 넘게 걸린듯… 그마저도 코딩하다가 계속 삽질해서 30분 동안 구현했다. maximum independent set 과 maximum vertex cover 에 대해서 공부하게 되었다. 그래도 실제로 대회같은데서 나오면 못알아챌듯하다. 문제들을 많이 풀어보면서 연습을 계속해야겠다.