Algorithm

1.인접 행렬(adjacent matrix):메모리 소모가 큰 대신 탐색 속도가 빠르다2.인접 리스트(adjacent list):메모리 소모가 작은 대신 탐색 속도가 느리다1의 경우 그래프의 모든 노드에 맞는 (예 v개의 노드 이면 v\*\*2) 행렬을 모두 구현해야

dfs ,bfs 둘다 구현완탐으로 그래프 순회하며 boolean리턴 하는 함수로 작성하여 효율성 높임

시간 복잡도

이분 탐색은 정렬되어있는 데이터에 대하여 진행한다시간 복잡도: N개의 데이터가 있을때 O(logN)아래 구현코드는 타깃을 찾거나 타깃이 삽입되어야 할 인덱스를 리턴한다.\*\*mid를구할때 비트 연산자로 구현하여 효율성을 높인다.

일반적 이분탐색(답이 없으면 상한 또는 하한을 만족 하는 인덱스 혹은 값 반환하도록)Main.bSearch의 while(left+1<right) 조건으로 인해L X R의 구조를 지키도록 하여 항상 사이값이 해가 되도록한다.

중복되는 연산을 줄이기 (top down방식의 memoization)작은 문제가 큰 문제의 부분이 되며 서로 영향을 미칠때( 분할 정복과 다른 점)대체적으로 점화식으로 나타낼수 있다.fn = fn-1 + fn-2의 점화식을 갖는다top down방식으로 구현시 n==10

다익스트라는 양의 가중치를 가진 그래프들의 노드간 연결이 주어질때시작점으로 부터 다른 모든 노드까지의 최소비용의 경로를 구한다.그리디(방문 하지 않은 노드중 최소 비용을 가지는 노드를 우선적으로 처리)DP(이미 계산한 최소 비용을 이용하여 그 노드를 경유하는 다른 노드

다익스트라는 그래프 내의 한 시작점 으로 부터 다른 노드까지의 최단거리를 구한다면플로이드 워셜은 모든 노드간의 최단 거리를 구한다.다익스트라 거리 리스트는 1차원(노드가 N일때 사이즈는 N)플로이드 워셜의 경우 거리 리스트는 2차원(N\*N)이다.하나의 노드(현재 갱신

입력:3 2 11 2 41 3 2출력:2 4

union, find연산을 가지는 자료구조로 최상단의 부모노드가 서로 다르면 다른 집합으로 보는 트리형 자료구조로 생각할 수있다.구현은 트리형으로 하지 않고 노드갯수와 같은 크기의 parent배열을 이용하여일종의 linked list 처럼 각 노드의 부모를 재귀적으로