알고리즘 저장소 (일반방식과 나만의 풀이)

[백준] no21736: 헌내기는 친구가 필요해 - BFS 지도탐색

문제 * 주어진 campus라는 맵에서 * 도연(I)가 이동 가능한 칸에 한해서 * 친구(P)의 개수를 구해라 * 만약 없으면 TT 출력 문제 링크 : https://solved.ac/search?query=21736 원리 전형적인 BFS 지도탐색 문제 1. BFS 공식을 이용한 상하좌우 탐색 private static int[] hor = {0, 0, -1, 1}; private static int[] ver = {-1, 1, 0, 0}; private static boolean[][] visit; private static void BFS() { Deque dq = new ArrayDeque(); dq.add(new Node(DY[0], DY[1])); visit = new boolean[N][M];..

[백준] no14940: 쉬운 최단거리

문제 * 배열의 세로(N)와 가로(M)와 0,1,2로 이루어진 이중 배열이 주어진다. * 이 때, 2는 딱 한칸만 주어진다. * 2로부터 각 칸까지의 거리를 모두 구하시오 * 단, 0일경우 이동이 불가한 칸이기에 0을 입력 * 단, 1이지만 도달할 수 없는 칸은 -1을 입력 문제 링크 : https://www.acmicpc.net/problem/14940 원리 1. BFS를 위한 Node클래스 private static class Node { private int Y, X, Cnt; public Node(int y, int x, int cnt) { Y = y; X = x; Cnt = cnt; } } 2. BFS 공식 : 여기서 시작용 int 값인 baseY와 baseX는 BFS()를 호출하는 main메소..

[백준] no11444: 피보나치 수 6 - 수학(행렬)

문제 * 피보나치 수열에서 N번째 숫자를 출력하는 문제 * 여기서 핵심은 순서가 최대 1000000000000000000번째까지라는 점이다. * 또한, 출력은 1000000007로 나눈 나머지를 출력한다. 즉, 출력하는 숫자 자체는 int범위 안에서 해결가능 원리 결론적으로 말하자면 이 문제는 행렬 (선형대수) 푸는 것이 출제자의 의도다. (필자는 피보나치를 보자마자 DP라고 생각했다가 헤맸다.) 여러개의 방정식을 하나의 핼렬꼴로 표현하면, 다음이 가능해진다. 1. 선형방정식의 해가 존재하는지 없는지 판단 2. 가우스 소거, 크래머 공식 등 여러 방법에 의해 쉽게 미지수에 대한 답 혹은 일반항을 찾기 즉, 다음과 같이 선형방정식을 행렬 꼴로 변환해서 풀이한다. Ax = b 형태 이에 관해 Stargaze..

[백준] no10768: 특별한 날

문제 * 년도는 2015년을 기준으로 계산 * 입력된 월, 일과 2월 18일을 비교 * 2월 18일과 같으면 Special 출력 * 2월 18일보다 빠르면 Before 출력 * 2월 18일보다 늦으면 After 출력 문제 링크 : https://www.acmicpc.net/problem/10768 LocalDateTime 사용 방법 /* 객체 생성 방법 */ LocalDateTime BeforeTime = LocalDateTime.of(년도, 월, 일, 시, 분, 초); LocalDateTime AfterTime = LocalDateTime.of(년도, 월, 일, 시, 분, 초); /* 비교 방법 */ BeforeTime.isBefore(AfterTime); AfterTime.isAfter(BeforeT..

[백준] no1967: 트리의 지름

문제 * 트리의 지름 = 두 노드 사이의 거리가 가장 긴 경로를 구하는 것 * 즉, Node A -> Node B 의 이동에 따른 비용이 다 다르므로, * 모든 노드를 대상으로, 둘 사이가 이동이 가능할 때, 최대 비용 경로를 구하는 것 문제 링크 : https://www.acmicpc.net/problem/1967 원리 1. BFS + PriorityQueue + Integer[][] 사용 2. DFS + ArrayList형 배열 사용 * 주의할 점 : 문제의 조건에서 최대 노드의 개수가 10000이므로, 10000 x 10000을 감당할 수 있어야함. 즉, 비용을 저장하고 탐색하기위해 일반적인 이중 배열을 사용하면 메모리 초과 발생 풀이방법 BFS + PriorityQueue 방식 1. 각 출발지점과..