[JAVA] 백준 2749 - 피보나치 수 3
2022. 8. 18. 21:14
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 해결 방법 문제에서 주어진 n이 1,000,000,000,000,000,000 이하의 자연수 반복문을 돌릴 수 없음 결과값은 피보나치 수를 1,000,000로 나눈 나머지이기 때문에 int 형으로도 처리할 수 있음 고민해본 결과, 피보나치 수를 1,000,000으로 나눈 나머지가 언젠가는 반복될 것이라는 생각이 들었음 코딩을 통해 반복되는 수를 찾음 피보나치 1,500,000 번째 숫자를 1,000,000으로 나눈 나머지는 0이었고, 피보나치 1,500,001 번째 숫자를..
[JAVA] 백준 1260 - DFS와 BFS
2022. 8. 18. 20:05
JAVA/백준(BOJ) 문제풀이
DFS, BFS 설명 및 백준 1260번 문제 풀이 https://chb2005.tistory.com/76 [JAVA] DFS, BFS DFS, BFS 란? DFS : Depth First Search의 줄임말로 깊이 우선 탐색을 뜻함 BFS : Breadth First Search의 줄임말로 너비 우선 탐색을 뜻함 다음과 같은 그래프를 탐색한다고 가정 DFS 수행 과정 1번 노드에서 시.. chb2005.tistory.com
[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