티스토리

혜아의 아무말

검색하기

블로그 홈

혜아의 아무말

blog.kyouko.moe/m

이혜아 님의 블로그입니다.

구독자: 6

방명록 방문하기

주요 글 목록

SCPC 2022 본선 풀이 SCPC 2022 2차 대회가 9월 3일 오후 1시부터 4시간동안 진행되었다. SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다. 이 게시글에서는 해당 문제의 풀이를 다룬다. 불일치도 요약 $0$이상 $1$ 이하의 실수 $N$개가 주어집니다. 이 중 $L$이상 $R$이하인 것의 개수를 $F(L, R)$이라고 합시다. 이 때, 모든 $0 \le L \le R \le 1$에 대해, $\left\lvert \frac{F(L, R)}{N} - (R-L)\right\rvert \le D$를 만족하는 최소의 실수 $D$를 구하세요. 풀이 더보기 $x$ 이하인 실수의 개수를 $f(x)$라고 하면, 식은 충분히 작은 $\varepsilon$에 대해 $\lef.. 공감수 7 댓글수 0 2022. 9. 3.
SCPC 2022 2차 풀이 SCPC 2022 2차 대회가 8월 6일 오전 9시부터 12시간동안 진행되었다. SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다. 이 게시글에서는 해당 문제들의 풀이를 다룬다. 1. 수열 연산 문제를 요약하면, 주어진 수열 $A$의 모든 수를 주어진 수 $K$ 이상으로 만들기 위해서 최소 횟수의 연산을 사용하고, 이 때 가능한 총 비용의 최솟값을 구하는 문제다. 한 연산은 연속된 구간의 모든 수를 $1$ 증가시키고, 이 연산의 비용은 구간의 길이이다. 더보기 연산을 수열 전체에 사용한다고 생각하면 사용해야하는 연산의 횟수는 $\max(K - \min A, 0)$이다. 이 이하로 사용해서는 최솟값을 $K$ 이상으로 만들 수 없다. 이제 가능한 .. 공감수 1 댓글수 0 2022. 8. 6.
SCPC 2021 2차 풀이 SCPC 2021 2차 대회가 8월 7일 오전 9시부터 12시간동안 진행되었다. SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다. 이 게시글에서는 해당 대회 문제의 풀이를 다룬다. 1. 원 안의 점 문제를 요약하면, 원점 $(0, 0)$을 중심으로 하는 반지름 $R$인 원 내부에 들어있는 좌표가 모두 정수인 점의 개수를 세는 문제이다. 단, 원의 경계에 놓인 점은 생각하지 않는다. ($R \le 200\,000$) 풀이는 간단하다. $x$좌표가 $a$인 위치에 대해서 $y$좌표로 가능한 값은 $-\sqrt{x^2-a^2}$ 초과 $\sqrt{x^2-a^2}$ 미만인 값이고($-R < a < R$), 정수점의 개수는 $\sqrt{x^2-a^2}.. 공감수 3 댓글수 0 2021. 8. 7.
SCPC 2021 1차 풀이 SCPC 2021 1차 대회가 7월 16일 오후 3시부터 24시간동안 진행되었다. SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다. 이 게시글에서는 해당 문제들의 풀이를 다룬다. 1. 친구들 문제를 요약하면, i 번 정점과 i+Di 번 정점을 연결 할 때, (1≤Di≤N, i+Di가 N을 넘으면 연결하지 않음), 연결 성분의 개수를 계산하는 문제이다. 그래프를 만들어주고 DFS와 같은 방법을 이용해서 연결 성분을 세어 주면 끝나는 문제이다. 이 문제에는 같은 시간복잡도의 좀 더 간단한 풀이가 있는데, i+Di가 N을 넘는 수의 개수가 답이 된다. 이를 증명하기 위해서는 다음과 같은 관찰이 필요하다. - 이 그래프에는 사이클이 존재하지 않는다... 공감수 0 댓글수 0 2021. 7. 17.
Merry Problem Solving 4일차 Merry Problem Solving 4일차 (12/24) 입니다! ARC103F - Distance Sums 문제: i번째 정점부터, 다른 모든 정점까지의 거리의 합이 Di인 트리가 있으면 아무거나 출력하고, 없으면 -1을 출력하라. 단, Di는 모두 다르다. 풀이: 먼저 문제의 Special Judge를 생각해봅시다. 모든 i에 대한 Di를 어떻게 구하면 좋을까요? 일단, D1을 1번에서 dfs를 돌린 후에 모든 높이의 합으로 구할 수 있습니다. 이제 다른 모든 Di를 구해야 하는데, 하나의 Di를 구하면 다른 Di를 구할 수 있습니다. 이는 다음의 정리를 이용합니다. 정리. T(u)를 u까지의 거리가 v까지의 거리가 더 짧은 정점의 집합이라고 정의하고, T(v)에 대해서도 마찬가지로 정의하자. u.. 공감수 0 댓글수 0 2018. 12. 26.
Merry Problem Solving 3일차 Merry Problem Solving 3일차 (12/23)는... 제끼고 봄베이 사파이어와 토닉 워터와 레몬을 섞어서 친구와 맛있게 마셨습니다. 벌금 7000원 끄악 공감수 0 댓글수 0 2018. 12. 24.
Merry Problem Solving 2일차 Merry Problem Solving 2일차입니다! 12/22에 푼 문제들입니다. 091F - Strange Nim 문제: Nim 게임을 하는데, i번째 무더기에는 처음에 Ai개의 돌이 있고, i번째 무더기에 X개의 돌이 있을 때 최소 1개에서 최대 X/Ki (나머지는 버림)개 사이의 갯수에 돌만 가져갈 수 있습니다. 서로 번갈아가면서 하나의 무더기에서 몇개의 돌을 번갈아가면서 가져가고, 더 이상 돌을 가져갈 수 없는 사람이 진다고 했을 때, 첫째 사람이 이기는지, 둘째 사람이 이기는지를 구하시오. 풀이: 이 문제는 그냥 Nim 게임(모든 K가 1인 경우)를 푼다고 하면, Impartial Game에서의 Sprague-Grundy Theorem를 사용합니다. 이에 관한 정보는 위키피디아 게시글에서 얻을.. 공감수 0 댓글수 0 2018. 12. 24.
Merry Problem Solving 1일차 Merry Problem Solving을 하고 있습니다! 2018/12/21부터 2019/1/1 까지 매일 앳코더(https://atcoder.com)의 정해진 점수만큼의 문제를 푸는 스터디입니다! 백준 온라인 저지 슬랙(https://acmicpc.net, https://acmicpc.slack.com) 의 #2018_merry_ps 채널에서 진행하고 있습니다. 저는 하루에 총 1400점을 풀기로 했습니다. 사실 앳코더는 점수에 따라 문제의 난이도차가 꽤 나기 때문에 ARC의 F번을 2개 풀어서 1400점을 채우는게 보통이나... 오늘 너무 바빴기 때문에 ARC의 D 3문제를 풀었습니다. 문제의 한국어로 간단하게 정리한 것과 풀이를 적습니다. 091D - Remainder Remainder 문제: 두 .. 공감수 0 댓글수 0 2018. 12. 21.
테스트 데이터 만들기: Anti-Hash test / Anti-Javasort test 테스트 데이터를 만들 때 즐겨 쓰는 데이터 들을 첨부합니다. 이 데이터들은 SCPC (삼성전자 대학생 프로그래밍 경진대회) 에도 활용 되었습니다. 내용이 간략하게만 쓰여져 있고, 정리 할 일이 있으면 길게 작성하도록 하겠습니다. (판도라의 상자이므로 열지 마십시오) 공감수 4 댓글수 0 2018. 10. 11.
선형 점화식의 빠른 계산 과 같은 선형 점화식을에 계산 해야하는 문제가 나와서 write-up을 해봤습니다. n번째 항까지의 모든 항을 계산하는 방법이고, 풀이가 생각보다는 깔끔합니다. 지금은 일단 간략하게 쓴 것이고, 제출을 해야 할 때 되면 아마 보강을 해서 좀 더 써서 올리지 않을 까 싶습니다. 문제: https://csacademy.com/contest/round-9/task/jetpack/ 공감수 2 댓글수 0 2018. 7. 24.
HYEA Online Judge 개발 최근에 블로그에 포스팅을 잘 하지 않았네요. 휴학하고 아예 머릿속에서 지워버린 것 같네요. 저만의 Online Judge를 만들고 싶다는 생각이 생겨서, HYEA Online Judge를 개발했습니다. 주소는 다음과 같습니다.: http://cms2.kyouko.moe:5000/지금은 베타 버전이고, 다양한 버그들이나 race condition들이 존재할 수 있으며 계속 수정중입니다. 오류가 있거나 오동작 한다고 생각하면 알려주시기 바랍니다. 또한 문제들이 예전 블로그에 포스팅한, 교육용 문제 모음에 있는 문제들이기 때문에, 채점을 원하시면 저한테 메일을 (사이트에 나와있음), 사용하고 싶은 아이디와 함께 보내주시기 바랍니다. 단체로 프로그래밍 사이트를 사용해도 괜찮습니다.덧글은 제가 확인을 잘 못하지만.. 공감수 6 댓글수 0 2018. 7. 6.
Simple Cubic General Maximum Matching Algorithm General Maximum Matching Algorithm에 대해 삽질을 많이 했고, 다른 사람이 삽질을 하지 않기 위해서 이 글을 쓰려고 합니다. 이 글은 매칭에 대해 잘 이해를 하고 있다고 가정하고, 이분그래프의 매칭을 찾는 법을 아는 사람을 위한 글입니다. 이분그래프에 대해서는 O(EV^0.5) 풀이가 존재하고, 시간복잡도 증명이 어렵지만 그 부분을 제외하고는 이해할 만 합니다. 사실 일반그래프에 대해서도 마찬가지가 존재하나, 구현하기가 굉장히 어렵습니다. 그래서 O(V^3) 시간 알고리즘을 소개하려고 합니다. 먼저 General Graph의 Matching에 어려움의 대해 설명을 하겠습니다. odd는 정점에서 간선을 홀수 번 타고 갈 수 있는 점, even은 정점에서 간선을 짝수번 타고 갈 수.. 공감수 3 댓글수 0 2018. 3. 22.
Run@KAIST 봄 연습 3주차 Run@KAIST 봄 연습 3주차 문제입니다. 앞으로 문제들은 이정도 난이도로 구성될 것 같습니다. 8문제를 준비했습니다. 공감수 0 댓글수 0 2018. 3. 20.
Run@KAIST 봄 연습 2주차 에디토리얼. 2주차 에디토리얼입니다. 문제의 출처는 다음과 같습니다.: A to Z (Atcoder ABC053B: https://beta.atcoder.jp/contests/abc053/tasks/abc053_b)직사각형 (Atcoder ARC081A: https://beta.atcoder.jp/contests/arc081/tasks/arc081_a)음식 맛있게 먹기 (Maximum Sum Subarray 연습문제)조상 (Dfs Ordering 연습문제)어비스의 탐험가 (Running Median 연습문제)도시 연결 (Minimum Spanning Tree 연습문제)혜아의 타이핑 (Atcoder ARC059D: https://beta.atcoder.jp/contests/arc059/tasks/arc059_d)돌 (.. 공감수 0 댓글수 0 2018. 3. 14.
Run@KAIST 봄 연습 2주차 Run@KAIST 봄 연습 2주차 문제입니다. 저번 주 보다는 문제의 난이도를 올렸습니다. 역시 8문제를 준비했습니다. P. S. 배점의 수정이 있었습니다. 공감수 0 댓글수 0 2018. 3. 11.
Run@KAIST 봄 연습 1주차 에디토리얼. 1주차 에디토리얼입니다. 문제의 출처는 다음과 같습니다.: 쉬운 계산기 (Atcoder ABC050A: https://beta.atcoder.jp/contests/abc050/tasks/abc050_a)세 수의 합 (Atcoder ABC051B: https://beta.atcoder.jp/contests/abc051/tasks/abc051_b)팩토리얼 (Atcoder ABC052C: https://beta.atcoder.jp/contests/abc052/tasks/arc067_a)혜아 인 어비스 (Priority Queue 연습문제)집단 (Disjoint set 연습문제)계산기 (계산기 구현 연습문제)구간의 합 (Segment Tree 연습문제)피라미드 (Atcoder AGC006D: https://be.. 공감수 0 댓글수 0 2018. 3. 9.
Run@KAIST 봄 연습 1주차 Run@KAIST 봄 연습을 9주동안 진행하게 되었습니다...교육용 문제를 기반으로 하고 풀이를 쓰려고 하는데 강제성이 없으면 절대로 쓰지 않을 것 같아 스스로 족쇄를 채웠습니다... Run@KAIST 봄 연습 1주차 문제입니다. 8문제를 준비했고, 첫 주라서 쉬운 문제들입니다. 공감수 1 댓글수 0 2018. 3. 4.
알고리즘 교육용 문제 세트 일이 있어서 교육용으로 만든 알고리즘 문제 세트가 꽤나 좋은 세트 같아서 퍼블릭하게 공개하고 싶어졌습니다. 같이 문제를 만든 사람은, kajebiii 와 KENNYSOFT 입니다. 문제들의 난이도는 KOI 중등부 1번 ~ 고등부 3번 정도인 것 같습니다. 문제들이 꽤 넓은 분야를 다루고 있으니 문제를 풀고 풀이를 들으면 실력이 오르는 세트라고 생각합니다. 문제들은 잘 알려진 문제들도 있고, 만든 문제들도 있으며 다른 곳에서 가져오거나 변형한 문제들도 있습니다. 블로그에 문제와 풀이를 계속 올릴 생각입니다. Logical Thinking은 일이 바빠서 잘 안 올리고 있네요... 혹시 문제가 지금 궁금하고 풀어보실 생각이 있거나 관심이 있으시면 이 게시글에 비밀 덧글로 이메일 주소를 달아주시거나 이메일 sa.. 공감수 0 댓글수 0 2018. 2. 5.
[문제 제작 후기] BAEKJOON 15328 - 산타의 선물 이 문서는, acmicpc.net 15328번 산타의 선물 문제를 만들게 된 계기, 풀이 그리고 테스트 데이터를 만든 방법에 대해 설명합니다. 문제 스포일러를 원치 않는 분은 읽지 않아주셨으면 합니다. 문제를 단순화 하면 다음과 같습니다.인지 아닌지 판단하세요. 이 문제를 만들게 된 계기는 어떤 트윗에서 시작합니다. 아니... 그... 저..... pic.twitter.com/agXpmPH9r3— 시프트 / shift* (@shiftpsh) December 27, 2017 UCPC 2016 D번문제인 Flowey's Love입니다. 입력과 출력이 전부다 정수이지만, 실수오차에 매우 민감한 가혹한 문제입니다. 사실 데이터가 충분히 강한지도 의문입니다. 왜냐하면 이 문제는 유리수, 혹은 제곱근, 혹은 그 수.. 공감수 7 댓글수 0 2017. 12. 28.
[Logical Thinking] 4. 시간복잡도 시간복잡도(Time complexity)는 어떤 프로그램이 수행하는데 걸리는 시간을 말한다. 프로그램이 빨리 실행 될 수록 이로운 점이 많기 때문에, 우리는 시간복잡도를 줄이려고 노력한다. 프로그램이 수행하는데 걸리는 시간과 시간복잡도에 대해 알아보자. 참고로 이 글에는 이해하기 어려울 수 있는 수학적인/공학적인 내용이 들어있다. 이해하지 않고 읽기만 해도 되는 내용에는 ⁺표시를 해놓겠다. 이외의 내용은 최대한 이해하기 쉽게 작성하려고 했다. 프로그램의 실행 시간 최신 프로세서 들은 어느정도의 연산을 할 수 있을까? 필자가 쓰고 있는 컴퓨터의 CPU는 Intel(R) Core(TM) i7-7700HQ @ 2.80GHz 이다. 여기서 2.80GHz라는 의미는, 1초에 28억번 "클럭"을 돌릴 수 있다는 것.. 공감수 2 댓글수 0 2017. 11. 30.
[Logical Thinking] 현재까지의 포스트 모음 Logical Thinking 게시글의 현재까지의 제목과 게시물 링크를 모아놓고, 새로운 게시글이 생길 때 마다 업데이트 하도록 하겠다. [Logical Thinking] 1. 수학적 귀납법 [Logical Thinking] 2. 루프 불변조건(Loop-invariant) [Logical Thinking] 3. 동적 계획법 [Logical Thinking] 4. 시간복잡도 공감수 1 댓글수 0 2017. 11. 25.
[Logical Thinking] 3. 동적 계획법 동적 계획법(Dynamic Programming)은 프로그래밍을 할 때 생기는 문제를 작은 문제들로 나눠서 풀고, 그것을 합치는 방법이다. 그 과정에서 이미 풀어봤던 문제가 발생하면, 문제를 다시 풀지 않고, 예전에 풀었던 정보를 가져오는 방법이다. 이것 때문에 분할 정복과는 다른 면이 있다. 글들은 최대한 이해하기 쉽게 작성하려고 했다. 동적 계획법동적 계획법을 최대한 쉽게 설명해 보려고 노력 했고, 내가 할 수 있는 제일 쉬운 설명을 가져왔다. 숫자를 세어 보도록 하자, 첫번째 줄에는 1이 몇개 있는가? 1 1 1 1 1 1 1 1 1 1 아마 대부분이 세어 보지 않았을 거라고 생각하지만, 1이 10개가 있다. 그러면 여기서 1을 하나 더 그었다고 생각해 보자. 1 1 1 1 1 1 1 1 1 1 1.. 공감수 2 댓글수 0 2017. 11. 25.
[Logical Thinking] 2. 루프 불변조건(Loop-invariant) 조건문과 반복문은 프로그래밍 언어를 단순한 계산기에서, 프로그래밍을 할 수 있는 도구로 만들어 주는 열쇠일 것이다. 오늘은 반복문을 사용할 때 많은 프로그래머들이 (익숙해서든, 익숙하지 않아서든) 잊어버리는, 루프 불변조건(Loop-invariant)에 대해 다뤄 보려고 한다. 최대한 이해하기 쉽게 작성하려고 했다. 프로그래밍을 하면서 가장 많이 만나는 것 중 하나는 반복문이다. 반복문은 C/C++과 Python에서 다음과 같은 꼴이다. (여기서 i++ 은 i += 1, i를 i의 다음숫자로 바꾼다.) 이다. C, C++: for(int i=0; i 공감수 5 댓글수 0 2017. 11. 21.
[Logical Thinking] 1. 수학적 귀납법 예전에 트위터에 글을 쓰겠다고 말 해 놓고, 쓰지 않은 글들이 존재한다. 그 중 하나를 지금부터 다시 시작해보려고 한다. 블로그에 로지컬씽킹으로 논리적으로 생각하는 법에 대해서 써보려고 합니다. 아마 첫 글이 오늘 올라올 것 같네요 pic.twitter.com/h5Nk9c2QiI— 이혜아@void (@mega_kina) August 28, 2017 아마 첫 두개는 이전 포스트의 내용을 다듬는 것이 될 것이다. 참고로 이 글에는 이해하기 어려울 수 있는 수학적인 내용이 들어있다. 이해하지 않고 읽기만 해도 되는 내용에는 ⁺표시를 해놓겠다. 이외의 내용은 최대한 이해하기 쉽게 작성하려고 했다. 프로그래머들은 대개로 셀 수 있는 것들을 다룬다. 그리고 객체에 번호를 붙이는 것에 익숙해져 있다. 예를들면 배열의.. 공감수 2 댓글수 0 2017. 11. 20.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.