하바나바나나

JUNCTION ASIA 2022 참가 후기 (1) JUNCTION ASIA 2022 참가 후기 (1) 어쩌다보니 정션 아시아 2022 해커톤에 참여하게 되었습니다. 사실 너무 귀찮아서 블로그 글을 쓰지 않으려고 했는데, 기억이 사라지기 전에 조금이나마 남겨보고자 글을 적게 되었습니다. 끝까 blog.havana.moe JUNCTION ASIA 2022 참가 후기 (2) JUNCTION ASIA 2022 참가 후기 (1) 어쩌다보니 정션 아시아 2022 해커톤에 참여하게 되었습니다. 사실 너무 귀찮아서 블로그 글을 쓰지 않으려고 했는데, 기억이 사라지기 전에 조금이나마 남겨보고자 글을 적게 되었습니다. 끝까 blog.havana.moe 정말정말 오랜만에 다시 쓰는 정션 후기입니다. 다 까먹어서 이제 뭘 ..

https://bhnb.havana.moe/ BHNB bhnb.havana.moe 별 헤는 밤(BHNB)을 WebGL을 사용해 개발해보았습니다. 별 헤는 밤은 천문 동아리 선배인 PngWnA 선배가 처음 개발한 프로젝트로, 웹 브라우저로 현재 접속 중인 위치에서의 밤하늘이 어떻게 보이는지 구현한 플라네타리움입니다. 해당 프로젝트를 나중에 또 다른 천문 동아리 선배인 susemeee 선배가 React로 포팅한 버전인 BHNB-react가 있고, 이를 다시 한 번 WebGL로 구현한 것이 이번 프로젝트입니다. 기술 스택 사용된 기술 스택은 다음과 같습니다. Next.js, React TypeScript three.js, react-three-fiber, react-three/drei Github Action..

https://www.acmicpc.net/problem/4913 4913번: 페르마의 크리스마스 정리 각 테스트 케이스에 대해서, 한 줄에 L U x y를 출력한다. 여기서 L과 U는 입력으로 주어진 값이고, x는 구간 [L,U]에 포함된 소수의 개수, y는 [L,U]에 포함된 소수중 제곱수의 합으로 나타낼 수 있는 www.acmicpc.net 풀이 자체는 어렵지 않은 문제입니다. 음수는 소수가 아니므로, 1부터 1000000 사이의 모든 소수를 에라체를 이용해 미리 구해준 뒤 누적합을 이용해 매 쿼리마다 소수의 개수와 제곱수의 합으로 표현되는 소수의 개수를 구해주면 됩니다. 단, 주의해야 할 점은 2 역시 제곱수의 합으로 표현되는 소수라는 점입니다. (1 + 1 = 2) 이걸 몰라서 세 번 틀렸습니다..

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 스택을 사용하여 풀 수 있는 문제입니다. 문자열의 P를 PPAP로 바꿀 수 있다는 말은, 달리 말하면 PPAP을 P로 바꾸어 원래 문자열을 복원할 수 있다는 뜻입니다. 문자열을 쭉 확인하며 스택에 문자들을 넣어준 뒤, 맨 마지막 네 문자가 PPAP라면 P로 바꾸는 과정을 반복하여 마지막에 스택에 P만 남아있다면 PPAP를, 아니라면 NP를 출력하면 됩니다. 아래는 코드입니다. #include #define FastIO ios::sync_with_s..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 원래는 14639번을 풀려고 했는데... 아무리 생각해도 못 풀고 힌트를 들어도 못 푸니까 cologne 님이 던져준 문제입니다. 연속된 전구가 주어지고 $i$번째 전구는 $i-1$, $i$, 그리고 $i+1$번째 전구를 toggle 할 수 있습니다. 원래의 전구 상태와 바꾸고자 하는 전구 상태가 주어질 때, 최소 toggle 횟수를 찾아야 합니다. 이는 그리디한 방법..

https://www.acmicpc.net/problem/4181 4181번: Convex Hull 때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소 www.acmicpc.net 말 그대로 컨벡스 헐을 구하는 문제입니다. 컨벡스 헐을 구할 수 있으면 그냥 구할 수 있습니다. 컨벡스 헐을 구할줄 몰라도 문제에서 어떤 점이 볼록 껍질에 포함되는지 알려주기 때문에 각도정렬을 슥삭슥삭 하면 구할 수 있습니다. 편의를 위해 반시계 방향의 시작점(x값이 가장 작은 점, 같다면 y값이 가장 작은 점)을 기준으로 기울기를 구해줍니다. 이렇게 하면 다른 모든 점들은 ..

https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 > T; for (int _ = 1; _ m; for (int i = 0; i > a >> b >> x; graph[a][b] = x; graph[b][a] = x; } for (int k = 0; k < m; k++) { for (int i = 0; i < m; i++) { for (int j = 0;..

https://www.acmicpc.net/problem/20938 20938번: 반짝반짝 이제 조금밖에 남지 않은 겨울 기분을 만끽하고 싶은 수현이는 지금부터라도 크리스마스 트리를 장식하려고 한다. 크리스마스 트리는 전구 스트립으로 두른다. 전구 스트립에는 전구 $N$개가 일 www.acmicpc.net dp를 두 번 돌리면 풀리는 문제입니다. $\mathcal{O}(N^2)$에 임의의 $l$과 $r$에 대해서 $l$부터 $r$까지의 조각의 기댓값을 구할 수 있습니다. 이 때 나이브하게 짜면 $\mathcal{O}(N^3)$의 시간이 걸리므로 메모이제이션을 통해 최적화를 해줘야 합니다. 이후 주어진 전구를 어떻게 $k$개 이하의 조각으로 나눠야 최적인지 찾으면 됩니다. 이는 $\mathcal{O}(KN..

https://www.acmicpc.net/problem/17308 17308번: Getting-Up Syndrome In the 21st century, many people have contracted an odd disorder – getting-up syndrome. Symptoms include having great difficulty getting out of bed in the morning and feeling out of sorts even after getting up. As a generally high-spirited teenager, ATM www.acmicpc.net 지문이 영어인데다 길지만 정리하자면 0부터 $m$ 사이의 주어진 쿼리의 연산들을 모두 적용했을 때, 나올 수 있..

https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 매 쿼리마다 $S$가 주어졌을 때 $S$ 안의 정점들 주 연결되어 있는 정점 쌍의 개수를 찾는 문제입니다. 문제를 정리하면, $S$가 주어질 때 $S$안의 정점들이 몇 개의 컴포넌트로 나누어지는지, 그리고 각 컴포넌트에는 몇 개의 정점이 있는지 찾는 문제라고도 할 수 있습니다. 컴포넌트 내의 정점들은 모두 서로 연결되어 있다고 할 수 있으므로 매 컴포넌트마다 컴포넌트 안의 정점에서 두 개..