[JAVA] 백준 1753 - 최단경로
2022. 8. 18. 20:04
JAVA/백준(BOJ) 문제풀이
다익스트라 알고리즘 설명 및 백준 1753 문제 풀이 https://chb2005.tistory.com/78 [JAVA] 다익스트라 (Dijkstra) (+ Priority Queue을 사용한 시간 단축) Dijkstra 란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 단, 가중치에 음수가 있으면 사용할 수 없음 시간복잡도 : O(E logN) (N:노드의 수, E: 간선의 수) 다음과 같은 그래프가 있 chb2005.tistory.com
[JAVA] 백준 11657 - 타임머신
2022. 8. 18. 20:02
JAVA/백준(BOJ) 문제풀이
벨만포드 알고리즘 설명 및 백준 11657번 문제 풀이 https://chb2005.tistory.com/79 [JAVA] 벨만포드 알고리즘 (Bellman-Ford) Bellman-Ford 알고리즘 이란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능 시간복 chb2005.tistory.com
[JAVA] 백준 11404 - 플로이드
2022. 8. 18. 20:00
JAVA/백준(BOJ) 문제풀이
플로이드-워셜 알고리즘 설명 및 백준 11404번 문제 풀이 https://chb2005.tistory.com/80 [JAVA] 플로이드-워셜 알고리즘 (Floyd-Warshall) Floyd-Warshall 알고리즘 이란? 모든 노드간에 최단거리를 구하는 알고리즘 다익스트라, 벨만포드는 한 노드에서 모든노드까지의 최단경로 Floyd-Warshall은 모든노드에서 모든노드까지의 최단 경로 벨 chb2005.tistory.com
[JAVA] 백준 1717 - 집합의 표현
2022. 8. 18. 19:59
JAVA/백준(BOJ) 문제풀이
Union-Find 설명 및 백준 1717번 문제 풀이 https://chb2005.tistory.com/81 [JAVA] Union-Find Union-Find 란? Union : 특정 2개의 노드를 연결해 1개의 집합으로 묶는 작업 Find : 특정 2개의 노드가 같은 집합에 속해 있는지 확인하는 작업 다음과 같이 6개의 노드가 있다고 가정 (1, 2), (2, 3), (4, 6), chb2005.tistory.com
[JAVA] 백준 2042 - 구간 합 구하기
2022. 8. 18. 19:57
JAVA/백준(BOJ) 문제풀이
세그먼트 트리 설명 및 백준 2042번 문제 풀이 https://chb2005.tistory.com/83 [JAVA] 세그먼트 트리 (Segment Tree) Segment Tree 란? 데이터 집합이 주어지고, 특정 구간의 합, 최대, 최소 값을 구해야하는 문제가 주어짐 이 때, 구간이 여러개이거나 데이터가 업데이트 될 수 있는 상황에서 더 빠르게 찾아내기 위 chb2005.tistory.com
[JAVA] 백준 2098 - 외판원 순회
2022. 8. 18. 19:56
JAVA/백준(BOJ) 문제풀이
TSP 알고리즘 설명 및 백준 2098번 문제 풀이 https://chb2005.tistory.com/86 [JAVA] 외판원 순회 문제 (TSP) + 시간초과 해결방법 외판원 순회 문제(TSP) 란? 모든 도시들 간에 이동비용이 주어졌을 때, 각 도시들을 한번만 방문하고 처음 시작점으로 돌아오는 최소 비용을 구하는 문제 TSP의 핵심 논리는 반복되는 부분을 제거 chb2005.tistory.com
[JAVA] 백준 17387 - 선분 교차 2
2022. 8. 18. 19:54
JAVA/백준(BOJ) 문제풀이
CCW 설명 및 백준 17387번 문제 풀이 https://chb2005.tistory.com/87 [JAVA] CCW CCW 란? Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때 CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*.. chb2005.tistory.com