Dev.baelanche

배열의 최대길이가 20이므로 전 구간을 완전탐색한다. 처음에 좀 헤맸는데 재귀를 쓰라는 힌트를 보고 풀었다. 메모이제이션 기법만 안썼지 구현방법은 dp 와 다를게 없다. public class Main { static int n; static int s; static int a[]; static int cnt = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); s = sc.nextInt(); a = new int[n]; for(int i=0; i= n) return; sum += a[idx]; if(sum == s) cnt++; recursive(idx + 1, sum - a[..

퀵정렬로 정렬하여 k-1 의 인덱스를 출력했는데 96%에서 계속 시간초과가 났다. 질문게시판을 보니 퀵정렬 대신 퀵셀렉트를 써야된다고 한다. 퀵셀렉트는 퀵정렬 도중 원하는 인덱스를 바로 캐치하는 알고리즘인데, 공부할 것도 많은데 알아보기 귀찮았다. 그래서 합병정렬로 해봤는데 역시나 풀린다.... '잘' 구현할거 아니면 퀵정렬보다는 합병정렬 쓰는걸 추천한다. 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 Bu..

Comparator 구현해서 5분만에 풀었다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String a[] = new String[n]; for(int i=0; i

정렬을 오름차순 혹은 내림차순으로 해주고 큰 수 > 작은 수 > 큰 수 > 작은 수 순으로 배치하여 넓이를 구하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a[] = new int[4]; for(int i=0; i

Comparator 클래스를 구현하여 문제에서 요구하는대로 정렬을 구현했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[][] = new int[n][2]; for(int i=0; i

Set(집합) 라이브러리를 이용하여 풀었다. 다음번에는 자료구조를 직접 구현해서 풀어야겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int an = sc.nextInt(); int bn = sc.nextInt(); TreeSet a = new TreeSet(); TreeSet b = new TreeSet(); for(int i=0; i

예제로 트리 구조를 유추해보자. 전위 순회 : 3 6 5 4 8 7 1 2 중위 순회 : 5 6 8 4 3 1 2 7 전위 순회는 루트부터 시작하고, 중위 순회는 루트를 중심으로 왼쪽 서브트리, 오른쪽 서브트리로 나뉜다. 전위 순회의 첫번째가 3이므로 루트 노드는 3이고 5 6 8 4 는 왼쪽 서브트리, 1 2 7 은 오른쪽 서브트리이다. 양 서브트리의 루트(최상단) 노드는 전위 순회의 첫번째 노드 이므로 각각 6, 7 이다. 루트 노트를 찾았으면 또 이등분하여 서브트리를 구한다. 시작 위치, 끝 위치, 루트 노드의 위치를 받아 재귀하여 구현하였다. public class Main { static int pre[]; static int in[]; public static void main(String[]..

입력값들로 트리를 만들어 후위 순회를 한다. 늑대의 수 - 양의 수가 음수가 될때를 주의해주어야 한다. public class Main { static ArrayList a[]; static char sw[]; static int score[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); a = new ArrayList[n+1]; sw = new char[n+1]; score = new int[n+1]; for(int i=0; i