The Story of Joon

Linear Algebra in Problem Solving (1) (현 포스트) Linear Algebra in Problem Solving (2) Linear Algebra in Problem Solving (3) 선형대수학(linear algebra)은 벡터 공간(vector space)과 선형 변환(linear transformation)에 대해서 다루는 학문으로, 여러 분야에서 많은 응용이 되고 있고 수학에서의 중요성 또한 매우 높다. 컴퓨터 과학도 예외는 아닌데, 이런 이유로 많은 학교에서 컴퓨터 과학/공학과에서 기초 선형대수학을 필수 과목으로 지정하기도 한다. 이 포스트 시리즈에서는 PS에서 등장하는 선형대수학 관련 문제들을 해결하기 위한 여러 가지 선형대수학 알고리즘을 다룰 예정이다. 일반..

3차원 컴퓨터 그래픽스에서 회전(rotation)은 매우 중요한 개념이다. 대학에서 또는 독자적으로 컴퓨터 그래픽스의 원리를 공부한 적이 있는 독자라면 3차원 회전을 사원수(quaternion)로 표현하는 방식에 대해 본 적이 있을 것이다. 단위 벡터(unit vector) \((x, y, z)\)를 회전축으로 반시계 방향으로 \(\theta\)만큼 회전시키는 동작을 사원수 방식으로는 아래와 같이 나타낸다: \[\cos(\theta/2)+x\sin(\theta/2)\mathbf{i}+y\sin(\theta/2)\mathbf{j}+z\sin(\theta/2)\mathbf{k}\,.\] 사원수는 우리가 익히 아는 일반적인 실수나 복소수와는 또 다른 시스템이다. 놀랍게도, 이렇게 나타내면 마법과 같이 3차원 ..

BOJ 11066 - 파일 합치기 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 이 문제는 2015년 ACM-ICPC 예선에 나왔던 문제로, DP 테이블을 정의하면 \(O(K^3)\)의 시간복잡도로 어렵지 않게 풀리는 문제다. 난이도는 solv..