Hyunebee

그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 크루스칼, 프림 2가지가 존재 크루스칼 간선 중 최소 값을 가진 간선부터 연결 사이클 발생 시 다른 간선 선택 주로 간선 수가 적으면 사용 O(ElogE) 프림 임의의 노드에서 시작 연결된 노드의 간선 중 낮은 가중치를 갖는 간선을 선택 간선의 개수가 많을 때 크루스칼 보다 유리하다. O(ElogV)

큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식 분할정복 vs DP 분할 정복은 부분 문제가 중복되지 않아서 DP와 다름 DP는 부분문제가 중복되어 재활용한다. 그리디 vs DP 그리디 알고리즘은 순간의 최선을 구하지만 DP는 모든 경우에 수에서 최적해를 구함 DP의 방법 상향식 접근 (타뷸레이션) 작은 하위 문제부터 풀면서 올라감 모두 계산하면서 차례대로 진행 하양식 접근 (메모이제이션) 큰문제에서 하위문제를 확인해가며 진행 계싼이 필요한 순간 계산하며 진행

매 순간 현재 기준으로 최선의 답을 선택해 나가는 방법 - 빠르게 근사치를 계산할 수 있다. - 결과적으로는 최적해가 아닐 수 있다. 그리디 알고리즘 예시 1) Actiity Selection Problem -N 개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때 -한 사람이 최대한 많이 할 수 있는 활동의 수 구하기 -> 이것을 종료 시간 기준으로 정렬 -> 먼저 종료되는 활동순, 겹치지 않는 순으로 선택 -종료 시간이 빠른 순으로 선택 처음은 종료시간이 3인 C가 옴 - A는 5에 종료를 하지만 시작이 1에서 함으로 선택x - B는 조건에 맞음으로 선택 C > B - D는 B와 시작 시간이 같음으로 선택x - E는 조건에 맞음으로 선택 C > B > E 2) 거스름돈(동전의 개수가 가장 적게) 잔돈..

어떤값을 가르키는 2개의 변수 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법 1.같은 방향에서 시작 2.서로 다른 방향에서 시작, 첫 번째 원소와 마지막 원소에 배치 -> 다중 for문의 복잡도를 조금더 선형적으로 해결 가능 단순 for문을 이용할 경우 1번째 for문과 2번째 for문을 돌면서 최악의 경우 n^2만큼 순회 2개의 p1, p2를 이용하여 최악의 경우 p1 = n만큼 p2 = n만큼 2n이다. 하지만 표기법상 n정도의 시간이 걸린다 생각한다.

정렬 알고리즘 특정 값을 기준으로 데이터를 순서대로 배치하는 알고리즘 1. 구현 난이도는 쉽지만, 속도는 느린 알고리즘 - 버블정렬, 삽입정렬, 선택 정렬 1.1 버블 정렬 인접한 데이터를 비교하며 자리를 바꾸는 방식 시간복잡도 : O(N^2) 1.2 삽입 정렬 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식 시간복잡도 : O(N^2) 1.3 선택 정렬 최소 또는 최대값을 찾아서 정렬하는 방식 시간복잡도 : O(N^2) 2. 구현 난이도는 조급 어렵지만, 일반적으로 속도는 빠른 알고리즘 - 합병정렬, 퀵정렬, 트리정렬 2.1 합병 정렬 배열을 계속 분할해서 길이가 1 이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식 시간복잡도 : O(nlogn) 2.2 힙 정렬 기존 배열을 최대 ..

우선 순위 큐 - 우선 순위가 높은 데이터가 먼저 나옴 != FIFO - Dequque시 우선순위가 높은 순으로 나감 - 우선 순위가 같은 경우는 FIFO로 출력 구현 방법 -> 자바의 내부적으로는 힙으로 구현되어 있음 enqueue() dequeue() 정렬된 배열 O(N) O(1) 정렬된 연결 리스트 O(N) O(1) 힙 O(logN) O(logN)

힙 => 완전 이진 트리 형태(마지막 level빼고 모든 노드가 채워져있으면 됨) - 중복 값 허용 - 반 정렬 상태(형제 사이의 크고 작음은 보장하지 않음) - 최소값 또는 최대값을 빠르게 찾아내는 데 유용한 자료구조 최소힙 최대힙 서로반대 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 최소힙 삽입 트리의 가장끝에 삽입 후 부모노드와 비교해 작을경우 부모노드와 교체 최소힙 삭제 최상위 노드 삭제 후 가장 마지막 위치의 노드와 교체 자식 노드중 더 작은 값이 있다면 자리 교체 구현 -> ArrayList활용 class MinHeap{ ArrayList heap; public MinHeap(){ heap = new ArrayList(); heap.add(0);//인덱스 1부터 시작할 수 있게 더미..

트리의 상위 개념 => 그래프 그래프란? 정점과 간선으로 이루어진 자료구조 -> 연결된 정점간의 관계를 표현할 수 있는 자료구조 -But 트리와 다른점은 Cyclic하다. 그래프의 구조 1. 정점 : 각 노드 2. 간선: 노드와 노드를 연결하는 선 3. 인접 정점 : 간선 하나를 두고 바로 연결된 정점 (A의 인접 정점은 B,C) 4. 정점의 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수, 무방향 그래프의 모든 정점 차수의 합=간선 수 * 2 5. 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수 6. 진출 차수 : 방향 그래프에서 외부로 나가는 간선의 수 7. 경로 길이: 경로를 구성하는데 사용되는 간선의 수 8. 단순 경로: 경로 중에서 반복되는 정점이 없는 경우 9. 사이클 : 단..