목록zerebase (46)
Hyunebee
매 순간 현재 기준으로 최선의 답을 선택해 나가는 방법 - 빠르게 근사치를 계산할 수 있다. - 결과적으로는 최적해가 아닐 수 있다. 그리디 알고리즘 예시 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. 사이클 : 단..
레드블랙 트리의 조건 1. root 노드와 leaf노드의 색은 black 2. red 색 노드의 자식은 black 3. 모든 leaf노드에서 root노드까지 가는 경로의 black 노드 수는 같음 조건을 만족하지 못할시 재배치해야함 여기서 NIL은 null Node라 생각하면됨 삽입 double red 발생 - (1) -부모 노드의 형제 노드가 red일때 이때는 색을 바꿔줌 -삽입한 노드의 부모와 부모의 형제 노드를 black으로 변경 -부모의 부모노드를 red로 변경 -부모의 부모노드가 root인지 double red인지에 따라 조정 double red 발생 - (2) -부모 노드의 형제 노드가 black이거나 없을때 이때는 위치를 바꿔줌 대상: 삽입한 노드, 부모 노드, 부모의 부모노드 -조정 노드들..