Algorithms

[java] 벨만포드 알고리즘

벨만포드 알고리즘 🔑그래프에서 최단거리를 구하는 알고리즘 ✏️음수 가중치 에지가 있어도 수행이 가능하며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 시간 복잡도: O(VE) 1. 에지 리스트로 그래프 구현> 최단 경로 배열 초기화 tip) 자바의 경우, Arrays.fill을 사용하면 빠르다. static final int INF = Integer.MAX_VALUE; Arrays.fill(arr, INF); 2. 모든 에지를 확인하면서 정답 배열을 업데이트 해준다. 노드 개수가 N이라고 가정할 때, 최단거리 배열에서 업데이트 반복 횟수는 N-1번이다. N개의 노드가 있고 음수 사이클이 없을 때 최단 경로를 구성하는 엣지의 개수는 최대 N-1개가 된다. (N개가 될 수가 없다) ✏️업데이트..

[java] 다익스트라 알고리즘

다익스트라 ✨start 노드와 모든 노드간 거리 탐색, 최단거리를 저장하는 배열 dist[] ✨edge는 모두 양수 ✨시간복잡도 O(ElogV) 🪄시간초과를 대비하여 되도록이면 buffer를 사용하도록 하자 1. 인접리스트로 그래프 구현 2. 최단거리 배열 초기화 3. 값이 가장 작은 노드 고르기 4. 최단거리 배열 업데이트 Min(현재 선택한 노드의 최단거리 배열 값+가중치, 연결 노드의 최단거리 배열 값) 한번 선택된(방문한) 노드는 다시 선택되지 않도록 체크하는 배열이 필요: check[] 백준 1753 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고..

[이분탐색] 징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에 이 문제를 보자마자 while문을 돌리면서 단순히 밟은 디딤돌을 -1 해주는 식으로 코드를 짰더니 testcase는 정답이였지만 어마어마한 시간 초과가... 그래서 이분탐색으로 경로 변경함. 처음에 건널 수 있는가? < 라는 boolean 값을 변수로 선언했는데 자꾸만 답이 3이 아니라 4가 나오거나 시간 초과가 뜨는 것이다... 코드 짜임새도 요상하고 길어지기만 해서 새로운 boolean..

[백준 나무자르기] 이분탐색시 시작 혹은 끝 지점 설정하는 방법

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 😓Arrays.sort 사용하는 방법 - 지양하기 import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStrea..

[java] 이분탐색

백준 1920 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in..

[이분탐색] 프로그래머스 입국심사

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr start 지점: times의 최솟값 end 지점: n명 모두가 심사를 받을 때 가용할 수 있는 최대 시간 📌주의할 점 long end = (long)times[times.length-1]*n; times가 int 배열이므로 (long)으로 형변환 해주기. 요 부분 빼먹으니 정확도 55퍼 나오더라... import java.util.*; class Solution { public long solu..