반응형 알고리즘&코딩테스트/fastcampus - 한 번에 끝내는 코딩테스트 369 Java편2 [알고리즘&코딩테스트] 이분 탐색 (Binary Search) 문제 목차 · 수열에서의 탐색이란? · 이분 탐색이란? - 이분 탐색의 시간 복잡도 - 이분 탐색에서 자주 하는 실수 - 이분 탐색 작동 방식 수열에서의 탐색이란? · 수열과 탐색 대상 X가 주어졌을 때, 다음의 질문을 던지는 것 - X가 존재하는가? - X [이하, 미만, 이상, 초과]의 원소는 몇 개가 있는가? - X와 가장 가까운 원소는 무엇인가? · 아래 그림 처럼 정렬 되지 않은 수열이 주어지면 탐색 속도는 O(N)이다. X = 63 72 19 38 58 10 92 18 11 87 · 아래 그림 처럼 정렬된 수열이 주어지면 이분 탐색으로 더 빠르게 탐색할 수 있다. 10 11 18 19 38 58 72 87 92 이분 탐색이란? · 정렬이 보장된 배열에서 기준 X를 가지고 범위를 이분하면서 탐색하는 .. 2022. 1. 9. [알고리즘&코딩테스트] 완전 탐색(Brute Force) 완전 탐색(Brute Force) · 문제를 해결하기 위해 확인하는 모든 경우를 탐색하는 방법이다 - 정답은 무조건 구하는 치트키 · 백 트래킹을 사용해야 하는 상황을 해결한다. · 모든 코딩테스트 문제에게 기본적으로 접근해 봐야 한다. · 장점: 부분점수를 얻기 좋다. · 단점: 전부 탐색하기 때문에 일반적으로 시간 복잡도가 높다. 코딩테스트에 나오는 완전 탐색 문제 종류 · 4가지: (중복없이 or 중복을 허용해서) N개 중 M개를 (고르기 or 순서 있게 나열하기) · 완전 탐색은 함수 정의가 50% // Recurrence Function (재귀 함수) // 만약 M 개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것! // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건.. 2022. 1. 4. 이전 1 다음 반응형
