우당탕탕 개발일지

유클리드 호제법이란 두 정수의 최대공약수(GCD)를 구하는 알고리즘으로 나눗셈과 나머지 연산을 반복적으로 사용하여 최대공약수를 계산한다. [백준] 2609 최대공양수와 최소공배수https://www.acmicpc.net/problem/2609  일반적으로 최대공약수를 구하기 위해서는 소인수분해를 진행하여 구한다.소인수분해 방법 import java.io.*;import java.util.*;public class Main { static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int gcd(int n, int m){ int answer = 1; int divisor = 2; ..

이진 탐색이란? 이분 탐색이라고도 불리는 이진 탐색은 정렬된 데이터에서 특정 값을 찾는 탐색 알고리즘이다.탐색 범위를 절반씩 줄여가며 값을 찾기 때문에 시간 복잡도가 O(logn)으로 빠른 탐색이 가능하다. Binary Searchimport java.io.*;import java.util.*;public class Main { static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int[] arr; static boolean binarySearch(int target) { int left = 0; int right = arr.length - 1; ..

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 요소가 특정 우선순위에 따라 정렬되는 큐 인터페이스의 구현체로, 항상 우선순위가 높은 요소를 먼저 꺼낼 수 있다. 기본적으로 우선순위 큐는 힙(Heap) 자료구조를 기반으로 동작한다. 힙이란? 이진 트리 기반의 자료구조로, 특정 규칙에 따라 부모 노드와 자식 노드 간의 관계를 유지하며 최댓값 또는 최솟값을 찾아내는 연산이 빠르다. 힙은 최대 힙, 최소힙 두 가지 유형으로 구분된다. Java에서는 힙을 PriorityQueue 클래스를 사용해 구현할 수 있다.주로 오름차순, 내림차순 정렬 방식을 이용하여 큐를 정의한다.오름차순 PriorityQueue pq = new Priorit..

플로이드 워셜이란 그래프 최단 경로를 구하는 알고리즘 중 하나로, 모든 정점에서 모든 정점까지 최단 거리를 구하는 알고리즘이다. 플로이드 워셜 알고리즘의 점화식은 다음과 같다. 다익스트라 알고리즘과 비슷해보이지만, 소스코드가 다익스트라에 비해 짧고 구현이 쉽다.  다익스트라 알고리즘단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다.1차원 리스트에 저장한다. 플로이드-워셜 알고리즘모든 지점에서 다른 모든 지점까지의 최단 거리를 저장한다.2차원 테이블에 저장한다.for (int k = 0; k   [ BOJ 11403 ] 경로 찾기https://www.acmicpc.net/problem/11403 처음에는 그래프 인접 리스트로 만들어 풀이를 하였으나 간과한 부분이 있었다. 1. 경로 탐색i → ..