전체 글

[16140] 정수론과 응용

가우시안 수 두 개 주고 GCD를 찾으라는 문제다. 3개의 subtask로 나누어져 있는데, 첫 번째는 새로운 차원을 사용하지 않는 정수 GCD, 두 번째는 아마도 좀 나이브하게 찾는(아니면 arctan 같은 걸 쓴다거나... 우웩.) 방식을 노린 것 같고, 마지막 subtask까지 전부 맞으려면 그보다는 좀 더 머리를 쓰는 방식을 요구하는 것으로 보인다. 우선 이 '가우시안 수' 라는 녀석을 살펴보자. 사실 그냥 복소수다. 이 가우시안 수 간의 곱셈은 다음과 같이 표현됨을 우리는 잘 안다. 두 복소수 $n = a + bi, m = c + di$에 대하여, $n \cdot m = (ac-bd) + (ad + bc)i$. 가우시안 수의 나눗셈에 대해 생각해 보자. 일단 가우시안 수를 서로 나눌 수는 있다...

[13334] 철로

13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 많은 블로그들에서는 Priority Queue를 사용하는 해설을 적어 놓았고 사실 Priority Queue를 쓰는 게 낫긴 한데, 여기서는 Priority Queue를 안 쓰는 방식을 소개한다. 문제의 철로 L의 오른쪽 끝과 수직선 상에 존재하는 가장 왼쪽의 건물이 처음 만날 때부터 왼쪽 끝이 가장 오른쪽의 건물을 지날 때까지 이동한다고 생각하자. 이 상황을 L이 움직임에 따라 각 건물이 L에 추가되었다가 제거..

[Div2 774] 3솔

15번째로 참여한 Codeforces Round #774 (Div. 2)에서 블루 퍼포를 따냈다. ABC를 솔하고 E를 파다가 실패했는데, 3솔만으로 퍼포가 나온 걸 보면 빠르게 푸는 게 꽤 큰 영향을 주긴 하나보다. D는 복잡할 것 같아서 대충 보고 때려치우고 그나마 친숙한 정수론 얘기 하는 E를 풀 계획이었는데 뭐가 문제였는지 자꾸 유사하면서도 다른 답만 뿌려대서 결국 못 풀고 마무리. 포함-배제를 잘못 짰는지... 오버플로우가 문제였는지... 그래도 일단은 지금까지 참여한 대회 중 최고 기록이고, 레이팅도 91이나 올랐으니 아쉬우면서도 만족스러운(??) 대회였다. 어떻게 풀 지는 잡았는데 구현을 시간 내로 못 해서 마지막 1솔을 놓치는 경우가 많았다. 기초적인 구현 속도를 좀 높일 필요가 있겠고, ..

[2731] 1379와 세제곱

2731번: 1379와 세제곱 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄 부터 T개 줄에는 테스트 케이스의 정보가 주어진다. 각 테스트 케이스는 숫자 하나로 이루어져 있고, 이 수는 문제에서 설명한 S이다. S는 www.acmicpc.net 뭔가 허무하게 풀리는 정수론 문제. 우선 문제에서 준 네 수 1, 3, 7, 9를 살펴보자면, $1^3\equiv 1\bmod 10$ $3^3\equiv 7\bmod 10$ $7^3\equiv 3\bmod 10$ $9^3\equiv 9\bmod 10$ 이다. 따라서 $S \bmod 10$의 값으로 찾아야 하는 수 $x$의 첫째 자릿수를 구할 수 있다. ($x_1$) 이제 한 자리씩 $x$의 왼쪽에 붙이면서 수를 찾으면 되는데, 방법은 다음과 같다. ${..

학생 기록 관리 시스템

Windows x64 환경에서 동작합니다. .NET 5.0 실행 환경이 필요합니다. 현재 최신 버전은 1.0.0입니다. 2022-02-28: 1.0.0 프로젝트 배포 이전 버전 더보기 아직 이전 버전의 릴리즈 노트가 없습니다. 학생 기록 관리 시스템 (SchoolRecordManagementSystem)은 학교 학생들의 여러 활동을 관리하고 기록하는 데 도움을 주는 소프트웨어입니다. 이하는 소프트웨어 사용 설명입니다. 학생들의 활동을 관리할 수 있는 페이지입니다. [활동 추가] 버튼을 눌러 새로운 활동을 추가할 수 있고, 리스트에서 활동을 선택해 활동의 제목이나 활동 내용을 변경할 수 있습니다. 사진에서 확인할 수 있듯이 중괄호 '{ }' 사이에 0~9 사이의 숫자를 입력하면 이후 학생 정보 관리 페이지..

블로그 이전

기존 블로그 (https://blog.naver.com/dmsvmail)에서 여기로 옮겼다. 네이버 블로그는 영 아니라 전부터 블로그를 옮겨야 하지 않나 싶긴 했는데 github에 react로 만들어서 올릴까 하다가 귀찮아서 그냥 티스토리. 이전 블로그에서처럼 백준 푼 거 올리고, 가끔 Codeforces 한 거 기록 남겨서 나중에 구경하고, 뭐 나중에 대학 가서든 혼자 공부해서든 배우는 내용들 있으면 정리해서 올려보기도 하고... 할 예정이다. 이렇게라도 써놔야 쓰든 말든 하지 귀찮아서 참

Codeforces 민트 달성!

%2022. 1. 31. 12:11에 작성된 글입니다% 어제 있었던 Codeforces Round # 769 (Div. 2)에서 빠른 3솔을 하고 83점을 얻어 민트로 올라왔다. 27일에 있었던 div2 # 768에서는 잠을 못 잔 채로 풀어서 실수투성이 2솔밖에 못 했는데 이번에는 괜찮게 나와줘서 다행이다. 이제 딥2는 4솔을, 레이팅은 블루를 목표로 달려 보자... 기초 알고리즘 DP나 그래프 탐색같은거 연습 좀 해야 할 듯.

오랜만에 Codeforces

%2022. 1. 4. 12:19에 작성된 글입니다% 원래 CF를 잘 안 했다. 시간 재면서 경쟁하는 stress 하의 상황에서 문제를 풀기보다는 천천히 고민하면서 풀기를 더 선호하기도 하고, 또 contest 열리는 시간이랑 내 시간대랑 잘 안 맞아서도 그랬고... 아무튼 오랜만에 들어가보니 Hello 2022 contest가 내일 열립니다! 하길래 이번엔 좀 참가해보자... 하고 register 해 놨다. 그리고 나서 대회 한시간 전에 interactive problem guide 문제 풀어보고 시간 맞춰서 대회 들어갔다. 결과는... 망했다. A랑 C 풀고 이상한 세그트리 짜다가 시간 다 버림. ㅠㅠ BOJ에서 시간 생각 안 하고 풀 때랑은 또 달라서 재밌었다. 당분간 코포도 좀 해야겠다. 블루나 ..