Algorithm

완전 이진 트리 (인덱스 트리) index/2하면 부모index\*2하면 왼쪽 자식, +1하면 오른쪽 자식 배열로 표현 사용할 데이터는 트리의 가장 아래에 위치2^0, 2^1 순으로 크기가 증가함사용할 데이터수가 5인 경우 2^2 < 5 < 2^3이므로 배

Class에 compareTo를 정의하여 정렬하기 Comparator를 이용하여 정렬하기

오름차순 정렬 후mid = (low + high) / 2target값과 mid값을 비교 후 low, high 값을 이동 후 반복O(logn)

완전 이진트리 형태시간복잡도: O(logN)최소값(Min Heap), 최대값(Max Heap)을 찾을 때 사용삽입 연산 시 조건 만족 확인 후 만족하지 않는 경우 부모-자식 위치 변경삭제 연산 시 항상 루트 노드를 삭제 후 가장 마지막 노드를 루트로 이동, 조건 확인

구간합 구하기Array를 활용한 Binary Tree실제 데이터는 리프노드에 저장내부 부모 노드에 하위 노드들의 구간합을 저장Update: 리프 -> 부모 -> 루트까지 모두 업데이트해줌Query: 시작~마지막 구간의 합 가져오기. 시작, 마지막 노드의 부모를 각각 계

최대공약수를 구하는 알고리즘 gcd(a,b) = gcd(b,a%b) 반복하다가 마지막에 나눠서 0으로 떨어지면 나눈 값이 최대공약수이다.최소공배수: (a \* b)/gcd(a,b)N이하의 모든 수로 나누어 보는 것은 비효율적이므로 2~sqrt(N) 까지 나누어본다.소수

nCk = (n-1)C(k-1) + (n-1)Ck= n! / k!(n-k)!

차수(Degree): 간선의 수in-degree: 들어오는 간선의 수out-degree: 나가는 간선의 수Cycle : 시작 정점과 끝 정점이 같은 경로N이 작은 경우플로이드 워셜다익스트라, 벨만포드, DFS, BFS

그룹을 만들고 같은 그룹인지 확인하는 알고리즘가장 상단에 있는 부모를 찾기찾아가면서 현재 부모도 업데이트부모를 업데이트할 때는 부모가 둘중 작은/큰 값으로 업데이트아래 예시에서는 작은 값이 부모가 되게 업데이트하였음그룹을 확인하는 알고리즘은 Union Find도 있지만

N개의 노드N-1개의 간선모든 노드는 연결되어 있다.두 노드에 대해 경로가 하나만 존재한다.순환이 없다.방향성이 없다.모든 노드가 연결되어있는 트리모든 노드가 연결되어 있고, 간선의 가중치의 합이 최소인 트리Union Find를 활용1\. 간선을 기준으로 오름차순으로

순환(사이클)을 가지지 않는 방향그래프DAG에서 방향성을 거스르지 않고 정점들을 나열하는 것각 정점을 우선순위에 따라 배치한 것결과는 유일하지 않다.노드 방문 후 나가는 간선을 지움 (outdegree를 0으로 만듦)indegree가 0인 노드부터 다시 반복indegr

트리에서 노드 A, B가 가장 처음으로 만나게 되는 노드자기자신도 포함!두 노드의 Depth를 맞춘 후1\. 같다면 그 노드가 LCA2\. 다르다면 Depth-1높이가 H인 경우 O(H)높이가 N이라면? O(N)하나씩 체크하면 속도가 너무 느리므로2^n만큼 높이를 거슬

무향 연결 그래프에서 한 노드를 삭제했을 때 두 개의 그래프로 나누어 진다면 해당 노드는 단절점DFS를 돌 때 첫 루프에서 방문한 점은 다 연결되어 있다.시작 노드인 경우자식 수가 2보다 큰 경우 단절점시작 노드가 아닌 경우이 노드의 방문 순서(order)가 연결된 정

출발점이 있다.다른 모든 도시로의 최소 시간을 구할 수 있다.3개 중 가장 빠름O(ElogV)Priority Queue를 이용모든 정점까지의 거리를 무한대로 초기화출발점에서 방문할 수 있는 정점과 거리를 Queue에 넣기Queue에서 꺼낸다.꺼낸 정점까지의 거리값과 기

모든 정점간의 최단 거리 찾기한 정점(k)에 대해 i에서 j까지 이 정점을 거쳐가는 모든 경로를 탐색이 정점을 거쳐가는 경우가 기존 경로보다 짧은 경우 업데이트O(N^3)

음수 비용인 경우도 가능음의 사이클 존재 여부 확인정점의 개수가 V이면 간선을 V-1개만 사용하면 최단 거리를 만들 수 있다.O(EV) = O((V-1)V) 시작점에서 다른 정점까지 거리를 무한대로 초기화모든 간선에 대해간선의 시작점이 아직 무한대인 경우 패스간선의 시

수열의 순서는 유지하되 일부 항을 선택하여 만들 수 있는 수열(부분 수열) 중 각 항이 이전 항에 비해 증가하는 부분 수열1번 항 부터DP배열의 가장 큰 수보다 큰 값이 들어오면 DP 배열에 저장Lower Bound : 자신보다 크거나 같으면서 그 중 가장 작은 숫자D

두 문자열(수열)이 주어졌을 때, 부분공통수열 중 가장 긴 수열 찾기연속적이지 않아도 됨두 문자열을 배열로 표현한다.DPi에 A문자열의 i번째 문자까지, B문자열의 j번째 문자까지 같은 문자의 총 개수를 저장한다.Ai = Bj인 경우 A0~Ai와 B0~Bj가 모두 업데