binary search
-
코딩 테스트 - 이진 탐색(Binary Search)의 개념과 문제Coding Test/Coding Test 문제 추천 2021. 9. 26. 11:44
이진 탐색(Binary Search) 이진 탐색이란? ㆍ 데이터가 오름차순으로 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. ㆍ 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 x와 비교한다. ㆍ x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 x가 중간값보다 크면 배열의 우측 데이터를 대상으로 다시 탐색한다. ㆍ 동일한 방법으로 다시 중간의 값을 임의로 선택하고, 해당 값을 찾을 때까지 위 과정을 반복한다. 이진 탐색 문제 난이도(하) ㆍ 백준 7795번 : 먹을 것인가 먹힐 것인가 (🥈 실버 3 티어) ㆍ 백준 1920번 : 수 찾기 (🥈 실버 4 티어) ㆍ 백준 1764번 : 듣보잡 (🥈 실버 4 티어) ㆍ 백준 3273번 : 두 수의 합 (🥈 실버 4 티어) ㆍ..
-
배열을 이용한 이진 검색Computer Science/Data Structure 2021. 9. 24. 12:20
Symbol Table 이란? ㆍ (키, 값) 쌍이 모인 자료구조 ㆍ 특정 키와 그 키에 해당되는 값의 쌍을 삽입할 수 있다. ㆍ 키가 주어질 때, 관련된 값을 검색할 수 있다. 배열을 이용한 Symbol Table의 동작 방법 구현 방법 Symbol Table의 기본 구성 public class BinarySearchST { private static final int INIT_CAPACITY = 10; private K[] keys; private V[] values; private int N; } ㆍ 키를 저장하는 배열 K[ ], 값을 저장하는 배열 V[ ]가 있다. ㆍ (키, 값) 쌍의 개수에 대한 변수인 N이 있다. search() 메서드 private int search(K key) { int..