eivomin eivomin

1. 중간 인덱스를 구한다. 2. 중간값과 key값을 비교한다. 3. 비교값에 따라 범위를 왼쪽, 오른쪽 혹은 값이 같은 경우는 해당 인덱스를 반환한다. public static int binarySearch(int[] arr, int key){ int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스 int hi = arr.length-1; // 탐색 범위의 오른쪽 끝 인덱스 // lo가 hi보다 커지기 전까지 반복한다. while (lo arr[mid]){ lo = mid+1; } // key값과 중간 위치의 값이 같을 경우 else{ return mid; } } // 찾고자 하는 값이 존재하지 않을 경우 return -1; } + Arrays.binarySearch(int[]a, int key) 해당..

package Algorithm; import java.util.*; public class dfs { static class Pair{ int x, y; public Pair(int x, int y){ this.x = x; this.y = y; } } public static void main(String[] args) { int[][] board = new int[502][502]; // 1이 파란 칸, 0이 빨간 칸에 대응 int[][] visited = new int[502][502]; // 해당 칸을 방문했는지 여부를 저장 int N = 7; // 행의 수 int M = 10; // 열의 수 int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; Stack ..

package Algorithm; import java.util.*; public class bfs { static class Pair{ int x; int y; public Pair(int x, int y){ this.x = x; this.y = y; } } public static void main(String[] args) { /* {1,1,1,0,1,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0}, {1,1,1,0,1,0,0,0,0,0}, {1,1,0,0,1,0,0,0,0,0}, {0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0} 1이 파란 칸, 0이 빨간 칸에 대응 */ int[][] board = new int[..

부분집합 한 집합의 원소들로만 구성한 집합. 공집합은 모든 집합의 부분집합이며, 모든 집합은 자기 자신의 부분집합이다. https://ko.wikipedia.org/wiki/%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9 부분집합 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 부분집합 관계를 표현한 벤 다이어그램. A는 B의 부분집합이다. 집합론에서 집합 B의 부분집합(部分集合, 영어: subset) A는, 모든 원소가 B에도 속하는 집합이다. ko.wikipedia.org 구현 package Algorithm; public class 부분집합 { static int[] arr = {1,2,3,4}; static int[] res = new int[4]; publ..

중복 조합 조합과 마찬가지로 n개의 원소에서 r개를 순서에 상관없이 뽑는데, 중복을 허락할 때의 가짓수이다. 구현 package Algorithm; import java.util.Arrays; public class 중복조합 { static int[] arr = {1,2,3,4}; static int[] sel = new int[2]; public static void main(String[] args) { combination(0,0); } private static void combination(int idx, int s_idx){ if(s_idx == sel.length){ System.out.println(Arrays.toString(sel)); return; } for(int i=idx; i

조합 조합이란 n개의 원소를 갖는 집합에서 r개의 원소를 선택하는 것 혹은 선택의 결과로 정의된다. 어떤 순서로 원소를 선택했는지는 중요하지 않기에 순열과는 다른 개념이다. 구현 package Algorithm; import java.util.Arrays; public class 조합 { static int[] arr = {1,2,3,4}; static int[] sel = new int[2]; public static void main(String[] args) { combination(0,0); } private static void combination(int idx, int s_idx){ if(s_idx == sel.length){ System.out.println(Arrays.toString(s..

중복순열 중복 순열은 순열과 마찬가지로 n개 중에 r개를 순서에 상관 있게 뽑는데, 중복을 허락하여 뽑는 것을 말한다. 구현 순열 코드에서 visited 체크 안 하면 중복순열! package Algorithm; import java.util.Arrays; public class 중복순열 { static int[] arr = {1,2,3}; static int[] res = new int[3]; public static void main(String[] args) { perm(0); } private static void perm(int idx){ if(idx == arr.length){ //출력 System.out.println(Arrays.toString(res)); return; } for(int ..

순열 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 혹은 나열하는 것을 순열(permutation)이라고 한다. 구현 package Algorithm; import java.util.Arrays; public class Permutation { static int[] arr = {1,2,3}; static int[] res = new int[3]; static boolean[] visited = new boolean[3]; public static void main(String[] args) { perm(0); } private static void perm(int idx){ if(idx == arr.length){ System.out.println(Arrays.toString(res)); ..