# Binary Search
Leetcode - 74. Search a 2D Matrix
주어진 2차원배열에서 target값이 존재하는지 확인하라. 각 row/column은 오름차순 정렬되어있다.
Leetcode - 704. Binary Search
주어진 배열중 target에 해당하는 값의 index를 리턴match와 Ordering으로 구현한점이 흥미로움.
백준 2776 암기왕
연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으
백준 4454 상근이의 여자친구
상근이는 여자친구를 데리러 가야 한다. 상근이의 차에는 기름이 t만큼 있고, 여자친구는 상근이가 현재 있는 위치와 m킬로미터 떨어져 있다.상근이는 여자친구를 최대한 빨리 데리러 가야 하기 때문에, 중간에 주유소에 들릴 시간이 없다. 어렸을 때부터 물리, 수학 영재로 전
프로그래머스 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사
프로그래머스 H-Index
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고
이분 탐색 이진 탐색 Binary Search
탐색 알고리즘 저장된 데이터들 중에 원하는 값을 찾는 알고리즘 대표적으로 아래와 같은 알고리즘들이 있다. 선형 탐색 알고리즘 (Linear Search Algorithm) 이진 탐색 알고리즘 (Binary Search Algorithm) 해시 탐색 알고리즘 (Has
내일배움캠프 - 알고리즘 2주차 개발일지
크기가 정해진 데이터각 원소에 즉시 접근 가능 ($O(1)$)삽입, 삭제 어려움 ($O(N)$)새로운 원소 추가시 새로운 공간을 할당해야되서 비효율적크기가 정해지지않은 데이터원소에 접근하기 위해서는 순차탐색 필요 ($O(N)$)삽입, 삭제, 추가 용이 ($O(1)$):
Leetcode - 240. Search a 2D Matrix II
행과 열이 모두 오름차순 정렬된 MxN크기의 matrix가있다. target값이 존재하면 true 없으면 false를 리턴.binary search를 행과 열 모두 할필요가 없고, 행을 순회하면서만 함. 추가 개선 포인트로, 모든 행을 탐색할필요가 없음. target이
[Algorithms][STL] C++ lower_bound, upper_bound
이진 탐색 (binary search) 기반의 탐색 방법입니다. (단, 배열 또는 리스트가 오름차순으로 정렬되어있어야 합니다.)찾으려는 key값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함입니다. (인덱스를 반환)lower_bound의 반환형은 i
baekjoon 18870
https://www.acmicpc.net/problem/18870우선 좌표압축이란 말을 제대로 이해해야 한다. 참고 : https://medium.com/algorithms-digest/coordinate-compression-2fff95326fb대
검색, 탐색 : Algorithm
선형 검색무작위로 늘어놓은 데이터 모임에서 검색이진 탐색일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색해시법추가 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행체인법 - 같은 해시 값의 데이터를 선형 리스트로 연결오픈 주소법 - 데이터를 위한 해시 값이
[Silver IV] Sort 마스터 배지훈의 후계자 - 20551
문제 링크메모리: 90808 KB, 시간: 3120 ms이분 탐색(binary_search), 자료 구조(data_structures), 정렬(sorting), 트리를 사용한 집합과 맵(tree_set)지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온
[Day7/15] LeetCode 75
어느덧 LeetCode 75 Level 1 을 시작한지 7일차다! 이제 반 정도 한거다 :)오늘의 주제는 어제와 마찬가지로 Binary Search 다.Binary Search 은 보통 문제에서 주어진 값 중 무엇을 찾아야하며 제한사항에 값이 좀 많다 싶을 때 쓴다.
[Silver V] 제곱근 - 13706 - Kotlin
문제 링크메모리: 22824 KB, 시간: 272 ms임의 정밀도 / 큰 수 연산(arbitrary_precision), 이분 탐색(binary_search), 수학(math)정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오.첫째 줄에 양의 정수 N이
[Silver IV] 수 찾기 - 1920 - Kotlin
문제 링크메모리: 91776 KB, 시간: 2012 ms이분 탐색(binary_search), 자료 구조(data_structures), 해시를 사용한 집합과 맵(hash_set)N개의 정수 A1, A2, …, AN이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지
Leetcode - 34. Find First and Last Position of Element in Sorted Array
중복된 값이 있는 정렬된 배열이 있을때, target값이 존재하는 범위를 리턴하라. 없다면 -1,-1을 리턴.단, 시간복잡도는 O(log N)을 초과할 수 없다.Leetcode 에서 200번째로 해결한 문제이다. 딱 두달전 5/9에 100개를 돌파했는데, 속도가 붙어서
Leetcode - 33. Search in Rotated Sorted Array
값이 정렬되어있는 배열이 있다. 그런데 특정 pivot 인덱스를 기준으로 회전되어있다. 이런 배열에서 target값의 index를 찾아라. 단 시간복잡도는 O(logN)을 초과할 수 없다.https://leetcode.com/problems/search-in-