gubshig

0.  서론2학년 때 학교 프로젝트로 TSP에 대해 다룬 적이 있는데, 이와 관련하여 MDMTSP(814-3)에 대한 해결책을 요즘 찾고 있어 정리해볼까 한다. TSP(외판원 순회 문제)는 대표적인 NP-complete(결정 문제의 경우) 문제 중 하나이다. ps에선 흔히 bit dp라 불리는 테크닉을 처음 접할 때 많이 소개되곤 한다. $\mathcal{O}(N \cdot 2^N)$ 정도의 해결책은 널리 알려져 있지만 P = NP가 아닌 이상 다항 시간 해결책을 기대하긴 어렵다. 근사해를 구하기 위한 시도를 해볼 수도 있지만, 다항 시간 근사해 조차 구하기 힘들다. 그러나 TSP로 환원 되는 다양한 문제들이 존재하고 현실 세계에서 이에 대한 해결책이 필요한 경우가 있다. 이 글에서는 TSP를 해결하는 ..

수고하셨습니다. 저는 11번이 너무 귀찮아서 그냥 대충 하고 접었네요...

서론처음 나가보는 국민대 대회 입니다. 원래 작년에 나가려 했으나 이런 대회는 아무도 언제 열리는지 알려주지 않더라고요? 홍보도 없고요. 결국 신청을 놓쳐 참가하지 못했습니다. 올해는 마감 n시간 전에 지인이 알려줘 겨우 신청 할 수 있었습니다. KOI 2차를 만족스럽게 마치고, 딱히 ps를 하진 않으며 국민대 대회를 기다리고 있었습니다. 여담으로 지인이랑 리사콘을 갔다 왔습니다. 제가 소아온 1기 때부터 리사를 좋아했었는데, 엔젤비트의 최고의 보물, 모든 소아온 ost, 모든 귀칼 ost를 다 해줘서 성불하고 왔습니다. 코난 극장판도 봤습니다. 코난 잘 모르는데 괴도키드는 좋아해서 적당히 재밌게 봤습니다. 요즘 극장판 퀄리티가 좋더군요. 말딸 새로운 시대의 문도 봤습니다. 예고편을 보고 티엠 오페라 오..

