728x90 IT Tech/Application37 트리 : 우선순위 큐 완전 이진트리 형태의 자료구조 일차원 배열로 구현 배열로 구현하였기 때문에 부모 또는 자식 노드를 찾아가는 연산을 구현하기도 간편하다. 왼쪽 자식노드 index = (부모 노드 index) * 2 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1 부모 노드 index = (자식노드 index) / 2 최소힙 : 부모노드의 키 값이 자식노드의 키 값보다 항상 작다. 최대힙 : 부모노드의 키 값이 자식노드의 키 값보다 항상 크다. 힙(Heap) 삽입연산 1. 트리의 가장 마지막 위치에 노드 추가 2. 추가된 노드와 그 부모 노드관계가 힙조건을 만족하는지 확인 3. 만족하지 않을 경우 부모와 자식의 키값 교환 4. 조건이 만족하거나 추가된 노드가 root 노드가 될때까지 2, 3번 과정 반.. 2022. 9. 16. 트리 : MST (Minimum Spanning Tree), 최소신장트리 MST : 그래프의 모든 정점을 연결할 수 있는 최소비용의 트리 만들기 신장트리(Spanning Tree) : 무방향으로 모든 정점을 포함하는 트리 . 깊이우선트리(DFS) 신장트리 : Depth가 높고 길죽하게 생성되는 트리 . 너비우선(BFS) 신장트리 : Depth는 낮지만 넓게 생성되는 트리 구현방법 2가지 1. 크루스칼 알고리즘 : 간선을 하나씩 선택해서 MST를 만듬 a. 최초에 모든 간선을 가중치에 따라 오름차순으로 정렬 b. 간선의 가중치가 낮은 간선을 선택, (Union-Find로 사이클 여부 체크) c. 모든 간선이 선택될때까지 반복 -> 중간단계에서는 하나의 트리가 아닌 여러개의 트리가 생성되며 최종적으로 하나의 트리로 연결됨 2. 프림 알고리즘 : 하나의 정점에서 연결된 간선들 중에.. 2022. 9. 16. 다익스트라와 관련 알고리즘 : 벨만포드, BFS, 플로이드워셜 벨만포드 - 음수간선 처리 가능(음수간선은 반드시 단방향) - 약 3000개 노드 BFS - 모든 간선이 동일한 가중치를 가지는 경우 플로이드워셜 - 모든 쌍의 최단경로 계산 - 200~400개 노드 2022. 9. 16. 다익스트라 1. 다익스트라 - 음수 가중치가 없는 그래프에서 시작 정점에서 다른 정점으로 최단 경로를 구하는 알고리즘 - 우선순위 큐를 활용하여 구현 - 기본동작 . 모든 정점의 거리를 무한대로 설정 . 출발점에서 주변의 정점들을 방문하며 거리 갱신 . 미방문 정점 중 가장 거리가 짧은 정점 선택 . dist[A] + Edge[A,X] 2022. 9. 13. DDD 바운디드 컨텍스트 기반 마이크로서비스 도출 서비스가 소유권을 가진 데이터를 독립적으로 식별하는 것이 중요 서비스의 기능에 의해서만 접근 가능(캡슐화)하도록 데이터를 식별해야 한다. 하나의 통합된 데이터가 여러 서비스에 사용된다면 데이터에 의해서 서비스의 독립성이 홰손된다. 즉 데이터를 기능과 분리해서 식별하지 않고 문제 영역인 하위 도메인마다 별도의 도메인 모델(바운디드 컨텍스트)을 정의해야 한다. * 바운디드 컨텍스트 : 다른 켄텍스트와 구별되는 경계 바운디드 컨텍스트의 특징 : 이쪽 도메인에서 사용되는 언어의 개염과 저쪽 도메인에서 사용되는 언어의 개념이 상이한 경계가 도메인의 경계, 즉 바운디드 컨텍스트임 도메인의 분류 - 핵심도메인 - 서브도메인 - 일반도메인 2022. 2. 4. 이전 1 2 3 4 5 ··· 8 다음 반응형
