-
coconut99's profile image
coconut99
May 28, 2025
CUDA를 이용한 행렬 곱셈
Introduction 행렬 곱셈은 병렬 프로그래밍에서 가장 중요한 연산 중 하나입니다. 행렬 곱셈은 컴퓨터 그래픽스, 인공 신경망 등 다양한 분야에서 기본적인 연산으로 사용되며, 사용하는 메모리에 비해 연산의 수가 많아 병렬화하기에 적합하기 때문입니다. GPU는 이러한 병렬 연산에 특화된 하드웨어입니다. GPU에는 단순한 연산 수천 개를 동시에 수행하도록 많은 연산 장치가 있으며 CPU의 cache 구조와 비슷하게 각 계층에서 공유되는 메모리가 있습니다. 행렬 곱셈을 위한 cuBLAS와 같은 라이브러리가 있으며, 이 글에서 소개할 내용은 해당 라이브러리를 구현하는 데 사용된 테크닉의 일부입니다....
-
coconut99's profile image
coconut99
February 25, 2025
LCS 알고리즘 최적화
개요 LCS(Longest Common Subsequence) 문제는 두 문자열의 공통 부분 수열 중 가장 긴 것을 찾는 문제로, 컴퓨터과학에서 가장 고전적이면서 중요한 문제 중 하나입니다. 이 글에서는 이 문제를 해결하는 간단한 Dynamic Programming 해법부터, 이것의 공간 복잡도를 개선한 Hirschberg 알고리즘과, 일반적인 문자열에서 더 효율적인 Hunt-Szymanski 알고리즘을 소개할 것입니다. 그리고 이들을 비트 집합을 이용해 더욱 최적화하는 방법을 다룰 것입니다. 간단한 DP 해법 $DP[i][j]$를 $A$의 길이 $i$인 접두사와 $B$의 길이 $j$인 접두사의 LCS 길이로 정의하면 다음과 같은 점화식으로 $A$와...
-
coconut99's profile image
coconut99
March 27, 2024
Polya's Enumeration Theorem을 이용한 카운팅 문제 해결
개요 Polya’s Enumeration Theorem(포여 열거 정리)는 어떤 작용에 대한 equivalence class의 개수를 구할 때 사용됩니다. 대표적인 예시로 돌리거나 뒤집어서 같은 것을 하나로 볼 때, 서로 다른 목걸이의 개수를 구하는 문제가 있습니다. 이 글에서는 Burnside Lemma와 그것의 일반화인 Polya’s Enumeration Theorem을 소개한 후 이를 적용하여 문제를 해결하는 과정을 서술하겠습니다. 관련 문제는 백준 문제집 또는 알고리즘 분류에서 찾아볼 수 있습니다. 해당 태그를 가진 문제가 9문제에 불과한 만큼 CP에서 자주 등장하는 주제는 아닙니다. 그렇지만 특정 형태의 카운팅 문제를...