Dev.baelanche

1부터 n-1 까지 최대힙으로 넣어준다. 마지막으로 배열의 n 자리에 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+1]; for(int i=1; i1; j/=2) a[j] = a[j/2]; a[1] = i+1; } a[n] = 1; for(int i=1; i

최소 힙을 문제에 맞춰 구현했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); MinHeap h = new MinHeap(100001); int n = sc.nextInt(); for(int i=0; i1; i/=2) { if(heap[i/2] > heap[i]) swap(i/2, i); else break; } } public int delete() { if(size == 0) return 0; int root = heap[1]; heap[1] = heap[size]; size--; for(int i=1; i*2

최대힙을 구현하여 문제에 맞춰 동작하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); MaxHeap h = new MaxHeap(100001); int n = sc.nextInt(); for(int i=0; i1; i/=2) { if(heap[i/2] heap..

배열에 대해서 방문한 적이 없고 땅이라면 인접한 땅에 대해서 DFS 를 한다. DFS 한 컴포넌트의 개수를 세어주면 된다. public class Main { static int w; static int h; static int a[][]; static boolean visited[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { w = sc.nextInt(); h = sc.nextInt(); if(w == 0 && h == 0) break; a = new int[h][w]; visited = new boolean[h][w]; for(int i=0; i

수의 개수가 10,000,000 이라 배열에 모두 담게되면 메모리 초과로 풀 수 없다. 정렬할 수가 10000 이하 라는것을 이용하여 수가 입력된 개수를 세어 정렬하는 카운팅 정렬(계수 정렬)으로 풀 수 있다. 풀이 1 public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); int a[..

줄의 개수가 최대 1000000 이라서 선택, 거품, 삽입 정렬 등의 느린 정렬방법으로는 풀 수 없다. 병합(합병) 정렬, 힙 정렬, 퀵 정렬 등으로 풀 수 있는데, 언급한 3가지 정렬 방법으로 모두 구현해 보겠다. 1. 병합 정렬(Merge Sort) public class Main { static int temp[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n; n ..

분할정복으로 * * * ***** 모양을 위, 왼쪽, 오른쪽으로 3등분하여 재귀호출하여 구현했다. public class Main { static char a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int alpha = n/3 - 1; a = new char[n][n/3*5 + alpha]; for(int i=0; i

n*n 크기의 2차원 배열을 구현하기에는 메모리가 너무 크다. 문제에서 말한대로 진행하는데는 문제가 있어 보인다. 배열을 만들지 않아도 인덱스 별로 i*j 가 들어간다는걸 이미 알고 있으므로, 루프 하나로 한 줄을 한번에 카운트 해주면 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long k = sc.nextLong(); long left = 0; long right = (long)n*n; while(left = k) right = mid - 1; else left = mid + 1; } System.out.println(lef..