Sum Rule : when the events cannot happen at the same timeProduct Rule : when the events happen in conjunction AND the number of leaves for each branch of the problem space tree is the sameHow to classify the problem space into events/sets : Ru..
1 ~ n : n itemsThis is easy. You only need to read the last item's number to get the number of items.8 ~ 11 : 4 numbers11 - 8 = 3 numbers? WRONG!!! Why? Subtraction = the number of spans between numbers, NOT a count of how m..
출처 : https://www.acmicpc.net/problem/2003Two Pointer Algorithm의 전형적 케이스 중 하나.사실 그렇게 어려운 것은 아니지만 이게 왜 되는지 100% 이해가 가지 않는 상황에서 증명을 안하고 넘어갈 수는 없었다.How do we know this algorithm takes care of all possible subsequences when it terminates?Again, I used J..
귀납법으로 그래프 문제를 증명할 때 항상 노드를 하나 지우는 방식으로 접근하라고 배웠는데사실 왜 그렇게 해야 맞는지는 확실히 배우지 않았다.물론 그냥 딱 듣고 왜 그런지 알아채는 친구들도 있겠지만.. 내 경우에는 ㄴㄴWith the help of Professor John F. Hughes, Brown University Department of Computer Science, here is a proof showing why you should a..
An Euler trail is a walk that uses every edge of a graph exactly once.An Euler circuit is a circuit that uses every edge of a graph exactly once.A Euler trail with same endpoints is a Euler circuit.Here are some examples:Letbe a finite co..
Prove that for , .Intuition: Suppose n people shake hands with other people in the group. They don't shake hands twice with the same person.How many handshakes take place?각 사람을 노드로 본다면 두 사람이 악수를 하면 그 두 노드 사이에 Edge 가 생긴다.전체 악수의 수 = N..
When designing an algorithm, ask yourself : For which cases does the obvious method work?Then find a new way to tackle the remaining cases!예제)Find a hamiltonian path through a tournament graph.Using a more-of-input approach, we claim to have a solu..
How to Think about Algorithms by Edmonds has good in-depth explanation of how to actually go about thinking about designing algorithms and approaching algorithmic problems. I applied the process to understanding Merge() routine of the MergeSort algori..
- Proof of Correctness
- Two Pointer