본문 바로가기
반응형

프로그래밍 ( Programming )86

Markov Process (마코프 체인, 마코프 프로세스) Markov Property 마코프 특성이란 과거 상태들과 현재 상태가 주어졌을 때 미래 상태는 과거와는 독립적이며 현재 상태에 의해 결정되는 개념입니다. 즉, 현재 상태에서 다음 상태로 전이될 확률은 오직 현재 상태에서만 의존하며 이전 상태나 이전 이벤트의 영향을 전혀 받지 않는 특성입니다. 이처럼 마코프 프로세스는 과거 상태를 반영 또는 기억하지 않기 때문에 Memoryless 프로세스입니다. t-k 시점부터 t까지 여러 state를 거쳐오면서 다음 시점인 t+1에 가기 위한 확률은 바로 직전 state인 t시간의 state 확률과 같다는 것을 의미합니다. Markov Process 마코프 과정은 이러한 마코프 특성 (Markov Property)를 지니는 이산 시간 확률 과정을 의미합니다. 이산 시.. 2023. 4. 23.
Acceptance-Rejection Sampling (허용-기각 샘플링) Acceptance-Rejection Sampling Inverse Transform Method와 마찬가지로 확률분포에서 샘플링을 하기 위한 기법 중 하나이며 제안 분포 (Proposal Distribution)를 이용하여 생성된 샘플들의 분포가 목표 분포 (Target Distribution)를 따르도록 수정하는 과정을 포함한 샘플링입니다. 목표 분포의 특징은 직접 샘플을 생성하는 게 어렵거나 불가능하다는 특징이 있습니다. Acceptance-Rejection Sampling을 적용하여 목표 분포에 대해서 샘플링을 하기 위해서는 우선 확률 밀도 함수 (PDF)를 알고 있어야 합니다. Motivation Inverse Transform Method와 같이 CDF가 역함수가 가능한 상황에서 적용할 수 있.. 2023. 4. 22.
Inverse Transform Sampling (역 변환 샘플링) Inverse Transform Sampling Uniform distribution에서 내가 알고 싶은 분포를 무작위 추출 (Random Sampling)이 가능하도록 바꿔주는 방법입니다. 우선 샘플링의 의미는 어떤 특정 분포를 따르는 무작위 샘플을 생성하는 것을 의미하며, 모집단에서 표본을 추출하는 일입니다. 우리에게 익숙한 개념들이 있습니다. PDF (확률밀도함수)는 각 입력값 x에 따른 확률 밀도를 알려주는 함수입니다. CDF (누적밀도함수)의 단점은 어떤 값이 더 자주 나오는지 모르지만 PDF는 CDF를 미분하여서 각 구간 변화의 정도를 얻을 수 있으며 해당 값들의 연속이 결국 어떤 값의 정도를 확인할 수 있습니다. 그러나 PDF 또는 CDF를 통해서는 샘플링이 불가능합니다. 두 함수가 확률 분.. 2023. 4. 21.
Random Number Generator (난수 발생기) 난수 발생기 (Random Number Generator, RNG) 랜덤으로 보이는 일련의 sequence를 만드는 과정을 의미합니다. 우리가 컴퓨터 상에서 사용하는 랜덤이라는 수는 사실 컴퓨터가 랜덤 하게 생성한 게 아닌 어떤 일련의 규칙을 통해서 우리가 인식하기에 랜덤이라고 보일 뿐입니다. TRNG (True Random Number) vs PRNG (Pseudo Random Number) TRNG는 물리적인 요소를 통해서 랜덤 수를 생성합니다. 예를 들어서 방사성 붕괴 (Radioactive decay), 열적 노이즈 (Thermal Noise), 그리고 대기 노이즈와 같이 이러한 요소들은 상당히 불확실성 한 특징을 지니고 있기에 이러한 특징을 이용하여 난수를 생성합니다. PRNG는 determin.. 2023. 4. 21.
Frequentist vs Bayesian (빈도주의자 vs 베이지안) 두 개의 개념은 확률을 해석하는 관점의 차이에 있습니다. Frequentist 확률은 장기적으로 일어나는 사건의 빈도로 주장합니다. 그리고 모수는 고정된 상수라고 가정하고 해석합니다. 장점 Objective Probability Statements: 빈도주의에서의 통계 접근은 긴 시간 동안의 event관찰을 통해서 객관적인 확률 statements를 제공할 수 있습니다. 즉, 결과 해석에 대해서 좀 더 빠르고 비 주관적으로 해석할 수 있습니다. 이는 곧 Robustness와 직결됩니다. Widely used: 베이지안 접근 보다 훨씬 다양한 상황에서 사용이 되며 대부분의 경우 샘플 수가 많기 때문에 더 많은 상황에서 사용이 가능하며 충분히 납득할만한 결과를 기대할 수 있습니다. 단점 Limited fle.. 2023. 4. 21.
몬테 카를로 (Monte Carlo) 몬테카를로 메서드 또는 다중 확률 시뮬레이션이라고도 하는 몬테카를로 시뮬레이션은 불확실한 사건의 가능한 결과를 추정하는 데 사용되는 수학적 기법입니다. 예를 들어서 집에서 회사를 갈 때 단순하게 고려하면 거리에 따라서 얼마나 시간이 걸릴지를 고려하여서 상당히 결정적입니다. 그러나 실제 상황에서는 교통 혼잡, 악천후 및 차량 고장등 확률적으로 낮은 상황들이 발생할 수 있기에 불확실성을 고려한 이동시간을 예측할 수 있습니다. 핵심은 반복적인 무작위적 샘플링입니다 (이러한 특징때문에 카지노와 도박장이 유명한 몬테카를로 지역이름을 채택하기도 하였습니다) 문제를 해결하기 위해서 반복적인 랜덤 샘플링을 통해서 문제를 풀게 되며, 기존에 우리가 생각하던 문제 해결 방식인 절차에 따라서 기계적으로 해결하는 방식과는 다.. 2023. 4. 20.
BFS & DFS 알고리즘 도입 브루트 포스 (Brute Force): 완전 탐색 알고리즘이며 가능한 모든 경우의 수에 대해서 탐색을 수행하여 조건이 만족되는 경우를 찾는 방법입니다. (Brute - 무식한 + Force - 힘) 모든 경우를 탐색하기 때문에 100%의 정답률을 보장할 수 있습니다. 그러나 모든 경우를 탐색하기 때문에 실행시간이 매우 오래 걸릴 수 있다는 단점이 존재합니다. 구조에 따라서 브루트 포스는 2가지로 나뉘게 됩니다. - 선형 구조 (순차 탐색) - 비선형 구조 (넓이 우선 탐색 - BFS, 깊이 우선 탐색 - DFS) 순차 탐색은 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘이며, 탐색 배열이 단방향이기에 선형 탐색 (Linear Search)라고 부르기도 합니다. 하지만 모.. 2023. 3. 3.
1057번 - 토너먼트 문제 링크: https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 알고리즘 분류 - 수학 - 브루트 포스 알고리즘 나름의 풀이 과정에 대한 사고 1, 2, 3, 4, 5, 6, 7, 8 -> 1, 2, 3, 4 -> 1, 2 -> 1 와 같이 진행이 될 때 1, 2를 그룹으로 묶을 수 있는 방법이 중요함. 즉, 3, 4 또한 한 그룹으로 묶을 수 있어야 함 리스트를 사용할수도 있지만 나눗셈과 뺄셈을 이용하여 접근하는 게 더 효율적이다. value = val.. 2023. 3. 1.
[CMake] CMake란 CMake는 빌드 파일을 생성 및 배포를 위한 패키지 생성에 이르는 과정을 모두 해주는 프로그램을 의미합니다. 즉, CMake를 통해서 프로젝트를 빌드하는 것이 아닌, CMake를 통해서 빌드 파일을 생성하는 단계까지 해주는 프로그램을 의미합니다. 빌드 파일을 만든다면 그 후 빌드 프로그램을 이용하여 프로젝트를 빌드하게 됩니다. 좀 더 히스토리를 보겠습니다. Compile & Linking (컴파일과 링킹) 컴파일은 소스코드를 어셈블리어로 바꿔주는 과정이며 소스파일 (.c)에서 목적파일 (.o)를 생성하는 과정을 의미합니다. 그리고 링킹은 서로 다른 파일에 있는 목적파일들을 한 군데 묶어서 하나의 실행파일로 만드는 과정을 의미합니다. 하지만 프로젝트가 커져서 만약 컴파일을 수행해야 할 파일들이 많아지게 .. 2023. 1. 14.
반응형