알고리즘

문제문제 바로가기풀이흔히 생각하는 m부터 n까지 각 수에 약수를 하나하나 검사하면 O^2최악의 경우 1,000,000^2 의 시간복잡도를 가짐으로 시간 초과나는 아래 두가지 방법을 문제에 적용시킴에라토스테네스의 체에라토스네스의 체: 각 수를 검사하면서, 해당 수의 배수를 지움이럴 경우 검사해야 하는 수가 줄어듬제곱근 까지만 검사어떤 수에 대해서, 그 수의 약수는 대칭 쌍을 가짐ex) 12에 대하여: 26, 62(대칭) / 34, 43(대칭)/이때 대칭쌍을 이루기 때문에 소수를 판별 할 때는 대칭 쌍을 이루는 두 수 중 하나에 대해서만 검사하면 됨ex) 12에 대해, 2*6을 검사할 경우, 12약수에 2를 포함하는지만 검사하면 6은 자연히 따라옴, 즉 2만 검사하면 됨이때 대칭쌍을 이루는 두 수 중, 하나..

문제문제 바로가기풀이문자열의 한 문자씩 스택에 삽입삽입할 때 마다, 스택의 마지막 문자열이 폭발 문자인지 검사 및 처리스택에서 특정 길이의 문자열 추출을 쉽게 하기 위해, 배열 및 인덱스로 스택 구현코드class Main { public static void main (String[] args) throws java.lang.Exception { // input BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); String bumb = br.readLine(); int bumbLen = bumb.length()..

문제문제 바로가기풀이플로이드-워셜 알고리즘으로 접근각 도시에서 다른 도시들에 대한 최단 거리를 구함그 후 각 도시에 대해, X번 도시를 왕복하는 시간들의 최대값을 구함코드// Don't place your source in a packageimport java.util.*;import java.lang.*;import java.io.*;// Please name your class Mainclass Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String..

문제문제 바로가기풀이평범하게 플로이드 알고리즘을 적용하면 된다.같은 출발노드와, 도착노드를 가지는 여러개의 간선이 존재할 수 있으니 유의하자코드// Don't place your source in a packageimport java.util.*;import java.util.stream.*;import java.lang.*;import java.io.*;// Please name your class Mainclass Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

문제문제 바로가기풀이임의의 노드에서 DFS 탐색으로 끝점 탐색끝점: 탐색을 시작한 노드에서 가장 거리가 먼 노드어느 노드에서든 DFS로 탐색을 하면서 최대 거리를 가진 노드를 찾으면, 해당 노드가 끝점임찾은 끝점에서 다시 한번 DFS 탐색을 통해 반대편 끝점을 구함두 끝점 사이의 거리가 트리의 지름코드// Don't place your source in a packageimport java.util.*;import java.util.stream.*;import java.lang.*;import java.io.*;class Edge { int dest; int weight; public Edge(int dest, int weight){ this.de..

문제문제바로가기풀이각 자료구조는 큐, 스택으로만 이루어져있음스택에 값 push 후 pop을 하면, push한 값이 그대로 나옴즉 나열된 자료구조에서 스택은 무시 가능스택을 제거하고 나면, 남은 자료구조는 큐로만 이루어져있음즉 그냥 큐 그 잡채코드// Don't place your source in a packageimport java.util.*;import java.util.stream.*;import java.lang.*;import java.io.*;// Please name your class Mainclass Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader br =..