23.11.01

2023. 11. 01 수요일

 

- MST와 최단 경로 알고리즘 차이? 종류?

: MST는 Minimun Spanning Tree이며,

이때 Spanning Tree는 사이클 없이 모든 정점이 n-1개의 간선으로 연결된 그래프.

 

최단 경로 알고리즘은 특정 노드에서 다른 특정 노드로 가는 길을 최소의 비용으로 가는 방법을 찾는 것.

 

둘은 목적이 다르다. MST는 전체적으로 최소의 비용을 고르기에, 최단 경로 알고리즘처럼 특정 노드에서 다른 특정 노드로 가는 최소 비용을 보장하지 않는다. MST는 무향 그래프에서만 동작하며, 최단 경로 알고리즘은 유, 무향 모두 동작한다.

 

MST

1. 크루스칼 – 간선 중심 // 최소 가중치의 간선으로 정렬 후 순서대로 두 노드의 부모를 같게 만들어줌.

2. 프림 – 노드 중심 // 이어진 노드 중 가장 최소의 가중치 구함.

 

최단 경로 알고리즘 (순서대로 속도가 느림)

1. 다익스트라 – 양수 가중치만 가능, 그리디. 특정 노드에서 모든 노드로 최소 간선을 구함. // 최소 가중치로 정렬하여, 방문 체크, 이후 해당 노드와 연결된 모든 노드를 확인하며 방문을 검사하고 아니라면 해당 노드의 기존 가중치와 현재 노드 가중치 + 해당 노드의 가중치 중 작은 값으로 업데이트. 그리고 다시 que에 추가.

2. 벨만 포드 – 음수 가중치도 가능.

3. 플로이드 와샬 – 음수 가중치도 가능. O(n^3)

 

 

- [Spring] lombok이란? 주요 어노테이션?

:  보일러 플레이트 코드를 줄여주는 라이브러리 (어노테이션)

 

@Getter/Setter : Java Bean 규약의 Getter, Setter 생성

@ToString : 객체의 데이터를 보여주는 toString() 생성

@No/All/RequiredArgsConstructor : 객체 생성자 자동 생성

@Data : Getter + Setter + ToString + EqualsAndHashCode + RequiredArgs + Value

@Builder : 빌더 패턴 생성

@Slf4j : 해당 클래스의 logger 자동 생성
(Logger logger = org.slf4j.LoggerFactory.getLogger(클래스명.class);)

@UtilityClass : static 메서드만 제공하는 유틸리티 클래스의 생성자를 private으로 만들어 객체 생성을 불가하게 함

 

ArgsConstructor 차이

No/All : 없거나/모든 필드들을 초기화하는 생성자 생성.

Required : private final로 선언된 필드들을 초기화. 스프링의 생성자 주입 시 쓰임.