728x90 Quality control (Univ. Study)196 Lecture 4 - One Random Variable Cumulative Distribution Function (CDF) CDF의 정의는 다음과 같다. X 2023. 5. 13. Lecture 18 - Graph(2) 위상 정렬 (Topological Sorting) 우선 싸이클이 없는 유향 그래프에서 정의되는 문제이다. 간단하게 살펴보면 모든 정점을 정렬하되 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치해야 하는 정렬이다. 이때 복수의 위상 순서가 존재할 수 있다. 라면 끓이기에서 위상순서를 나타낸 그래프를 보면 위와 같다. Kahn 기반 알고리즘 다음은 Kahn 알고리즘 기반 위상 정렬의 psuedo code이다. topologicalSort1(G, v) { for ← 1 to n { 진입간선이 없는 정점 u를 선택한다; A[i] ← u; 정점 u와, u의 진출간선을 모두 제거한다; } ▷ 이 시점에 배열 A[1…n]에는 정점들이 위상정렬되어 있다 } 수행 시간은 Θ(|V|+|E|)이고.. 2023. 5. 8. Lecture9, 10 - Gauss's Law, Divergence Gauss's Law 가우스 법칙은 특정 폐곡면을 잡았을때 해당 폐곡면을 통과하는 electric flux density의 총합이 해당 폐곡면의 내부에 존재하는 모든 전하량의 합이 같다는 법칙이다. Point charge field 점전하에 의해서 발생된 charge field를 살펴보자. 위의 상황에 대해 가우스 법칙을 적용해보면 다음과 같다. Line charge field 선전하에 의해서 발생된 charge field에 대해서 알아보자. 위의 상황에 대해서 가우스 법칙을 적용해보자. Divergence 전자기학에서의 Divergence는 벡터장의 확산 정도를 나타내는 개념이다. 특정 미소 지점에서 벡터장의 상태를 표현하는 스칼라 값이다. 위와 같이 divergence를 이용하여 전하밀도를 구할 수 .. 2023. 5. 4. Lecture8 - Electric Flux Density Faraday Experiment 패러데이의 실험에서는 전하량 +Q로 대전된 내부의 금속구를 폐곡면 금속구로 감싸서 아래와 같이 Flux와 Q가 완전히 일치하는 상태를 만들었다. 그리고 그에 따라 전기 플럭스 밀도에 대한 식을 다음과 같이 쓸 수 있게 되었다. 외부원과 내부원을 따로 보면 다음과 같다. 이를 일반화하면 다음과 같이 D벡터로 표현할 수 있다. 이때 이를 electric field intensity와 비교하면 아래와 같은 관계식을 구할 수 있다. 따라서 electric flux density와 electric field intensity를 비교해보면 다음과 같다. 2023. 5. 4. Lecture 17 - Graph(1/4) 그래프 정점(vertex) 및 간선(edge)로 이루어진 자료구조이다. G = (V, E) 형태로 나타냄 (V: 정점 집합, E: 간선 집합) 두 정점이 간선으로 연결되어 있을 경우 인접하다고 한다. 종류 그래프의 종류를 나누는 기준은 다음과 같다. - 두 vertex 간 가능한 edge의 개수 - Edge의 방향 유무 - Loop의 유무 - 추가적으로 edge의 weight 유무에 따라 weighted, unweighted로 나눌 수 있음 인접 행렬을 이용한 그래프의 표현은 이해하기 쉽고 간선의 존재 여부를 Θ(1)만에 파악 가능하다. 그러나 그래프 정보를 저장하기 위해서만 Θ(𝑛^2) 시간이 소요되고 메모리 사용량도 크다는 점은 단점으로 작용한다. 간선의 밀도가 높은 그래프에서는 인접 행렬을 사용한 .. 2023. 5. 1. Lecture 14 - Dynamic Programming 동적 프로그래밍(Dynamic Programming) 동적 프로그래밍이란 큰 문제의 해답에 더 작은 문제의 해답이 포함되어 있으며, 이를 재귀호출로 구현할 때 같은 해답을 구하기 위한 중복 호출이 다수 발생하는 경우에 활용하는 문제해결 기법이다. 큰 문제의 해답에 더 작은 문제의 해답이 포함된 경우를 최적 부분 구조(Optimal Substructure)를 가진다고 한다. 동적 프로그래밍을 적용하는 문제는 아래와 같은 두 성질이 있다. ① 최적 부분구조(optimal substructure) - 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함된다. (점화식 형태로 표현) ② 재귀호출시 중복(overlapping recursive calls) - 재귀적 해법으로 풀면 같은 문제에 대한 재귀호출이 .. 2023. 4. 24. Lecture3 - Discrete Random Variable Random Variable Sample Space의 event를 수직선 상의 하나의 점으로 mapping하는 것이다. 이를 함수에 올리면 다음과 같이된다. Coin Tosses Head와 Tail의 확률이 1/2로 같다고 했을때 동전을 세번던지는 경우에 대해 알아보자. 우선 Sample Space는 다음과 같다. X를 Head가 나오는 수로 두면 PDF가 다음과 같이된다. 이때 PDF는 Probability Density Function으로 확률 밀도 함수이다. 물론 엄밀히 따지면 discrete RV는 PMF 즉 Probability Mass Function 확률 질량 함수라고 불러야 하지만 수업 시간에는 편의를 위해 혼용하는 것으로 보였다. Expected value of discrete rando.. 2023. 4. 14. Lecture 13 - 집합의 처리 상호 배타적 집합 상호 배타적 집합은 서로 공유하는 원소가 없는 여러 집합들의 모임 (disjoint sets)으로 각 집합은 대표 원소로써 해당 집합을 나타낸다. 관련 연산을 보면 다음과 같다. ▪ Make-Set(𝑥) : 원소 𝑥로만 이루어진 집합을 생성 ▪ Find-Set(𝑥) : 원소 𝑥가 포함된 집합을 찾은 후 대표 원소에 대한 포인터를 반환 ▪ Union(𝑥, 𝑦) : 원소 𝑥가 포함된 집합과 원소 𝑦가 포함된 집합을 합쳐서 합집합 생성 시간 복잡도 분석 관련하여 총 𝑚회의 Make-Set, Find-Set, Union 연산이 있을 때 𝑛번의 MakeSet 연산이 포함된 상황을 가정한다. 대표적으로 그래프 구조에서의 connected component 관련 처리에 활용된다. 연결 리스트를 이용.. 2023. 4. 10. Lecture7 - Electric Field(2) Line charge electric field z축을 따라 선전하가 배치되었을때 P점에 전기장이 주는 전기력을 계산해보자. 선전하로부터의 거리의 1승에 반비례함을 알 수 있다. 이러한 기본 식을 활용하여 선전하가 z축에 존재하지 않는 경우를 보면 다음과 같다. 선전하가 (6,8,z)로 표현될 때의 경우이다. Sheet charge field 이번에는 면전하에 대해서 알아보았다. 거리와 관계없이 전기장은 일정함을 알 수 있다. 2023. 4. 8. 이전 1 ··· 15 16 17 18 19 20 21 22 다음 728x90
