기록장

최소 스패닝 트리신장 트리 (Spanning Tree)그래프에서 일부 간선을 선택해 만든 트리최소 연결로 이루어짐 즉, 모든 노드가 가장 적은 간선 수로 이어져있는 경우에 해당정점이 n개일 때 간선이 n-1개이면 스패닝 트리BFS, DFS로 신장 트리 찾기 가능 (탐색 도중 사용한 간선을 모으면 됨)최소 비용 신장 트리 (Minimum Spanning Tree, MST)스패닝 트리 중 사용된 간선들의 가중치 합이 최소인 트리각 간선의 가중치가 동일하지 않을 경우, 단순히 적은 간선을 쓴다고 최소비용이 되는 건 아님사이클이 없어야 함구현 방법으로는 Kruskal, Prime 알고리즘이 있는데 둘 다 그리디한 방법임Kruskal Algorithm간선을 비용이 낮은 것부터 v-1개 선택하며 떨어져있던 노드를 ..

위상 정렬방향 그래프에서 간선으로 정점 간 선후관계가 주어졌을 때, 선후관계가 위배되지 않도록 나열하는 정렬하나의 그래프에 여러 개의 위상 정렬 결과가 있을 수 있음그래프 내에 사이클이 없어야 위상 정렬이 만들어질 수 있음 (사이클이 없는 방향 그래프: DAG(Directed Acyclic Graph)위상 정렬의 시간 복잡도는 O(V+E) -> 모든 정점을 큐에서 한 번씩 꺼내면서 연결된 간선을 제거함 O(V) + 각 간선을 한 번씩 탐색하면서 진입 차수를 감소시킴 O(E) -> 빠른 속도의 알고리즘구현 방법위상 정렬을 코드로 구현할 때 매번 정점과 간선을 지우면 매번 O(V^2)로 동작하게 될 것이다.대신 미리 indegree 값을 저장해뒀다가 매번 indegree값을 1씩 감소시키는 방법을 사용하면 ..

Rest API의 응답값을 넘기는 형식 중 하나데이터를 캡슐화하는 방법왜 필요한가?public class Member { private Long id; private String name; private int age;}{ "id" : 1, "username" : "홍길동", "age" : 15}Member라는 객체를 JSON형태로 표현하면 다음과 같다. [ { "id":1, "username":"홍길동", "age":15 },{ "id":2, "username":"아무개", "age":24 }, ... { "id":99, "username":"개똥이", ..