-
Kudeki Chain과 CUDA Programming
목차 개요 Data Parallelism GPU 구조 Kudeki Chain 문제 설명 CUDA 프로그래밍 방법 최종 코드 마무리 참고 자료 개요 몇 달 전에 Kudeki Chain이라는 문제를 GPU를 사용해서 풀어보았다. 풀이를 간략하게 정리해서 개인 블로그에 포스팅을 했는데, 생각보다 GPU에 관심있는 독자가 많았다. 그래서 이번에는 GPU와 CUDA 프로그래밍에 대해 포스팅을 작성하여 내용을 공유하고자 한다. Data Parallelism Data Parallelism은 다른 데이터들에 대해 동일한 연산을 한 번에 계산하여 프로그램의 실행 시간을 줄이는 방법이다. 배열 A와 B를 더하고, 그 결과를 배열...
-
Python의 큰 정수 표현법 2 - 사칙연산
개요 지난 글에 이어, 이번 글에서는 Python의 int가 실제로 여러 가지 연산을 수행하는 방법에 대해 파헤쳐 보겠습니다. 이전에 살펴본 것처럼 Python은 큰 정수를 표현하기 위해 크기를 변화시킬 수 있는 배열을 사용하고, 배열의 각 원소는 4바이트의 크기를 가지며 $0$ 이상 $2^{30}-1$ 이하의 값을 가집니다. $i$번째 원소를 $i$제곱하여 더한 값이 그 int가 나타내는 실제 값이라고 했었습니다. 당연하지만 CPU가 이런 구조에 대한 직접적인 연산을 지원하지 않기 때문에, 간단한 연산, 비교 연산이나 사칙연산조차도 CPU가 계산할 수 있는 단위까지 쪼개어...
-
2019 한국정보올림피아드(KOI) 중/고등부 문제 풀이
2019 한국정보올림피아드(KOI) 중/고등부 문제 풀이 중등부 1번. 신기한 수 Subtask 2 (100점) 숫자 $N$ 이 주어지면, 해당 수의 일의 자리에 적힌 수는 $N \mod 10$ 이 된다. 이후 숫자를 10으로 나눠주면, 십의 자리, 백의 자리… 에 있던 수들이 모두 일의 자리, 십의 자리로 움직인다. 고로, 이를 반복하면 $O(\log N)$ (입력에서는 최대 8번) 의 단순 연산으로 $N$의 자릿수 합을 알 수 있다. 어떠한 수 $A$ 가 어떠한 수 $B$ 로 나누어 떨어지는 것은, $A$ 를 $B$...
-
shake! 2019 본선 출제 후기
shake!는 경인지역 6개 대학(아주대학교, 경희대학교, 성균관대학교, 인하대학교, 한국항공대학교, 한양대학교 ERICA)의 학생들이 참여하는 대회입니다. 예선을 통해 각 학교 대표 10명이 선발되고, 본선에는 60명의 대표들이 모여 대회를 치룹니다. 이 포스트는 2019년 shake! 본선(7월 7일에 열림)의 출제위원을 맡으면서 있었던 일들과 결과에 대한 후기를 다룹니다. 기타 운영에 관해서는 참여하지 않았기에 후원사 찾기, 출제진이 구성되는 과정 등은 다루지 않습니다. 출제진은 koosaga님과 ainta님, spectaclehong님, 그리고 메인 운영진인 Acka님과 저(hojoon0205)로 이루어졌습니다(모두 acmicpc.net 아이디 기준입니다). 혹시 이 대회의 문제들을 풀어보고 싶으신 분들은 백준...
-
이진탐색의 확장 - 트리에서의 효율적인 탐색
서론 이진탐색은 정렬된 $N$개의 원소가 있을 때, 원하는 수의 위치를 $O(\log N)$ 시간에 찾는 테크닉이다. 이 글에서는 이진탐색을 트리로 확장할 것이다. 그리고 트리에서도 원하는 수의 위치를 $O(\log N)$시간에 찾을 수 있다는 증명과, 비교연산을 최소로 하는 방법을 설명할 것이다. 이진탐색 탐색이란 숨겨진 $a$ 이상 $b$이하의 정수 $x$에 대해, 이 $x$를 찾는 과정이다. 이진탐색에서는 다음과 같은 질문을 할 수 있다: “어떤 수 $y$ 에 대해, $y$와 $x$의 대소관계는 무엇인가?” $y$가 $x$보다 크다는 답이 돌아오면, 우리는 $x$가 $y+1$...