알고리즘 (44) 썸네일형 리스트형 AVL Tree Goal 자가 균형 트리에 대한 이해 AVL 트리에 대한 이해 AVL 트리를 직접 구현해본다. AVL Tree란? 자가 균형 이진탐색 트리(self-balancing binary search tree) 일종으로, 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다. AVL 트리는, 트리가 비균형 상태가 되면 스스로 노드들을 재배치(self-balancing)하여 균형 상태로 만든다. 따라서, 항상 균형 트리를 보장하기 때문에 O(logn)의 탐색 시간을 보장한다. *이진 탐색 트리에서 균형을 유지하는 것이 중요한 이유 더보기 이진 탐색 트리 연산(삽입, 삭제, 탐색)의 시간 복잡도는 탐색 시간에 지배된다. 그렇기 때문에 이진 탐색 트리에서 균형을 유지하는 것은 굉장히 .. 힙(heap) Goal 힙(heap)에 대한 이해 힙의 특징을 이해하고, 어떤 상황에서 쓰면 좋은지 설명할 수 있다. 힙을 표현할 수 있다 힙을 사용해서 우선 순위 큐를 구현하고 정렬할 수 있다. 힙(heap)이란? 완전이진트리(complete binary tree)를 기본으로 한 자료구조로서 다음과 같은 힙 속성(heap property)을 만족한다. 힙 속성(heap property) heap order property : 부모 자식 노드간에 대소 비교가 가능하다 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다(최대 힙, Max heap) 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다(최소 힙, Min heap). heap shape property : 완전이진트리 모양이다. (완전이진트리 .. Kruskal 알고리즘 Goal Kruskal 알고리즘에 대한 이해 Kruskal 알고리즘을 구현할 수 있다. Kruskal 알고리즘이 사용되는 예시를 들 수 있다. 사전 필요 지식 최소 신장 트리 Union-Find 크루스칼 알고리즘(Kruskal's algorithm) 탐욕적인 방법(Greedy Method)을 이용하여 모든 정점을 최소 비용을 갖는 간선으로 연결하는 알고리즘 *탐욕적인 방법 : 결정을 할 때마다 "그 순간에 최적"이라고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것 순간의 최적이라고 생각했던 것들을 모아 최종적인 결과를 도출해 낼 때, 그것이 "궁극적으로 최적"이라는 보장은 없다. 하지만!! 다행히 Kruskal 알고리즘은 궁극적으로도 최적의 해를 구하는 것으로 증명 되었다. Kruskal 알고리.. Union-Find Goal Union-Find에 대한 이해 Union-Find 알고리즘을 구현할 수 있다 Union-Find란? Union-Find란, 서로소 집합(Disjoint-Set)을 표현하는 독특한 자료구조이다. (Union, Find라는 연산을 포함하기 때문에 Union-Find(합집합 찾기)라는 이름이 붙었다) *Disjoint Set : 서로소 집합을 다루는 자료구조 Union-Find의 연산 union-find에는 다음과 같은 연산을 제공한다. make-set(x) : x를 유일한 원소로 하는 새로운 집합을 만든다. => 초기화 union(x, y) : x가 속한 셋과 y가 속한 집합을 합친다 find(x) : x가 속한 집합을 찾는다 (집합을 반환, 또는 집합을 대표하는 대푯값(트리의 루트 등)을 반환).. 그래프 순회(Graph Traversal) - BFS , DFS Goal 그래프 순회(탐색)에 대한 이해 BFS, DFS에 대한 이해 BFS, DFS를 구현할 수 있다 그래프 순회(Graph Traversal/Search) 그래프에의 임의의 한 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업 보통 그래프 순회, 그래프 탐색을 동일한 의미로 사용하므로 편의상 그래프 탐색이라 칭하겠다. (단어 의미를 엄밀히 따지자면 그래프 순회가 좀 더 정확한 표현이다) (참고) 더보기 Search vs Traversal 순회(Traversal)와 탐색(Search)이 동일한 의미로 사용 되기도 하는데, 굳이 구분하자면 다음과 같다. 탐색(Search) : index나 해싱 등의 방법으로 원하는 데이터를 빠르게 찾는 방법 순회(Traversal) : 특정 순회 알고리즘을 사용하여.. 반복과 재귀 Goal 순환과 반복을 적절하게 사용할 수 있다. 프로그래밍 언어에서 어떤 일을 반복적으로 수행하는 방법으로 반복(iteration)과 재귀(recursion)가 있다. 반복과 순환, 두 가지의 방법에 대해서 알아보자 반복(iteration) for, while 등의 반복 구문을 이용해서 특정 구문을 반복하는 방법 [반복 구현 코드] int factorial(int n) { int result = 1; for (int i = n; i > 0; i--) { result = result * i; } return result; } 재귀(recursion) 함수가 자기 자신을 호출하는 반복 방법 [재귀 구현 코드] int factorial(int n) { if (n == 1) return 1; else retu.. [BOJ 1799] 비숍 문제 링크 : https://www.acmicpc.net/problem/1799 문제 분류 : 백트래킹 참고 : https://j2wooooo.tistory.com/80 풀이 방법이 생각이 안나서 참고하면서 풀었다. ㅠ.ㅠ 문제 풀이 핵심은 하나는 체스판을 두 부분으로 나누어서 보는 것이다! 위 그림과 같이 체스판을 흰색과 검은색으로 칠하고 보면, 흰색 영역과 검은색 영역은 대각선으로 이동으로는 절대 겹칠 수 없는 영역이다. 즉, 하나의 체스판을 2부분으로 나눠서 생각해볼 수 있다. 최종적으로 검은색 영역 최대 개수 + 흰색 영역 최대 개수 로 답을 구할 수 있다. 한 부분에 대한 시간 복잡도는 다음과 같이 계산될 수 있다. 하나의 칸에 비숍을 놓는경우, 놓지 않는 경우가 존재 => 2가지 흑, 백 각각.. 가중치 그래프(Weighted Graph), 최소 신장 트리(MST) Goal 가중치 그래프에 대한 이해 가중치 그래프를 표현(또는 구현)할 수 있다 최소 신장 트리에 대한 이해 최소 비용 신장 트리를 구할 수 있다 사전 관련 지식 : 그래프 가중치 그래프(Weighted Graph) 그래프의 간선에 가중치가 있는 그래프 가중치 그래프는 다음과 같이 표현된다. G = (V,E, w) V(G) : 그래프 G의 정점 집합 E(G) : 그래프 G의 간선 집합 w(e) : 간선 e의 가중치 (간선의 가중치(weight) 또는 비용(cost) 모두 같은 의미이다.) 가중치 그래치 그래프의 응용 분야는 매우 다양한데, 그 중에서 네트워크를 표현하는데 많이 사용되기 때문에 가중치 그래프를 네트워크라고도 한다. 가중치 그래프는 최소 환승, 최단 경로, 최소 비용 등과 같은 것들을 계산할.. 이전 1 2 3 4 5 6 다음
