기억보단 기록을

삽입정렬은 배열인덱스를 하나씩 증가시키며 앞선 정렬된배열에 하나씩 삽입하는 원리이다.

a[0] = e, 즉 배열은 1번째 인덱스부터 시작하는데 0번쨰인덱스에는 자기자신이 들어간다. 

왜냐하면 삽입정렬은 앞선 배열의 원소하나씩 비교해가며 자신보다 작은원소의 다음배열칸에 삽입하게 되어 있는데, 결국 끝까지간다면(현재 원소가 앞선배열중 가장 작은 값이라면) 첫번째인덱스에 집어넣기위해 0번째 인덱스에 자신을 넣는다.

1.깊이우선탐색(DFS)

시스템 스택을 이용한 DFS 이다.

2.너비우선탐색(BFS)

'리스트로 구현한 queue'의 기능을 사용한 BFS이다.

그래프의 표현

1.Adjacency matrix

2.Adjacency list

2.Adjacency Multilist

위의 리스트 방식은 결국 무방향그래프의 경우 가령 1과 3 vertex가 연결되어있으면 두번표시를 해야하니 비효율적이라는 것이다. 따라서 multilist를 사용해 노드간의 연결정보를 한번씩만 표현해줄 수 있다. 다소 이해하기 어렵고 프로그램 작성하는데 매우 헷갈렸다.

쉽게말해 달리기 대진표다.

8번레인까지 조별예선 한다고 치고, 1등끼리만 토너먼트트리를 결성해 우승자는 걸러낸다.

sortedIdx는 각 조별예선의 몇번째 사람이 토너먼트트리에 진출할껀지를 가리키는 인덱스이다.

이진탐색트리는 말그대로 이진탐색을 위한  트리이다.

노드기준 오른쪽은 자신보다 큰노드, 왼쪽은 작은노드가 들어가기때문에 이진탐색트리의 서브트리또한 이진탐색트리이다.  균형잡인 complete binarytree의경우  탐색 시간복잡도가 높이 h에대해 n개의 자료가 있다고 가정한다면O(h) = O(log2n)이 된다. 하지만 아래와 같이 균형잡힌 트리가 아니라면, 최악의 경우 시간복잡도 n이 나올수도 있으므로 항상

이진탐색트리의 균형을 맞추어주는 알고리즘또한 중요하다.

Maxheap이란 트리구성에서 데이터값이 가장 큰 노드가 가장 root노드에 배치된다.

간단히 배열로써 구현하였다.

배열인덱스 1은 루트노드를 의미한다.

Maxheap tree에 push 하는법 : i가 트리의 크기(즉, 맨 마지막 노드) 로 부터 시작해 부모노드와 크기비교

만약 부모 노드가 더 크다면 maxheap이 유지되는것이니 그냥 마지막에 넣으면 되는데 부모노드가 더 작다면 부모노드를 내려야한다. 계속해서 최상단 root까지 비교해 거슬러 올라가는 식이다.

Maxheap tree에 pop 하는법 : pop이 어려운데, 이는 상단 부모노드를 한개 뺄시 아래의 균형이 깨진다.

따라서 자식들중 더 큰 노드를 다시 부모자리에 채우는 식이다.