Development Palette

- 가운데에 있는 값과 찾는 키를 비교하고 다음 구간을 결정하고, 그 구간을 또 반으로 나누어 키 비교를 반복하는 검색방법을 통해 원하는 키를 찾는 것 - 이진 검색을 하기 위한 수행 조건은 정렬된 상태 - 시간복잡도 : log2의 N승 - 이진검색은 문제를 풀 때 이진검색의 아이디어를 접목하여 사용하기 때문에 스스로 구현할 줄 알아야함! package com.ssafy.w0817; import java.util.Arrays; public class BinarySearchTest { public static void main(String[] args) { int[] arr = {10,4,6,20,35,7}; Arrays.sort(arr); // 값들을 오름차순 정렬 // 4,6,7,10,20,35 Sys..

반으로 나누어 각각 해결하고 또 나누어 해결하는 식을 반복하여 마지막에 통합하여 해답을 찾는다. package com.ssafy.w0817; import java.util.Scanner; //분할 정복 알고리즘과 재귀 비교 //호출횟수만 비교하기 위해 코딩한 것(값의 오버플로우 생각하지 않고) //분할정복이 월등히 적은 횟수 public class SquareNumber_분할정복 { //재귀 static int callCnt; static long exp1(long x,long y) { callCnt++; if(y==1) return x; return x *exp1(x, y-1); } // 분할정복 static long exp2(long x,long y) { callCnt++; if(y==1) retur..

완전검색(브루트포스)를 사용했을 때 n>=30일 경우 너무 많은 시간을 소비하기 때문에 그리디 알고리즘(내가 생각하는 최적의 해)를 구하기 위해 효율적인 방법으로 접근 단, 최적의 해를 반드시 구한다는 보장이 없을 수 있다. package com.ssafy.w0817; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; //Greedy, 탐욕 알고리즘 public class MeetingRoomTest_Greedy { static class Meeting implements Comparable { // 미팅객체들을 비교하며 판단하기 위해 Comparable 사용 // Comparable : 원소 스스로가 다른 원소랑..

지그재그 우선탐색 int[][] arr = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16} }; int R = arr.length; int C = arr[0].length; // 지그재그 우선탐색 for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { int temp = (i%2==0)?j:C-1-j; System.out.print(arr[i][temp]+" "); } System.out.println(); } 짝수 index일때는 arr[i][j]그대로 이지만, 홀수 index일 때는 시작점이 달라지므로 arr[i][temp]로 temp값을 이용해 열을 바꿔주면 된다. int temp = (i%2==0)?j..

아래의 코드들은 암기해야 한다고 생각할 정도로 숙지하고 있어야 한다. 순열, 조합, 부분집합은 브루트포스(완전탐색)와 매우 연관이 깊다 순열 (Permutation) 순서의 의미가 있다. 선택했던 것을 확인해주는 boolean 타입의 isSelected 배열 package com.ssafy.w0803.p; import java.util.Arrays; /** * @author THKim */ // N개의 서로 다른 수에서 뽑는 순열 public class PermutationTest2 { static int N=3,R=2; static int[] input; static int[] numbers; static boolean[] isSelected; public static void main(String[]..