코딩테스트16 다익스트라 구현법 1번부터 시작해서 아직 방문하지 않은 것중에서 가장 길이가 작은걸로 순차 탐색 List> 사용우선순위큐 필요Edge는 도착위치 가중치 넣음 컴패라블 오버라이딩해서 맞춤 distance 1차원 배열필요 첨에 맥스값으로 꽉채움 지속적 업데이트 큐가 빌때까지 돌림지금까지 도출된 다음 노드로 가는 거리가 지금 다음 노드 거리보다 작으면 컨티뉴지금 다음의 다음으로 가는 거리와 지금 다음의 거리와 현재 나온 길이를 더해서 작은값으로 distance업데이트 package org.problem.다익스트라;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;// 실버 1 지.. 2026. 4. 1. 조합 구현법 1. 재귀사용2. visited 필요 없음3. 스타트인덱스 전달 package org.problem;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;// 실버 2 로또// 조합 문제public class b6603 { static StringBuilder sb = new StringBuilder(); static int count; static int[] arr; public static void main(String[] a.. 2026. 4. 1. 정렬 버블정렬가장 큰 값이 가장 뒤로 떠오른다(bubble)시간복잡도 n^2실제연산은 n(n-1) / 2 숫자가커질수록 대략적으로 n^2에 가깝게 증가0인덱스부터 옆자리와 비교하면서 위치를 바꾸면서 뒤로간다 그러다보면 가장 오른쪽 제일 큰수부터 하나씩 완성하는것4개 6회10개 45회100개 4950회1000개 499500회n^2의 절반에 가깝게증가함4321342132413214231421341234선택정렬버블정렬과 반대로 앞에서 최솟값부터 채워나간다.가장앞 인덱스를 최솟값으로 지정배열전체를 탐색하며 최솟값을 갱신최솟값지점과 가장앞 인덱스를 교체그 다음 인덱스도 반복시간복잡도 n^2실제연산은 n(n-1) / 2 432113241234버블정렬보다 스왑은 2배 적지만 모든 배열을 탐색하므로 시간복잡도는n(n-1) .. 2025. 12. 6. [그래프] 코딩테스트에서 어떤문제에 어떤 알고리즘을 써야할까?? 이 글은 각 알고리즘의 자세한 구현 방법에 초점을 맞추고 있지 않습니다.실전에서 어떤 문제에 어떤 알고리즘을 써야하는지를 빠르게 파악하는데 초점을 맞추고 있습니다. 실전에서는 문제에 어떤 알고리즘을 써야하는지 알려주지 않습니다.때문에 어떤 알고리즘을 써야하는지 빠르게 파악하고 불 필요한 혼란을 겪지 않는 것이 시간압박을 피하는 최고의 방법입니다. 크게 두 가지의 섹션으로 나누었습니다.1. 그래프에서 자주 쓰이는 알고리즘의 종류와 특징을 살펴본다.2. 각 알고리즘을 어떤 문제에 써야하는지 알아보겠습니다. 1. 그래프에서 자주 쓰이는 알고리즘의 종류와 특징을 살펴보겠습니다 1. BFS (넓이 우선 탐색) : 한 정점에서 다른 모든 정점까지의 최단거리를 계산하는 알고리즘특징 : 자신 주변의 노드부터 차례차례.. 2025. 8. 18. [골드5] 백준 2467 용액 투 포인터(Java) 이분탐색으로도 풀 수 있다고 하던데 전 투 포인터로 풀었습니다. package org.problem.투포인터;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;// 골드 5 용액// 시간 제한 1초 수는 10만 n(logN)까지 허용public class b2467 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); i.. 2025. 7. 30. [골드3] 백준 1238 파티 Java 풀이 package org.problem.다익스트라;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;// 골드 3 파티// 문제// N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.// 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.// 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.// .. 2025. 7. 30. [골드3] 백준 1835 웜홀 Java 풀이 package org.problem.벨만포드;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.StringTokenizer;// 골드 3 웜홀public class b1835 { static final int INF = Integer.MAX_VALUE / 2; static class Edge { int from; int to; int time; public Edge(int fr.. 2025. 7. 30. [골드4] 백준 11404 플로이드 Java 풀이 package org.problem.플로이드워셜;// 골드 4 플로이드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class b11404 { static final int INF = Integer.MAX_VALUE / 2; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int cityTotal .. 2025. 7. 30. [골드2] 백준 11444 피보나치 수 6 Java 풀이 분할정복과 행렬곱셈을 활용하여 풀었다import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;// 골드 2 피보나치 수 6// 100경 번째 피보나치를 구해야 함 시간 제한은 1억 번 연산 이내로 제한public class b11444 { static final long MOD = 1_000_000_007L; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long n = Lon.. 2025. 7. 25. [실버1] 백준 1149 RGB 거리 DP 풀이(Java) package org.practice.dp;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;// 백준 실버 1 RGB거리를 DP로 푼 문제public class b1149DP { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int houseCount = Integer.parseInt(br.readLine()); .. 2025. 7. 25. [실버1] 백준 1149 RGB 거리 DP 풀이(Java) package org.practice.dp;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;// 백준 실버 1 RGB거리를 DP로 푼 문제public class b1149DP { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int houseCount = Integer.parseInt(br.readLine()); .. 2025. 7. 25. [실버1] 백준 1149 RGB 거리 다익스트라 풀이(Java) DP로 푸는게 빠르고 편하지만 다익스트라로도 풀 수 있다.package org.practice.다익스트라;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;// 실버 1 RGB거리// 한 마디로 양 옆에 집이랑 색깔이 같으면 안된다는 것 양 끝 집은 옆 집이랑만 비교하고// 색이 같으면 안된다는 것은 일종의 간선으로 표현할 수 있다. 입력에는 배열로 빨,초,파의 각 견적이 나와있는데// 이것을 선택하는 것을 어떠한 배열에서 특정한 배열로만 이동 가능하다고 보면 코스트를 가진 노드로 표현할 수 있다.// 최소 비용으로 목적지까지 가는 문제와 동일하며 우선순위 큐를.. 2025. 7. 25. 이전 1 2 다음
