개발일지

목차 브루트포스 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 장점 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 단점 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매우 비효율적이다. 브루트포스 종류 ✔️선형 구조 : 순차 탐색 ✔️비선형 구조 : BFS(넓이 우선 탐색), DFS(깊이 우선 탐색) (1) 선형 구조 : 하나의 자료 뒤에 하나의 자료가 존재하는 것으로, 앞 뒤의 관계가 1:1의 선형관계를 말한다. ex) 선형 구조 : 배열, 리스트, 스택, 큐 / 탐색 방법 : 순차..

MST는 간선에 가중치를 고려하여, 최소 비용의 스패닝 트리를 선택하는 것이다. [조건] 본래의 그래프의 모든 노드를 포함한다. 간선의 가중치의 합이 최소여야 한다. 모든 노드가 서로 연결되어 있다. 트리의 속성을 만족한다. 즉, 사이클이 존재하지 않는다. *사이클 : 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있는 것을 뜻한다 ✅ 크루스칼 알고리즘 최소 비용 신장 트리를 찾는 알고리즘으로, 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 스패닝 트리를 찾음으로써 간선의 가중치의 합이 최솟값으로 되도록 하는 알고리즘이다. 동작원리 모든 간선들을 가중치를 기준으로 오름차순으로 정렬한다. 가중치가 가장 적은 간선을 선택한다. 선택한 간선이 연결하려는 2개의..

목차 이진 탐색 트리 각 노드의 값이 왼쪽 서브트리에 속한 모든 노드의 값보다 크고 오른쪽 서브트리에 속한 모든 노드의 값보다 작은 이진 트리이다. 이진 탐색 트리는 데이터를 효율적으로 검색할 수 있다. 원하는 값을 찾을 때까지 현재의 노드값보다 찾고자하는 값이 작으면 왼쪽으로 움직이고, 크면 오른쪽으로 움직인다. 이렇게 원하는 값을 더 빠르게 찾을 수 있게 된다. 중복값을 허용하지 않는다. 이진 탐색 트리와 힙의 차이 이진 탐색 트리 힙 정렬 방식 정렬된 데이터 저장 일정한 순서(최소힙 또는 최대 힙) 중복 중복 허용 안함 중복 허용 주 용도 - 연산에 특화(데이터 삽입,삭제,검색에 효율) - 특정 트리를 빠르게 탐색하는데 유용 최대 또는 최소값을 빠르게 찾을 때 유용 이진 탐색 트리 삽입, 삭제 과정..

목차 힙이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙을 사용하는 이유? 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다. 하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다. 우선순위 큐와 같이 최댓값 또는..

목차 트리란? 트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 트리는 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 트리 구조에서 사용되는 기본 용어 노드 (Node) 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음. A, B, C, D, E, F, G, H, I, J 간선 (Edge) 노드와 노드 간의 연결선 루트 노드 (Root Node) 트리 구조에서 부모가 없는 최상위 노드 root node : A 부모 노드 (Parent Node) 자식 노드를 가진 노드 H, I에 부모 노드는 D 자식 노드 (Child node) 부모 노드의 하위 노드 노드 D의 자..