24.06.24

2024. 06. 24 월요일

 

- [Java] String을 LocalDateTime 및 LocalTime으로 바꾸는 방법?

: String str = “10:00”이라 할 때,

DateTimeFormatter formatter = DateTimeFormatter.ofPattern(“mm:ss”);

LocalTime time = LocalTime.parse(str, formatter);

이때 LocalDateTime, LocalDate 등으로 바꿀 수 있지만, 각각의 포맷에 맞는 패턴을 모두 사용해야 한다. 즉, 위의 경우에는 LocalTime이었기 때문에 “mm:ss”라는 패턴을 성공적으로 파싱하지만, LocalDateTime에 적용할 경우 에러를 낸다. 단, parse 메서드 이용 등의 형태는 동일하다.

 

 

- 그래프 관련 알고리즘 5개, 설명과 각 차이?

: 크루스칼, 프림, 다익스트라, 벨만 포드, 플로이드 워샬 알고리즘이 있다.

 

크루스칼, 프림은 최소 신장 트리(MST)에 속하며,

최소 신장 트리란 “모든 노드를 최소 비용으로 잇는” 그래프를 의미한다.

둘 다 greedy하게 매순간 최소의 비용 간선을 중심으로 동작한다.

 

다익스트라, 벨만 포드, 플로이드 워샬은 “특정 노드에서 도착 지점까지의 최소 비용”을 목적으로 동작한다. 벨만 포드는 음수 간선이 존재할 때, 플로이드 워샬은 모든 정점에서 다른 정점의 최솟값을 구할 때 사용한다. (음수 사이클의 존재 여부는 확인할 수 있으나, 정상 동작하진 않는다)

 

구현 차이

크루스칼 : greedy [dp(union) + dfs]

프림 : greedy [visited + bfs]

다익스트라 : greedy [dp]

벨만 포드 : INF가 아닌 모든 간선을 노드 수만큼 반복 [dp]

플로이드 워샬 : a -> b -> c로 거쳐서 가는 모든 경우 반복 [dp]