All Posts

함수의 정의 함수는 어떤 집합의 각 원소를 다른 어떤 집합의 각 원소에 유일하게 대응시키는 관계를 말한다. 예를 들어 $ X $ 와 $ Y $ 가 집합일 때 $ X $ 에서 $ Y $ 로의 함수 $ f $ 는 $ f : X \to Y $ 로 나타낸다. 이는 카테시안 곱 $ X \times Y $ 의 부분집합으로 정의되며 카테시안 곱은 $ \{ (x,y) \mid x \in X, y \in Y \} $ 이다. 각 $ x \in X $ 에 대해 정확히 하나의 $ y \in Y $ 가 존재하여 $ (x,y) \in f $ 를 만족하는 성질을 가진다. 이를 $ f(x) = y $ 라 표기한다.이때 집합 $ X $ 를 정의역(domain)이라 하고, 집합 $ Y $ 를 공역(codomain)이라 한다. $ f $..

바닥 함수 (Floor Function) $$ \lfloor x \rfloor = \max \{ n \in \mathbb{Z} \mid n \leq x \} $$입력값 이하의 가장 큰 정수를 반환하는 함수로, 내림 함수, 버림 함수, 최대 정수 함수라고도 한다. 기호로 표기할 때 $ [x] $ 를 사용하기도 한다.예를 들어 $ \lfloor 8.5 \rfloor = 8 $ 이고, $ \lfloor -8.5 \rfloor = -9 $ 이다.바닥 함수를 이용해서 실수의 소수 부분만 분리도 가능하다. 예를 들어 $ 8.12 $ 의 소수 부분은 $ 8.12 - \lfloor 8.12 \rfloor $ 이다. 천장 함수 (Ceiling Function) $$\lceil x \rceil = \min \{ n \in..

https://www.acmicpc.net/problem/20436문제 주어진 키보드 조건에서 주어진 문자열을 타이핑하는 데에 걸리는 시간의 최솟값을 구하는 문제이다. 풀이 키보드 좌표를 구하는 부분과 키보드 타이핑 시간을 구하는 부분이 필요하다.키보드 좌표를 구하는 부분은 아래와 같이 리스트 속 문자열을 만들고, 여기서 해당 문자를 탐색하는 방식으로 만들어도 된다.keyboard = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']그러나 오른손과 왼손을 구분하는 것 때문에 각 문자에 좌표를 설정해서 딕셔너리로 찾는 것이 더 직관적이고 좋은 것 같아 아래 코드와 같이 구현했다.타이핑 시간 계산은 문제에서 제시한 방식을 그대로 사용하였다. 코드 lkeyboard = {'z':(0,0),..

기댓값과 분산 $ E(X) $ | 기댓값 (Expected Value)$$ E(X) = \sum_{i=1}^{n} x_i p_i $$$$ E(X) = \int_{-\infty}^{\infty} x f(x) dx $$어떤 확률변수가 평균적으로 가지리라 기대되는 값이다. 즉 확률 과정에서 얻을 수 있는 모든 값에 확률로 가중 평균한 것이다. 이산확률변수는 $ \sum $ 을 사용하여 가중 평균하고, 연속확률변수는 $ \int $ 을 사용하여 가중 평균한다. $ Var(X) $ | 분산 (Variance)$$ Var(X) = \sum_{i=1}^{n} (x_i - E(X))^2 p_i $$$$ Var(X) = \int_{-\infty}^{\infty} (x - E(X))^2 f(x) dx $$각 확률변수 값이..

https://www.acmicpc.net/problem/31418문제 정해진 스펀지 내에서 일정 시간이 흘렀을 때 바이러스들의 분포의 수를 구하는 문제이다. 바이러스들은 1초에 대각선, 상하좌우 중 한 방향으로 한 칸 이동하거나 움직이지 않을 수 있다. 풀이 바이러스가 어디에 있을 수 있냐를 구하는 문제이다. 바이러스는 좌우로는 최대 $ T $ 만큼 이동할 수 있고, 상하로도 최대 $ T $ 만큼 이동할 수 있다. 대각선도 마찬가지이니 바이러스 위치는 $ (2 \times T + 1) \times (2 \times T + 1) $ 개의 가능성을 가진다.그런데 바이러스는 스펀지에서 벗어나진 못하므로 바이러스가 이동하다가 좌우측, 상하측으로 스펀지에 막힐 가능성을 생각해야 한다. 만약 바이러스가 이동할 수..

배열  자리를 나타내는 인덱스(index)와 동일한 자료형의 데이터 값으로 된 집합이 연속적인 형태로 되어 있는 자료구조이다. 연속적인 형태라는 것은 데이터 값이 메모리에 저장될 때 순차적으로 저장된다는 뜻이다. 이때 순차적으로 붙은 각 번호가 인덱스이다.또한 데이터의 자료형이 모두 동일하기 때문에 특정 값에 접근할 때 그 값의 인덱스를 알 수 있다면 메모리 주소 역시 알 수 있다. 즉 원소들이 연속적으로 배치되어 있기 때문에 각 원소에 접근할 때 시간복잡도가 $ \mathcal{O}(1) $ 인 임의접근(random access)이 가능하다.대부분 언어에서 기본적으로 별도의 라이브러리 없이 지원하며, 인덱스를 통해 배열의 값에 접근할 때 [] 를 주로 사용한다. 또한 대부분의 언어에서 배열 인덱스의 시..

삼각행렬의 성질 삼각행렬은 하삼삭행렬(lower triangular matrix)와 상삼각행렬(upper triangular matrix)로 나뉜다.어떤 두 행렬이 하삼각행렬이고 서로 행렬곱 연산이 가능할 때 두 행렬의 곱은 하삼각행렬이다. 또한 만약 하삼각행렬인 행렬이 가역행렬이라면 이 행렬의 역행렬은 하삼각행렬이다. 당연하게도 하삼각행렬과 하삼각행렬을 더하면 하삼각행렬이 나온다. 상삼각행렬 역시 같은 성질을 지닌다. 즉 각 삼각행렬은 덧셈, 곱셈, 역행렬에 대해 닫혀있다. LU 분해 단위행렬에 기본 행 연산을 했을 때 나오는 기본행렬은 단위행렬, 상삼각행렬, 하삼각행렬, 혹은 치환행렬이다. 치환행렬(permutation matrix)은 단위행렬에서 행을 교환하여 얻은 행렬이다.가우스-요르단 소거법으로..

유일한 해 연립일차방정식을 $ AX = B $ 꼴로 나타낼 때, 만약 $ A $ 가 $ n $ 차 정사각행렬이면서 가역행렬이고, $ B $ 가 $ n \times 1 $ 행렬이라면 이 연립일차방정식은 유일한 해 $ X = A^{-1}B $ 를 갖는다. 증명은 다음과 같다.$ n $ 차 정사각행렬을 $ A $ 는 가역행렬이므로 $ A^{-1} $ 이 존재한다. 연립일차방정식 $ AX = B $ 양변에 $ A^{-1} $ 을 곱하면 $ A^{-1}(AX) = A^{-1}B $ 이다. 이는 $(A^{-1}A)X = A^{-1}B $ 이고, $ I_n X = A^{-1}B $ 이며, $ X = A^{-1}B $ 이다. $ A $ 의 역행렬은 유일하므로 $ X = A^{-1}B $ 는 유일한 해이다. 동차연립일차..

자료의 분포 위치측도, 중심위치측도, 산포측도는 대략적으로 자료의 대표적 성격을 보여준다. 그런데 단순히 이러한 측도들을 통해서는 자료의 비대칭성을 보일수는 없다. 자료의 분포가 좌우대칭이라는 전제가 있다면 평균과 분포만 있어도 대략적인 그림을 그릴 수 있겠지만, 그렇지 않다면 분포가 어느 방향으로 얼마나 기울어져 있는지 확인하고, 표현해야 자료의 특성을 정확히 표현할 수 있다. 왜도 (Skewness) 자료의 분포가 기울어진 정도를 의미한다. 왜도가 0 일 때 좌우대칭이며, 음수라면 오른쪽으로 긴 꼬리를 가진, 즉 왼쪽으로 치우쳐진 모양을, 양수라면 왼쪽으로 꼬리를 가진, 즉 오른쪽으로 치우쳐진 모양을 가진다. 왜도가 0 일 때가 위 그림에서 주황색, 음수일 때가 초록색, 양수일 때가 파란색 그래프이다..

위치측도 (Measures of Position) 자료를 정렬했을 때의 위치를 나타내는 측도들이다. 표본 데이터에 주로 사용되기에 정렬 가능하다는 가정이 되어 있다.위치 측도 자체로는 많은 것을 알아내기 어렵지만, 위치 측도를 활용하면 데이터의 분포, 개형 등을 확인할 수 있다. $ Q_i $ | 사분위수 (Quartiles)자료를 네 개의 같은 갯수를 가진 그룹으로 나누고, 각 기준값을 위치 측도로 삼는다. 오름차순으로 정렬된 데이터의 인덱스를 $ i $, 자료의 크기를 $ n $ 이라 할 때, $ f_i = \dfrac{i-1}{n-1} $ 의 값이 0.25, 0.5, 0.75 가 되는 값이 각 사분위수가 되고, 차례대로 $ Q_1, Q_2, Q_3, $ 라 부른다. 특성상 $ Q_2 $ 는 중앙값과..