본문 바로가기

전체 글

(75)
개인적인 웹툰 몇줄 감상 * 너무 유명한, PC 기준 순위 5위권 즈음에 들어가는 웹툰들은 과감히 제외하고 선정합니다. * 보는 웹툰 중에서도 이건 한번씩 볼만하다 싶은 작품들을 선정했습니다. * 글쓴이의 취향은 상당히 마이너합니다. 꿈의 기업 드림 코퍼레이션이라는 의문의 회사에 취직한 사람들과, 그들이 살았던 도시, 그리고 한 인공지능의 이야기. 물론 스릴있고 흥미롭지만 무엇보다도 생각을 많이 하게 해 주는 작품. 긴 이야기 호흡에도 지치지 않을 자신이 있다면 시도해볼 가치가 충분하다. 고삼무쌍 이세계가 아닌 현세계에서 고등학생이 깽판치는 웹툰. 빠르고, 호쾌한 B급감성 신세대 무협. 이제는 무협도 따분하게 보지 않을 수 있다. 색다른 판타지 웹툰이 필요했거나, 아니면 요즘 살기가 좀 팍팍해서 큰 웃음이 필요한 사람들에게. 닥..
[BOJ] 16910 mex와 쿼리 [문제 링크](https://www.acmicpc.net/problem/16910) 문제 요약 다음과 같은 세 쿼리를 처리해야 합니다. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다. 각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다. 문제 풀이 일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상..
[BOJ] 14591 KUBC League, 17165 Gosu 14591 KUBC League 문제 요약 토너먼트 그래프가 있다. 1번 정점에서 시작해서 모든 정점을 순회하는 단순 경로를 찾으면 된다. 문제 풀이 DFS 스패닝 트리에 의거하여, 그냥 DFS를 1번 정점에서부터 수행 후 마지막부터 출력해주면 된다! 코드 #include #include #include #define all(x) (x).begin(), (x).end() #define endl "\n" #define ends " " #define pb(x) push_back(x) #define fio() ios_base::sync_with_stdio(0); cin.tie(0) using namespace std; typedef long long ll; typedef pair pii; typedef pai..
Small to Large Trick Intro Small to Large Trick은 집합을 서로 합치는 연산을 최적화 할 때 사용하는 트릭입니다. (한국에서는 작은거 큰거 라고도 불리는 모양입니다.) 예를 들어 $n$개의 disjoint한, 크기가 1인 집합을 서로 합쳐야 한다고 합시다. 당연하게도 크기가 $a$인 집합에 크기가 $b$인 집합을 추가하는 데는 $O(b)$의 시간이 걸립니다. 이걸 Naive하게 구현한다면 얼마의 시간이 걸릴까요? 만약 두 집합을 합칠 때 아무 집합을 다른 집합에 합치는 것을 계속 반복한다면, 최악의 경우에는 크기가 가장 큰 집합을 크기가 가장 작은 집합에 계속해서 넣으면서 총 $O(N^2)$의 시간이 걸릴 것입니다. 하지만 어지간히 멍청한 알고리즘이 아니고서야, 크기가 큰 집합을 작은 집합에 합칠리가 없습..
Google Hash Code 2020 후기 부추전 고양이 boots jeon cats는 이런 사람들이 모여 만든 팀입니다. ryute, 고려대 아기호랑이, 랜덤과 휴리스틱을 사랑함 Lawali, 고려대 석유호랑이, 랜덤과 휴리스틱을 혐오함 cloneofsimo, 고려대 어른호랑이, 아무튼 알고리즘 시작한지 한달 반 지남 junie, 서울대, 왜 설대인데 고대 사이에 끼어 계십니까? :blobaww: 개인적으로 junie님하고 꽤 많이 친하기에, 구글 해시코드에 나가자는 뜻이 맞아 2인 팀이 결성되었습니다. 그 후 연습을 빙자한 맥주 마시기 행사를 가진 다음 사람이 많을수록 무조건 이득이라는 것을 확인하고, 대충 버스를 태워줄 수 있을 것으로 보이면서 할 것도 딱히 없어 보이는 라왈리를 섭외했습니다. 마지막으로 인원수를 대충 때워야 할 것 같다는 ..
[BOJ] 13329 Meteor Shower 문제 요약 y>0인 반평면에 다각형들이 있다. 원점에서부터 빛을 쏴서 다각형들을 관측할 때, 어떻게 빛을 쏴도 관측할 수 없는 다각형의 개수를 세서 출력한다. 문제 풀이 이런 류의 문제에서 항상 쓰는 테크닉인 스위핑을 갖고 옵시다. 다만 평소에 쓰는 라인 스위핑이 아닌, 각도 기준으로 스위핑을 진행해야 합니다. 다각형끼리 서로 교차하지 않으므로, 각 다각형을 각도가 가장 작은 점과 각도가 가장 큰 점을 이어주는 선분으로 바꿔줘도 답에는 영향이 없습니다. 그렇다면 문제는 n개의 선분이 주어졌을 때 완전히 가려지는 선분을 구하는 문제로 환원됩니다. 모든 선분의 끝 점을 각도 순으로 정렬합니다. (https://koosaga.com/97) 선분의 시작 지점이 들어올 때 집합에 선분을 추가하고, 종료 지점이 들..
[ICPC] ICL 2016 (GP of Tatarstan) 후기 & 잡설들 Intro 고려대학교 2020 ICPC 팀이 한 팀 결성되었습니다! ryute, 20학번, 퍼플 seyun, 19학번, 오렌지 cheetose, 군인, 오렌지 cheetose님이 저에게 팀 하자는 제안을 주셨고, seyun님도 cheetose님한테 팀 하자는 제안을 드린 것 같아서 영문도 모른 채 3인 팀이 구성되게 되었습니다. 저는 오렌지 둘의 버스를 탈 수 있으니 대만족이고, 현재 음료수와 간식을 배달하고 분배하는 업무에 숙달되기 위해 오늘도 열심히 노력하고 있습니다. 입학하기도 전에 버스팀이 생기는 사람이 있다? 서로 얼굴을 본 적이 없다는 이유로 만나서 밥을 먹기로 했습니다. cheetose님이 밥 먹기 전에 셋을 하나 돌자고 하셔서 솔직히 불안했습니다. 오렌지 2명 사이에 끼어서 노솔브 하면 어..
[BOJ] 10264 Particle Swapping 문제 링크: https://www.acmicpc.net/problem/10264 문제 요약 평면 그래프에서 다음과 같은 쿼리를 처리해야 한다. 어떤 두 정점이 주어질 때, 각 정점에서 반대 정점으로 이동하는 개체 2개가 있다. 이동 중 개체 사이 거리의 최솟값이 가장 최대가 되도록 배치했을 때 거리의 최솟값을 구한다. 단, 경로에서는 간선은 따지지 않고 오직 정점만을 따진다. 문제 풀이 그래프를 적절히 바꿔서 모델링해보자. 정점 A에서부터 출발하는 개체와 정점 B에서 출발하는 개체의 위치를 순서쌍으로 표현해볼 수 있다. 만약 그렇다면 이동 중 개체 사이 거리의 최솟값은, 순서쌍을 정점으로 두고 순서쌍 사이의 상태 전이가 가능한 경우를 적당히 간선으로 이어줬을 때 (A,B)에서 (B,A)로 이동하면서 찾아..