우주수첩의 우주먼지

이전 포스팅 https://dusty-wznt.tistory.com/85 에서 Prime에 대해 다뤘고 그와 동시에 에라토스 테네스의 채의 원리를 너무나도 완 벽 하 게 이해를 해버렸.땨. # 에라토스 테네스의 체 주어진 integer x가 prime인지에 대한 여부를 쉽게 판별할 수 있도록 processing 해주는 알고리즘. prime 여부는 크기가 n인 array에 저장되며 (이해를 돕기 위해 sieve라고 하겠다. sieve == 체) i>2에 대하여 sieve[i] ==0이면 i는 prime이고 sieve[i]==1이면 i는 !prime이다. 이처럼 배열은 해당 index가 prime인지에 대한 여부를 저장한다. 여기서 에라토스 테네스의 채를 구현할 때 key idea가 될 조건은 앞서 포스팅 ..

거 참 제목 하나 영어로 썼다고 간지나는 거 보소. 이전에 에라토스 테네스의 체를 포스팅 한 적이 있다. https://dusty-wznt.tistory.com/19?category=1061713 이때는 그냥 코드 구현만 하고 자세한 설명이 없었는데 수업을 듣다가 원리를 깨달아 버렸다. 만약 N이 prime이 아니라면 두 positive integer a,b >1에 대하여 n=a*b로 나타낼 수 있다. 이 경우 a or b는 반드시 √n 을 넘지 않는다. bool prime(int n){ if(n

앞서 포스팅 했던 두 numpy 라이브러리를 활용하여 Median Filtering을 진행하고자 한다. median : https://dusty-wznt.tistory.com/82 clip : https://dusty-wznt.tistory.com/83 Median filtering은 이미지가 가지고 있는 noise를 제거하기 위한 필터링의 방법 중 하나로 이미지에 Mask를 씌워 해당 마스크의 크기만큼 이미지의 픽셀값을 조회한 뒤 정렬된 픽셀값들 중 중앙 값 저장하여 salt and pepper noise와 같은 튀는값을 제거하고자 하는 목적으로 사용된다. def median_filtering(src, msize): h, w = src.shape dst = np.zeros((h, w)) for row ..

#numpy.clip(array, min, max) array내의 element에 대하여 min보다 작은 값들은 min의 값으로 변경하고 max보다 큰 값들은 max로 변경한다. import numpy as np arr = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) clip_arr = np.clip(arr1, 3, 7) print(clip_arr) 위의 코드를 실행할 경우 결과 값 => 3 3 3 3 4 5 6 7 7 7

# np.median() np.median(array) : 파라미터로 들어온 array 의 정렬된 중간 값을 구해준다. import numpy as np arr = [2, 5, 7, 6, 8, 10, 11] m = np.median(arr) print(m) 위의 코드를 실행했을 경우 2 5 6 7 8 10 11순으로 정렬 된 array의 가운데 값인 7이 반환된다 import numpy as np arr = [2, 5, 7, 8, 10, 11] m = np.median(arr) print(m) 위의 경우처러 짝수일 경우에는 7과 8의 중간값이 7.5가 반환된다.

#include #include using namespace std; #define NUMBER 12 int tree[4 * NUMBER]; // 4를 곱하면 모든 범위를 커버할 수 있다. 개수에대하여 2의 제곱 형태의 길이를 가지기 때문...이라는데 머지? int A[] = { 1,9,3,8,4,5,5,9,10,3,4,5 }; // 구간 합을 구하고자 하는 리스트를 저장한다. void build(int node, int start, int end) { if (start == end) { tree[node] = A[start]; } else { int mid = (start + end) / 2; // 재귀로 두 부분으로 나눈 뒤에 그 합을 자기 자신의 합으로 한다. // 처음 시작은 build(!,0,n..

# Min Cut Problem == vertex patitioning Source s, sink t를 가진 directed graph G =(V,E)에서 s-t cut (s∈S, t∈T)를 만족하는 vertex들의 partition(S,T)으로 정의한다. 한 partition은 무조건 source만, 다른 한 쪽의 partition은 무조건 sink만 포함. 한 partition에 sink 와 source를 모두 포함할 수는 없다. s-t cut의 capacity C(s,t)는 u∈S, v∈T를 만족하는 모든 edge의 capacity의 총 합으로 정의한다. 시작 vertex는 source에서, 종료 vertex는 sink에서 존재해야 한다. # Max-flow & Min cut theorem Dire..

# Ford-Fulkerson Algorithm Max-Flow 문제를 해결할 수 있는 대표적인 알고리즘이다. 주어진 그래프 G와 현재 Flow f로 정의되는 잔여 그래프(residual graph) Gf를 이용해서 해결된다. # Residual graph 초기화 G의 vertex와 edge를 모두 G0로 copy한다. G0의 edge 중 one-way-path edge를 edge(v,u)를 G0에 추가한다. 이때 edge(v,u)의 capacity는 0으로 정의한다. one-way-path : edge(u,v)는 있으나 edge(v,u)는 없는 경우 2번의 작업상태에 있는 그래프를 G'이라고 칭할 예정이다. #Augumenting path : 증가 경로 G'의 source 에서 sink 까지 가는 pa..

# 네트워크 플로우 (Network Flow) - 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는지를 측정하는 알고리즘 # 필요 용어 정리 capacity (용량): edge가 수용할 수 있는 값 flow (유랑) : 실질적으로 보내는 값 source : indegreee가 0인 vertex sink : outdegree가 0일 vertex (수첩의 개입) 이라고 정의하기에는 너무 두루뭉실 뜬구름이 뭉게뭉게여서 다시 설명을 하자면 육상 트랙의 라인 수 == capacity 트랙에서 한 번에 뛰어야 하는 선수의 수 == flow 라고 생각하면 앵간 편하지 않을까 싶기도 한댱 ㅇㅅㅇ... 뭔가 일반화된 그래프의 시각으로 봤을 때 start 점이 source / finish 지점이 sink라고..

# OS의 흐름 Program Binary code Main Memory high level language /command low level language / Instruction, data excutable code Compiler : 하나의 command가 여러개의 instruction으로 저장 Loader : excutable code # OS의 기본 element processor IO module main memory system bus # Processor 컴퓨터의 작동을 관리. 데이터를 처리하는 함수를 실행 CPU라고도 불린다. == core라고도 불린다