건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다. Randomized Algorithm Las Vegas Monte Carlo 랜더마이즈 알고리즘 알고리즘을 수행하는 과정에서 난수를 활용하는 알고리즘이다. 예를 들어 퀵 소트의 피벗을 랜덤하게 선택하도록 하면, 특정 상황에 최악의 경우를 내던 알고리즘이 평균적...

건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다. Backtracking 모든 케이스를 다 따져보다가, 이건 굳이 안따져도 되는 케이스다 싶은 것을 굳이 체크하지 않고 걸러내면 Backtracking이라고 한다. 어떤 조건을 달았을 때 시간복잡도가 어떻게 달라지는지 계산하기는 매우 어렵다. [!example]- 최대 가치 막대 ...

건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다. Graph 문제 상황을 노드와 간선 관계로 표현할 수 있다면, 문제 상황을 그래프로 옮겨서 풀 수 있다. 예를들어 컴퓨터 네트워크를 컴퓨터를 노드, 연결 상태를 간선으로 생각할 수 있다. 또는 미로의 각 칸을 노드, 갈 수 있는 길을 간선으로 표현할 수 있다. 그래프에서 사용 가능한 ...

건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다. Dynamic Programing Dynamic Programing의 본질은 ‘기록하며 풀기’와 같다. 알고리즘이란 문제의 모든 경우를 일반적으로 해결하는 방법이다. 따라서 문제를 해결하기 위해 모든 경우를 다 따져봐야 하는데, 그 과정에서 중복되는 계산이 많이 생기면 배열과 같은 곳에...

건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다. Divide and Conquer 입력값을 절반으로 나눠서 재귀적으로 답을 구했다고 치자. 두 답을 합쳐서 반환할 답을 만들 수 있다면 Divide and Conquer로 문제를 해결한 것과 같다. 정리하면 다음과 같다. 입력 값을 나눈다. (보통 절반) 각각 재귀적으로 답이...

건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다. Greedy 모든 경우를 다 따져보지 않아도 현재 상태에서 최선이라고 생각되는 경우만 선택했을 때 답이 구해지는 알고리즘이다. 최선의 기준은 여러가지가 있을 수 있고, 기준에 따라 그리디 알고리즘이 해를 찾을 수도, 못찾을 수도 있다. 따라서 최선을 선택하는 방법을 잘 선택하는 것이 핵...

건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다. Sorting 정렬 알고리즘의 경우 일반적으로 비교 정렬을 사용하고, 특정 조건이 만족되는 경우 Counting Sort, Radix sort같은 알고리즘을 사용할 수 있다. 비교 정렬 알고리즘의 경우 (O(n\log n))보다 빠를 수 없다. 그 이유는, 비교하는 선택지를 결정 ...

건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다. 결정, 비결정 문제 결정 문제란 예, 아니요로 답할 수 있는 문제다. 예를 들어 ‘주어진 숫자 n이 소수인가?’, ‘그래프가 모든 정점을 연결하고 있는가?’는 결정문제다. 닫힌 질문과 같다. 비결정 문제란, 예, 아니요로만 답할 수 없는 문제다. 예를들어 ‘그래프의 두 노드 사이의 최...

Analytical mechanics/Fowles, Grant R. (7판)의 내용입니다. 가속계 관성계에 대해 병진 가속하는 좌표계를 가속계라고 한다. 기준계의 가속도와 크기는 같고 방향은 반대인 관성력을 물체가 받는 힘에 추가한다. 관성력은 (F_{i}=-m A_{0})와 같다. [!tip] 사실 중력 = 관성력이다.{title} 아인슈...

Analytical mechanics/Fowles, Grant R. (7판)의 내용입니다. Projectile motion 공기 저항을 받지 않는 포사체 운동을 예측하는 방법에 대해서 알아보자. 초기 속도가 (\mathbf{v_{0}})으로 주어지고, (t=0)일 때 ((0, 0, 0))에서 포사체 운동을 시작한다. 이 입자가 받는 힘은 중력밖에 ...