Dev.baelanche

알고리즘 기법 없이 예제에 나온대로 구현했다. 일단 짜고 코드를 정리하려고 했는데 아무래도 안할 것 같아서 그냥 업로드 했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int len = 1; int blank = 0; for(int i=2; i

n 이 커질수록 네모의 개수가 비례하여 증가한다. n 일때 출력될 가로, 세로 길이를 유추하고 분할정복으로 구현했다. public class Main { static char a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int len = 1; for(int i=1; i

각 문자열의 인덱스를 뒤로 미루면서 최소값을 구해야 한다. 예제로 풀면 다음과 같다. a d a a b c a a b a b b c 0 +1 +1 0 0 +1 A의 길이만큼 각 문자열을 비교했다. 각 인덱스가 일치하지 않으면 +1을 하였고 이 경우에는 3 이 나왔다. a d a a b c a a b a b b c 0 +1 0 +1 0 0 A를 한칸 미루어서 비교했다. 마찬가지로 일치하지 않을시 카운트하였고 앞의 경우보다 문자열이 더 일치하므로 답이 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc.next()..

2 : 1 의 페어로 나가야 하므로 n/2 와 m 을 비교하여 큰쪽에서 인턴쉽에 나가게 한다. 출력할때는 n/2 와 m 중 작은쪽을 출력해주면 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); for(int i=k; i>0; i--) { if(n/2 >= m) n--; else m--; } System.out.println(n/2 < m ? n/2 : m); } }

기본적인 이분탐색에서 한번 꼬아낸 문제이다. 각 랜선의 길이 : L 나눌 단위 길이 : D 일때, L / D 의 합이 K 를 만족하는 선에서 최대 길이를 구해야 한다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = sc.nextInt(); int n = sc.nextInt(); int a[] = new int[k]; for(int i=0; i

나무 자르기 문제와 거의 유사한 문제이다. 예산을 더하는 로직만 약간 다를뿐 이분탐색으로 접근하면 된다. 코드 1 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; long sum = 0; int max = 0; for(int i=0; i

이분탐색을 입문하기 좋은 문제이다. 예제로 풀이해보겠다. 나무의 높이는 20, 15, 10, 17 이고 최소값은 0, 최대값은 20이다. 최대값은 나무의 높이 중 가장 큰 것으로 해도 되고 문제에서 주어진 최대값 1000000000 을 사용해도 된다. low 20 15 10 17 high 0 20 정한 low, high 을 2등분 하여 조건을 성립하는 방향으로 범위를 좁혀가야 한다. 0과 20의 중간값은 10 이므로 10의 높이로 나무를 자른다. low 20 15 10 17 high 0 10 5 10 7 20 각 나무는 10, 5, 10, 7 의 길이만큼 남았고 자른 나무는 10, 10, 0, 10 으로 총 30이다. 나무는 적어도 7만큼 가져갈 것이므로 30은 너무 크다. 따라서 자를 높이를 올려야 하..

그래프에 대해 공부해 보았다면 DFS 로 풀 수 있는 문제란걸 유추할 수 있다. 연결된 정보를 가지고 문제를 푼다 -> 그래프 문제 만든 그래프로 최단거리, 최소거리를 구해야 한다 -> BFS 그렇지 않다 -> DFS 네트워크 연결이 한방향으로만 되지는 않을것이고 별도의 언급도 없으니 양방향 그래프라고 볼 수 있다. 2차원 배열로 그래프를 만들어 노드마다 연결된 노드 번호를 매겨주고 카운트를 세어주면 된다. 노드 탐색을 할때 연결된 노드를 전부 탐색한 뒤 재귀호출 하는 방식으로 구성하고 싶어서 큐를 이용했다. public class Main { static int n; static int a[][]; static boolean visited[]; static Queue q = new LinkedList(..