이분 탐색이란? 이분 탐색은 정렬된 데이터에서 원하는 값을 효율적으로 찾기 위한 검색 알고리즘입니다. 특정 데이터를 찾을 때 O(log n)의 시간 복잡도를 가지므로 빠른 속도로 찾을 수 있습니다. 이분 탐색 작동 원리 데이터의 중간 값과 특정 데이터와 값을 비교한다 중간 값이 특정 데이터 값과 일치하면 종료한다 중간 값이 특정 데이터 값보다 크면, 왼쪽부터 다시 이분 탐색을 한다 중간 값이 특정 데이터 값보다 작으면, 오른쪽부터 다시 이분 탐색을 한다 이분 탐색 활용 검색 정렬된 데이터에서 특정 값을 찾을 때 이분 탐색을 사용합니다. 최적화 최적화 문제에서 이분 탐색을 이용해 가능한 경우의 수를 줄일 수 있습니다.
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 입출력 예시 풀이 HashMap을 사용..
그래프 탐색 그래프 탐색은 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 모든 정점을 한 번씩 탐색하는 것을 의미합니다. 그래프 탐색 방법에는 깊이 우선 탐색(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..
