해나의 컴공생존기

1. Traversal Traversal : 그래프의 노드를 방문하는 방법 어디서 시작하는지 정하지 않는다. 어디에서 시작하느냐에 따라서 다른 알고리즘이 된다. 같은 노드를 여러번 지나갈 수 있다. 어떤 문제를 푸느냐에 따라서 계산할 것들이 달라진다. Traversal을 통해 그래프 안에 뭔가 구조가 만들어질 것이다. => 보통 Tree가 만들어 진다. 2. Any-Order Traversal 어떤 노드 s에서 시작하고 s를 BOX에 넣는다. BOX가 비어있지 않으면 아래의 과정을 반복한다. 하나의 노드를 꺼내고 방문하지 않은 노드라면 방문한 뒤 어떤 계산을 수행한다. 그리고 노드와 인접한 모든 엣지들을 BOX에 넣는다. 이후 이 과정을 계속 반복한다. 박스에 여러개 들어있다면 어느 것을 꺼내겠는가? 어..

1. Merge Algorithm sorting된 두개의 배열을 앞에서부터 각각 하나씩 비교하며 한 배열에 순서대로 합치는 알고리즘. 이 알고리즘의 단점은 하나의 배열을 새로 만들어야한다는 것이다 2. Recursive Merge Sort 위 코드를 간단히 설명해보자면 먼저 a[]와 똑같은 b[]를 만든다. h는 배열 전체 길이의 절반이다. b[0]부터 b[h-1] 까지 sort하는 함수를 한번 호출하고 b[h]부터 b[n-h-1]까지 sort하는 함수 하나를 호출한다. 끝까지 한 다음에는 마지막에 a로 sorting되며 합쳐진다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야..

1. sorting의 조건 정확하게 sorting이 되기 위해서는 아래의 두가지 조건이 성립되어야한다. 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]n−1 일 때 sort 함수가 성공한다고 가정하자. 항상 재귀 실행 전에 a[0]에 최소값이 들어간 후 실행된다. 따라서 재귀로 들어가기 전부터 ∀x((x>0)→(a[0]a[0]