이분 탐색이란? 이분 탐색은 정렬된 데이터에서 원하는 값을 효율적으로 찾기 위한 검색 알고리즘입니다. 특정 데이터를 찾을 때 O(log n)의 시간 복잡도를 가지므로 빠른 속도로 찾을 수 있습니다. 이분 탐색 작동 원리 데이터의 중간 값과 특정 데이터와 값을 비교한다 중간 값이 특정 데이터 값과 일치하면 종료한다 중간 값이 특정 데이터 값보다 크면, 왼쪽부터 다시 이분 탐색을 한다 중간 값이 특정 데이터 값보다 작으면, 오른쪽부터 다시 이분 탐색을 한다 이분 탐색 활용 검색 정렬된 데이터에서 특정 값을 찾을 때 이분 탐색을 사용합니다. 최적화 최적화 문제에서 이분 탐색을 이용해 가능한 경우의 수를 줄일 수 있습니다.
그래프 탐색 그래프 탐색은 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 모든 정점을 한 번씩 탐색하는 것을 의미합니다. 그래프 탐색 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)이 있습니다. 시간 복잡도 : 인접 행렬(O(V^2)), 인접 리스트(O(V+E)) V : 접점, E : 간선 DFS DFS는 시작점에서 시작하여 해당 분기를 모두 탐색 후 다음 분기로 넘어가는 탐색 방법입니다. 모든 경로를 탐색할 때 DFS를 사용한다. 검색 속도는 BFS에 비해 느리다. 메모리 효율은 인접리스트가 인접 행렬에 비해 좋지만 속도는 인접 행렬이 빠르다. 스택 또는 재귀를 이용하여 구현한다. BFS BFS는 시작점에서 가까운 점들을 우선적으로 탐색하는 방법입니다. 두 노드..
조합 조합은 서로 다른 n개에서 순서 없이 r개의 숫자를 뽑는 경우의 수를 의미한다. static int K; static int[] arr; static boolean[] visited; // 조합 public static void main(String[] args) { arr = new int[]{1, 2, 3}; K = 2; // 뽑는 개수 visited = new boolean[arr.length]; //배열의 개수만큼 초기화 combination(0, 0); } public static void combination(int idx, int cnt) { if (cnt == K) { for(int i = 0; i < arr.length; i++) { if(visited[i]) System.out.p..
순열 순열은 서로 다른 n개의 값 중에서 r개의 숫자를 뽑는 경우의 수를 의미한다. static int K; static int[] arr, result; static boolean[] visited; // 순열 public static void main(String[] args) { arr = new int[]{1, 2, 3}; K = 2; // 뽑는 개수 result = new int[K]; visited = new boolean[arr.length]; //배열의 개수만큼 초기화 permutation(0); } public static void permutation(int cnt) { if (cnt == K) { System.out.println(Arrays.toString(result)); retu..
