전체 글

그래프 구현 방법 2가지 그래프를 구현할 때, 보통 ArrayList를 이용하였는데, Map을 이용하여 구현하는 방법도 익혀보고자 작성하게 되었습니다. ArrayList[] 배열을 사용 그래프 크기가 고정되어 있어야하므로, 최대 크기로 배열의 크기를 선언해야 함 final int MN = 100; ArrayList[] graph = new ArrayList[MN]; for(int i=0; i

플로이드 워셜(Floyd Warshall) 로버트 플로이드와 스티븐 워셜이라는 컴퓨터 과학자가 고안한 알고리즘 시간복잡도 O(V^3) 사용하는 경우 모든 쌍에 대해 최단거리를 구해야 하는 경우 아이디어 A -> B 경로보다 A -> X -> B로 가는 경로가 더 짧을 경우, 업데이트 방법 2차원 배열 dist[][]를 INF로 초기화. dist[a][b]는 a에서 b로 가는 거리를 뜻하므로, dist[a][a]일 경우 0변경 주어진 경로 거리(가중치) 갱신 dist[a][b]에서 노드 k(1 dist[a][k] + dist[k][b] 만족하는 경우, 해당 값으로 갱신 => 모든 쌍 (a, b)에 대해 노드 k를 경유하는 것이 더 좋은지 확인함 정리 3개의 for문으로 이루어진 3중 반복문으로써 비효율적임..

[구름톤챌린지] 문제 # https://level.goorm.io/exam/195690/%ED%86%B5%EC%A6%9D/quiz/1 N만큼의 통증을 0으로 만들기위한 최소한의 치료약 사용 개수를 구하는 문제 내가 작성한 코드 /* 9개의 테스트케이스 통과 못한 코드 */ import java.io.*; import java.util.*; class Main { static final int MN = (int)1e9; static int N; static int[] dp; static int[] items = {1, 7, 14}; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(n..

[구름톤챌린지] 문제 # https://level.goorm.io/exam/195689/%EA%B5%AC%EB%A6%84-%EC%B0%BE%EA%B8%B0-%EA%B9%83%EB%B0%9C/quiz/1 임의의 칸에서 8방향의 인접한 칸을 탐색하여, 인접한 칸들 중 구름이 있는 칸의 개수를 저장하고 주어진 값`K`와 동일한 값을 칸의 개수로 가지는 칸이 몇 개가 존재하는지 구하는 문제 내가 작성한 코드 import java.io.*; import java.util.*; class Main { static final int DIR_NUM = 8; static int[] dy = {-1, -1, -1, 0, 1, 1, 1, 0}; static int[] dx = {-1, 0, 1, 1, 1, 0, -1, -1..

[백준/BOJ] 문제 # https://www.acmicpc.net/problem/2847 주어진 단계별 점수를 오름차순으로 만들기위해 최소한으로 점수를 감소시켜야하는 횟수를 구하는 문제 내가 작성한 코드 import java.io.*; import java.util.*; public class BOJ2847 { static int N; // 레벨의 수 static int[] scores; // 단계별 점수 static int cnt = 0; static int highScore; // 점수를 몇 번 감소시켜야 하는지 기준이 되는 점수 public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader..

[백준/BOJ] 문제 # https://www.acmicpc.net/problem/1003 주어진 정수를 인수로 피보나치 함수를 호출하게 될 때, 0과 1을 인수로 피보나치 함수를 호출하는 경우가 각각 몇 번인지 구하는 문제 주어지는 정수는 40까지 주어지지만, 실제로 모든 피보나치함수를 호출할 수 없으니 dp를 이용하여 해결해야하는 문제 내가 작성한 코드 package boj; import java.io.*; import java.util.*; public class BOJ1003 { static final int MN = 40; static int[][] dp; static int T; static int N; public static void main(String[] args) throws Exce..

[구름톤챌린지] 문제 # https://level.goorm.io/exam/195688/%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%82%98%EB%88%84%EA%B8%B0/quiz/1 내가 작성한 코드 import java.io.*; import java.util.*; class Case{ String first, second, third; // 3개의 부분문자열 Case(String first, String second, String third){ this.first = first; this.second = second; this.third = third; } } class Main { static int higherScore = Integer.MIN_VALUE; // 가장 높은 점수 ..

[구름톤챌린지] 문제 # https://level.goorm.io/exam/195687/%EC%9D%B4%EC%A7%84%EC%88%98-%EC%A0%95%EB%A0%AC/quiz/1 내가 작성한 코드 import java.io.*; import java.util.*; class Pair implements Comparable{ int num, cnt; Pair(int num, int cnt){ this.num = num; this.cnt = cnt; } @Override public int compareTo(Pair p){ return this.cnt == p.cnt ? p.num - this.num: p.cnt - this.cnt; } } class Main { static int N, K; // 1..