wifilion

나는 병신임을 이 문제로 다시 깨달았다스위핑 라인 관련 문제를 1개정도밖에 예~~~~전에 풀어봤어서 쉽사리 갈피를 잡지 못하였기에이 "갈피"를 블로그를 통해 잡았다....병신새기 진짜 티어값 못하는듯 어쨌든 그 "갈피" 란 다음과 같다: 철로 문제에서, 구하고자 하는 것은, 오른쪽 점에서 왼쪽으로 길이 d만큼의 구간 내에(혹은 경계에) 있는 라인 수라는 것 이 "갈피"를 잡고 나서 이제 곧 최적화를 해야 됨을 알게 되었고, 이는 꽤 쉬웠다 본인은 "보석 도둑"이라는 골드2 그리디 문제에서 상당히 많은 영감을 얻었었다. 그 중에서하나가 반복문에서 돌려도 크기가 단조감소하기에 그냥 O(N)이라는 거였는데, 이에 착안했다.우선순위 큐를 왼쪽 기준 오름차순, 오른쪽 기준 오름차순 순의 우선순위로 정렬(보통 나는..

일기를 다시 써 볼까 한다방학을 했기 때문에 할짓이 없기 때문이다방학 동안에는 일반물리학이나 복습하고백준 골드 I, II문제나 풀면서 힐링해야겠다. 물론 C++문법은 우리의 "대 컨벡스 헐"을 위해서라도 공부해야겠다는 생각이강하게 들었기에(...) 공부할 생각이다.시간표를 짜 봤다.컴퓨팅 기초를 넣은 이유? 컴핵은 백준 다이아들이 서식하는 무시무시한 강의라 들어서 쫄았다.컴기나 들으며 힐링해야겠다는 생긱이 들어 이를 선택했다.프방은 개인적으로 C++을 깊이 다루고 싶어서 수신을 도전할 예정이다.선대는 뭐 그렇다 치고 뜬금없이 왜 "정치와 정치이념" 이 들어가 있냐 물을 수 있는데꿀강이라 하기 때문에 넣어 봤다.픽순은 물리2(개인적으로 문 교수님의 강의를 듣고 싶기에)정치, 정치이념선대 순이다.나머지는 널..

쓰레기 슈트는 convex hull 알고리즘을 활용하는 문제이다. 이 글에서는 convex hull 알고리즘을 다루지 않으니, 이에 대해서는 다른 글을 읽고 오길 추천한다. 쓰레기 슈트 문제는, 주어진 점들로 이루어진 다각형이 있을 때, 이를 회전시켜 들어갈 수 있도록 하는 구멍의 최소 너비를찾는 문제이다(문제 설명에 쓰여 있다). 그리고, 이 문제의 AC 여부를 결정하는 가장 큰 요소는... 부동소수점.항상 부동소수점 오차를 주의하고, 반올림 함수나 올림 함수 등을 컴퓨터에 미리 구현해 놓고 필요시마다 가져다 쓰는 것도 나쁘지 않은 방법이다(실제로 본인은 그렇게 했다). 쓰레기 슈트 문제는 얼핏 보기에는 컨벡스 헐을 사용하는 문제가 아닌 듯 보일 때도 있다. 그러나, 풀이에 사용할 가정이 성립하려면 c..

하루걸림ㅇㅇ역시 실버를 풀면서 인간이 힐링을 해야지 살 맛이 나는구나...내일은 클래스 3 도장깨기 ㄱㄱ해야지클래스3는 dfs/bfs라서 그래프를 좋아하는 본인으로썬 썩 괜찮은 경험이 될 듯.이전에 못 풀었던 문제들을 지금 들여다보니까참 뭐랄까 왜 생각 못했는지...

나는 플래4인데 왜 플래문제를 풀지를 못하니...이렇듯 부족한 실력을 키우기 위해서클래스2부터 차례대로 금장을 달아주기로 했다. 실버는 존나 쉽기 때문에 하루에 20문제도 풀어재낄 수 있다.골드 4~5 dp도 쉽다. 그런데 이제 골드3부터 좀 문제지. 오늘 랜덤마라톤으로 나온 골드3 그리디 하나 풀었는데 존나 쉽긴 했다. 그렇다고 다 쉽다는 보장이 없기에... 시간 남으면 동시에 클래스 6도 도전하기로. 습격자 초라기가 문제 셋에 있어서 그 좋같은 친구는 패스하고, kmp나 이전에 배운 SCC, 2-SAT나 복습하련다. 근데 그거앎? 계절이라 시험 이틀남음ㅋㅋ 근데 공부는 다 해 놓아서 딱히 상관은 없을지도.인공지능 연전이나 컴공 복전을 붙이려 한다. 컴퓨터 관련해서 뭐라도 붙여놓으면 도움이 되잖슴. 그..

심심해서 애니소개를 작성하려 한다.제목은 エロマンガ先生이다. 이거 좀 위험하다. 번역기는 돌려보지 않기를 추천한다. 참고로 이 제목을 달고 나와서 15세 심의를 받았다. 애니메이션은 1~14화(OVA포함)으로 구성된다. 본인은 1화부터 14화까지를 하루만에 정주행한 뒤 그 다음 날 한 번 더 정주행하고 리뷰를 쓴다. 이 작품은 "라노벨 작가"의 이야기를 다룬다. 동일하게 이에 관련된 이야기를 다루면서, 소위 "Immoto"물인 작품으로는 "  妹さえいればいい。"가 있겠다. 이것도 번역 돌리지 마라.  참고로 아래 작품은 19세 이용가이다. 본인은 이 작품을 좋아한다. 이 작품은 캐릭터 디자인, 그리고 작화 면에서 특히 뛰어나다 할 수 있다(적어도 본인은 그렇게 생각한다). 그리고, 가장 마음에 드는 점이..

lazy propagation을 쉽게 말하자면, 구간 업데이트 쿼리를 빠른 시간 내에 처리하기 위해 lazy한 업데이트를 사용하는 것이다. 이게 뭔 소린가 하면, 업데이트를 안하고 존버까고 있다가, lazy배열의 값을 해당 노드를 필요로 하는 시점에서 update처리해주는 기법이다. 이러면 구간쿼리를 NlogN이 아닌, 다른 쿼리에 낑겨서 들어가기 때문에 logN으로 처리할 수 있다(물론 빅 오)스위치 문제는 이러한 lazy propagation의 대표적인 예시 중 하나이다. 본인은 쿼리 문제 중 세그트리 관련 문제를 풀 때, 이 문제가 세그트리를 어떻게 써야 하는지부터 생각하는 법이다.https://www.acmicpc.net/problem/1395  아래는 이 문제를 풀 때 생각한 순서이다.1.세그트..

2-SAT문제는, 두 개씩 묶인 boolian 변수들의 AND 연산을 true로 만들 수 있는 변수들의 boolian 설정이가능한지 묻는 문제이다. 역시 글로 쓰니 어렵다. 식으로 알아보자.f: (x1∨x2) ∧(~x3∨x4)∧.... 일 때, xn을 true/false(boolian 변수이므로)로 설정해서 이 전체 식이 true가 될 수 있는지여부를 판단하는 것이다. 당신은 명제의 화살표를 그래프의 간선에 대응시킬 수 있다는 생각을 해 본적 있는가?본인도 물론 없다. 어떤 훌륭한 친구가 그런걸 생각하겠는가. 근데 누가 했대...각 절(저 괄호로 묶인 단위를 절이라 한다)이 true가 되기 위한 조건을 생각해 보자. 첫 번째 절에서, x1이 true이면? x2는 true이던지 false이던지 그게 먼 좃..

오늘은 일요일이다. 어제 시험을 봤는데, 좃말아먹었다. ㅅㅂ Q3+10을 기대했는데, 뭐. 오랜만에 쓰는 일기다. 언제 썼는지도 사실 기억 안나. 일주일 뒤면 물리학 시험인데 얘는 뭘 공부할지 감도 안잡힌다. 그래서 PS를 한다. 하루 7시간씩, 스트릭에 강박을 느끼며 내가 잘하는 걸 하나라도 만들고 싶어서. 과고 이름 더럽히고 싶지 않아서. 그냥 그렇게. 그래서 그래서 조금 그래서 조금 우울하다. 노래 추천도 오랜만에 한다. '카구야'라는 kai의 노래가 있다. 링크는 남기기 귀찮으니, 알아서 찾아보도록 하자. 얘는 애니메이션 주제간데, 그 애니메이션은 파칭코를 모에화(....)한 무려 그런 애니메이션이다. 그래도, 뭐 좋더라고. 다음 일기는 언제가 될지는 모르겠는데 이 일기를 읽는 사람이 있기나 할까..

자, 오늘은 무엇을 공부했는가, 사실 오늘 한건 아니고, SCC라는 테크?닉에 대해 공부를 했다SCC는 Tarjan's algorithm으로 구현하는 방법을 학습하였다.대충 말하자면, 트리를 만들고(그래프로? 이건 좀 귀한데) 자기 자신에서 최대로 향할 수 있는 부모 정점이자신이면 SCC로 스택에서 꺼내는, 뭐 그런 식이다.SCC의 성질로부터 사이클들을 SCC로 만들고, SCC로 만든 그래프는 사이클이 없는 방향그래프가 된다.즉, DAG이다.DAG에 먼짓을 할 수 있냐?그건 위상정렬이죠. 위상정렬에 뇌가 절여지는 중이다.과고에 있을 적 cactus를 매우 좋아하는 친구가 있었다.단절점 / 단절선을 배운 다음 그 유명한 cactus를 보고 싶은 느낌이다.