꼭 이걸 써야 되는지 써도 되는지는 모르겠다 공개적인 곳에서 자랑하는 것도 아니고, 그래도 이런 경험을 해볼 일이 얼마나 될라나 싶어서 여기다 대강 글로 적어 남기고 싶다. 사실 겨울학교 전까지만 해도 내가 잘하는 지도 몰랐고 국대에 대한 욕망도 별로 없었는데 (기대치가 없으니), 와서 보니까 내가 생각보다 잘하더라. 겨울학교 끝날 때 시험을 치고 대강 6등? 언저리에 머물렀더니 확실히 유혹이 생겼다. 딱히 잘본것도 아닌데 그렇다고 딱히 못 본것도 아니고 그 점수대가 다 비슷비슷해서. 꼴지를 해도 공부야 했겠지만 그래도 목표치를 조금 높게 잡아보기로 했다. 그런다고 죽는것도 아니고 ㅎㅎ 겨울학교 갔다오고 배운게 참 많다.. 세그먼트 트리를 짤 수 있게 된 것도 사실상 그 이후였고, 컨벡스헐트릭도 몇달만에..
https://www.acmicpc.net/problem/2519 새로운건 없는데 다까먹었네.. 다음과 같은 논리식들을 만족하는 막대기가 필요하다.1. 교차하는 막대기 두 쌍이 있다면, 두 쌍 중 한 쌍이 사라져야만 한다.2. 3개의 막대기 중 한 막대기를 사용한다면, 나머지 두 막대기는 사용하면 안된다.고로 2-SAT으로 풀리는 문제이다. 논리식을 만들어주자. 2번은 너무 당연히도 명제이다. 막대기 A를 지운다는 것을 E(A) 라고 표현했을 때, 2번은 E(A) -> ~E(B), E(A) -> ~E(C)... 를 6 (3 * 2)개 만들어주면 된다.1번은 약간 변형해줘야 명제가 된다. E(A) || E(B) 라는 식의 명제인데. 논리식은 가정이 참이면 결론이 참이어야 하고, 가정이 거짓이면 항상 참이다..
- Total
- Today
- Yesterday