1. 리차오 트리리차오 트리는 주로 CHT(Convex Hull Trick)이라 불리는 다음과 같은 문제에 사용된다.직선 $ax + b$ 추가$x$가 주어질 때 직선들 중 $ax + b$의 최댓값 쿼리물론 최솟값 쿼리 또한 해결 가능하다.이때 직선의 기울기 $a$가 단조증가/단조감소하고, 쿼리로 주어지는 $x$가 단조증가/단조감소 하는 경우 스택을 이용한 업데이트, 쿼리 amortized $O(1)$ 해법이 존재한다(https://justicehui.github.io/hard-algorithm/2019/01/25/CHT/).  리차오 트리는 단조 조건이 없는 경우에도 사용할 수 있지만, 업데이트와 쿼리가 $O(\log X)$ ($X$는 쿼리로 주어지는 수의 범위)가 걸린다는 단점이 있다. 단조 조건이 있..

학교선린인터넷고등학교 제117기 소프트웨어과 (2022/03/02 ~ 2025/02/07)한양대학교 25학번 산업공학과 (2025/02/25 ~ ) 온라인 저지 프로필https://www.acmicpc.net/user/gubshig - 1009 solvedhttps://solved.ac/profile/gubshig - Diamond II 2574https://codeforces.com/profile/cerise_bouquet - Rating (max. expert, 1726)https://atcoder.jp/users/revue - Rating (max. 1694 2 Kyu) 대회 참가/수상 2022 선린 프로그래밍 경시대회 동상(3위) 2022 선린 제6회 천하제일 코딩대회 본선 참가(11위) 2023..

수능 공부 끝에 다시 돌아왔습니다. 이번 5월에 1차에서 동상을 받아서 본선에 진출하게 되었습니다. 정시 때문에 딱히 준비를 하진 않았고 대회 1~2주 전 즈음에 재활을 조금 했습니다. 생각보다 좋은 결과를 받았습니다. 아직 가채점 결과가 나오진 않았지만 운이 좋으면 은상을 노려볼 수 있지 않을까요? 14:21:16 가로등(1번) 100점대회는 13:30분에 시작했습니다.시작하고 1번 문제를 읽었습니다. 일단 구간을 적당히 $2N$개로 쪼개서 최솟값을 관리해줄 수 있는 자료구조에 넣고 $K$번 뽑아주면 될 것 같았습니다. 구현을 딱히 생각 없이 하다 조금 틀리고 1시간 정도 지나서 100점을 받았습니다. 쉬운 문제였는데 구현도 말리고 오래 걸려서 이때까진 대회가 망한 줄 알았습니다. 16:27:34 xo..

https://youtu.be/Gls1MQLv5o0?si=3fOPGTouHiqVEYuK 갓곡 주의) 성덕, 오타쿠 얘기가 다수 있습니다. 역할 수도 있으니 주의해주세요. 원래 서코를 자주 까지는 아니고 가끔 갔었는데 어느 순간부터 제가 오타쿠 유행(블루아카이브, 붕괴스타레일, 원신, 버튜버 등등)에 뒤쳐진 이후로부터 귀찮기도 하고 제가 아는게 점점 없어져서 안갔었습니다. 그러다 작년 겨울쯤에 solved.ac 디스코드 에서 2월 일러스타페스에선 solved.ac 부스가 열릴 계획이라는 말을 듣고 가는 것을 계획했었습니다. https://x.com/kimchikura/status/1747584226822905996?s=20 X의 김치쿠라(Anisong DJ Event)님(@kimchikura) 【チケット情..

일본여행 마지막 날입니다. 내일 12시즈음에 비행기를 타고 출발할 예정이라 추가적으로 할 수 있는게 딱히 없을 것 같네요. 오늘은 철판구이, 도쿄타워, 이케부쿠로 레뷰 콜라보 카페, 튀김꼬치요리 먹기 등등을 하였습니다. 3일간의 피로가 누적되어 쓰러질 것 같지만, 이 감정과 체험을 글로 남기고 싶기에 열심히 작성해볼게요. 어제 11시 즈음에 잠들어서 그런지 7시에 잠이 깼습니다. 깬 당시에도 피곤이 엄청 몰려왔었지만 일본에서의 마지막 날이라는 생각으로 일어나서 아침을 먹으러 갔습니다. 오늘의 아침은 간단하게 커피를 먹는 용도로 생각했습니다. 점심에 맛있는 것을 먹을 예정이기에 아침에 너무 무거운걸 먹을 생각이 없었습니다. 와플... 정말 맛있더군요. 솔직히 말하면 그렇게 특별한 맛은 아니었지만, 평균 이..

주의) 니지가사키 얘기가 상당히 많습니다. 2일차는 오다이바에서 하루를 지내는 것을 목표로 삼았습니다. 오다이바는 관광지로도 유명하지만, 사실 저에게는 오다이바가 통째로 성지입니다. https://twitter.com/JZC7NfSPwiPxwcq X의 니지가사키MAP님(@JZC7NfSPwiPxwcq) 니지가사키 스쿨아이돌 동호회 성지순례 지도 (한국어판) / 虹ヶ咲学園スクールアイドル同好会 聖地巡礼 MAP (韓国語) / #lovelive #虹ヶ咲 #聖地巡礼 / 오류 지적과 피드백은 언제나 환영합니다 twitter.com 러브라이브 니지가사키학원 스쿨 아이돌 동호회의 배경이 되는 도시로, 일본에 가면 꼭 가보고 싶었는데 마침 호텔 근처 (지하철로 30분) 거리이기도 하고, 관광지로도 유명하다 하여 방문해보았..

도쿄! 정말 좋아요. 꽤 오랫동안 가고 싶었는데 이번에 고3 기념으로 가족여행을 가게 되어서 운 좋게 도쿄에 갈 수 있게 되었습니다. 여행 출발부터 하루의 끝까지 작성해볼 생각입니다. 지금 정신이 약간 헤롱헤롱해서 완전 의식의 흐름 일기 같을 수 있다는 점, 유의해주세요. (기억보존용) 김포공항 8시 비행기라 집에서 5시 즈음에 출발하는 것을 목표로 하였습니다. 평소 5시에 잠드는 생활 패턴을 가지고 있는 저는, 밤을 새면 도쿄에서 제대로 즐기지 못할 것을 염려하여 일찍 기상(아침 10시)을 하고 하루종일 많은 활동(usaco 밀기, 리듬게임 하기)을 하여 피곤해지도록 조절하였습니다. 결국 기적적인 11시 수면에 성공하였지만, 아쉽게도 새벽 2시에 기상하고 다시 잠들지 못하여 3시간 수면을 하고 집에서 ..