본문 바로가기

전체 글

 (78)
[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)로 이동하면서 찾아..
[BOJ] 1396 크루스칼의 공 문제 링크: https://www.acmicpc.net/problem/1396 문제 요약 간선에 가중치가 존재하는 그래프가 존재하는데, 다음과 같은 쿼리를 빠르게 처리해야 한다. 정점 x에서 시작해서 y까지 이동하려고 할 때, 이용해야 하는 간선의 최소 가중치는 얼마인가? 그리고 x에서부터 그 가중치로 방문할 수 있는 정점의 개수는 몇 개인가? 문제 풀이 두 가지 풀이가 존재한다. (1) 병렬 이분 탐색 한 쿼리에 대해서 다음과 같은 문제를 해결한다고 생각해보자. 정점 x에서 시작해서 k 이하의 가중치를 갖는 간선만을 사용할 수 있을 때, 정점 y에 방문할 수 있는가? 또한 이 때 정점 x로부터 방문할 수 있는 정점의 개수는 얼마인가? 이 문제를 해결하는 방법은 쉽다. 말 그대로 k 이하의 가중치를 가지..
USACO 2020 January (Gold) 풀이 Intro 원래 USACO 참여할 생각이 없었는데 브론즈만 밀어야지 실버만 밀어야지 하다가 결국 골드를 키게 되었다. 중간에 뇌절파티를 많이 해서 예상보다 시간이 매우매우 많이 걸렸다. 개인적인 난이도는 2->1->3이라고 생각하나, 증명 없이 뇌를 비우고 푼다면 1번이 2번보다 더 쉬울수도 있다는 생각을 해본다. 세 문제 모두 플5에서 플3 정도의 수준이라고 생각한다. 1. Time is Mooney (time) 문제 요약 정점 1000개, 간선 2000개인 그래프가 있다. 각 정점은 1000 이하의 가중치를 가지고 있는데, 정점을 방문할 때 마다 그만큼의 점수를 얻는다(여러 번 방문해서 점수를 얻을 수 있다). 단, 사용한 간선 개수를 $t$라고 하면 주어지는 1000 이하의 정수 $c$에 대해 $c..
Goodbye, BOJ 2019! 후기 Intro 굿바이, BOJ 2019! 라는 대회는 어떻게 보면 제 주도로 만들어진 대회입니다. leejseo님과 rdd6584님과 작년 백준에서 진행했던 디디포스를 끝내고, 다음 대회를 진행해 보자는 말이 나왔었습니다. 10월 초 경에 생각이 나서 대회를 열고 싶었는데 만약 12월 말에 대회를 개최하게 된다면 디디포스와 거의 1년 간격이 된다는 것을 알았습니다. 구데기컵과 키파컵을 보고 백준에도 매년 정기적으로 개최되는 대회가 있었으면 좋겠다고 생각했는데 마침 대회를 여는 시기가 연말이었기 때문에, 낼름 연말 대회 자리를 먹기로 시도했습니다. 백준 대회란이 백준 고유 콘테스트가 아닌 다른 교내대회 오픈컨으로만 가득 채워진 것이 조금 안타까워서도 있었습니다. 그런 고로 자주 활동하는 알고리즘 채팅방에서 사..
Mstone Groove T87A 게이트론 저소음 갈축 후기 귀찮은 관계로 사진은 한장밖에 없습니다. 11월 중순에 수능 끝나고 바로 구입해서 한달 조금 넘게 쓰고 있는 중입니다. 14만원 정도에 구입했습니다. NYPC 참가상으로 받은 오테뮤 청축을 쓰면서 소음이 너무 심하게 거슬렸기 때문에, 소음이 너무 크지 않은 키보드이면 좋겠다고 생각했습니다. 저소음 적축을 많이 추천받았지만 키보드 타이핑을 제대로 못 해서 오타율이 상당히 높았기 때문에 적축을 쓰기에는 좀 문제가 있다고 생각했습니다. 다른 저소음 축이 있나 보다가, 게이트론사에서 거의 유일하게 저소음 갈축을 생산한다는 얘기를 듣고 구입을 결정했습니다. 저소음 게이트론 갈축을 끼워서 판매하는 기성품 제품도 이거 하나밖에 못 찾았기에, 거의 선택의 여지가 없었습니다. 처음 써보는 갈축이기 때문에 갈축 자체의 후..
BOJ: 코딩 테스트를 위한 길라잡이 (미완성) 들어가기에 앞서 미완성인 길라잡이입니다!!!!! 링크 지금 거의 다 깨져서 조만간 수정 예정입니다 최근 많은 기업들이 코딩테스트를 진행한다고 들었습니다. 왜 코딩 테스트를 진행할까요? 아직 기업 코딩 테스트에 목숨을 걸 나이는 아니지만, 아무래도 기업에서는 대학에서 커리큘럼을 모두 소화했다면 이 정도는 코딩해서 풀 수 있지 않을까라고 생각하기 때문 아닐까 합니다. 실제로 회사에서 해결하기를 원하는 과제가 엄청 대단한 수준을 요구하는 것 또한 아니고요. 하지만 많은 분들이 이를 굉장히 힘들어 합니다. 또 왜 이런 생고생을 해야 하냐고 물으시는 분들도 있습니다. 하지만 이런 간단한 과제조차 효율적으로 해결하지 못하고 또 버그를 내서 제대로 잡지 못한다면, 실무에서 코드가 훨씬 길어졌을 때도 마찬가지로 수렁에..

티스토리툴바