# 이진탐색

62개의 포스트

[Algorithm] Lower Bound & Upper Bound

Lower Bound & Upper Bound 하한선 알고리즘, 배열에서 특정한 값을 찾는 알고리즘은 이분 탐색(Binary Search)을 응용한 알고리즘으로, 정렬되어있는 배열에서 target이상의 값이 처음 나오는 위치를 찾는 알고리즘 이다. 반대되는 개념으로 U

2021년 5월 4일
·
0개의 댓글
post-thumbnail

[Kakao] 징검다리 건너기

이진탐색

2021년 5월 3일
·
0개의 댓글

2019 카카오 인턴십 Q5

풀이 코드문제를 보자마자 단순히 떠올린 생각은 모든 배열 요소를 1씩 감소시키면서 확인해 나가는 방법이었다. 하지만 배열의 크기 범위를 확인하면 이 완전탐색 적인 방식은 해결이 되지 않을 것 같았다. 당연히 DFS도 안 될 것이고, 그렇다면 다이나믹 프로그래밍은 어떤가

2021년 5월 2일
·
0개의 댓글
post-thumbnail

[Programmers] 1. 기본 자료구조: 배열(리스트), 기초 알고리즘: 정렬, 탐색, 재귀

자료구조 (Data Structures)와 알고리즘 (Algorithm)은 왜 알아야 하는가? 자료구조 1. 배열 (Array, List) 정렬과 탐색 그리고 재귀

2021년 4월 28일
·
0개의 댓글

백준 온라인 저지 1654: 랜선 자르기

이 문제를 푸느라 시간도 너무 오래 걸렸고 멘탈도 나갔는데(!) 일단 맞았다고 떴으니 됐지 않나 생각한다.https://www.acmicpc.net/problem/1654우선 문제를 이해하도록 해보자.첫째줄 입력값은 가지고 있는 랜선의 개수 K, 필요한 랜선의

2021년 4월 22일
·
0개의 댓글

[JS] Q27 정렬된 배열에서 특정 수의 개수 구하기

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.단, 이

2021년 4월 20일
·
0개의 댓글

[JS] 이진 탐색

배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.이진 탐색은 위치를 나타

2021년 4월 15일
·
0개의 댓글

[백준/2110] 공유기 설치(Java)

백준 2110 공유기설치 Java 이진탐색

2021년 4월 2일
·
0개의 댓글

[알고리즘] 백준 > #2343. 기타 레슨

문제링크 백준 #2343. 기타 레슨 풀이방법 전에 풀었던 이진탐색문제와 아주 비슷하게 생겨서 보자마자 이진탐색을 이용하면 되겠다고 생각했다. 즉, begin, end 값을 최초에 설정해두고 툭툭 값을 던져보면서 그 범위를 반으로 나눠나가는 방식을 이용했다. N과 레슨

2021년 4월 1일
·
0개의 댓글

"입국심사" 문제 풀이

이번 문제는 이진탐색 알고리즘을 사용해야 하는 것을 알았음에도 불구하고 애를 먹은 문제다. 이진탐색 알고리즘 자체는 간단해서 어렵지 않았지만, 문제는 어떻게 어떤 방식으로 적용시켜야 하는지 감이 잡히질 않았다.데이터들의 크기가 커서 일반적인 방식으로 접근하면 시간초과가

2021년 3월 31일
·
0개의 댓글

[Python] bisect 활용해 범위 탐색하기

위와 같은 리스트가 있을 때 2의 개수를 세고 싶다면위 코드 처럼 count 메소드를 사용하면 된다시간복잡도는 O(n)이다 리스트의 길이가 억단위로 넘어가게 되면 시간복잡도 측면에서 불리할 수 있다파이썬에서 제공하는 bisect를 사용해보자bisect_right, bi

2021년 3월 30일
·
0개의 댓글

떡볶이 떡 만들기 문제

오늘은 이것이 취업을 위한 코딩테스트다 교재 201페이지에 수록된 떡볶이 떡 만들기 문제 해결을 기록해 보려고 한다. 문제는 교재 201페이지를 참고하자.떡의 각 길이 19 15 10 17이 주어졌다고 하고 절단 높이는 h라고 하자. 얻을 수 있는 떡의 길이는(19-h

2021년 3월 26일
·
0개의 댓글
post-thumbnail

백준 - K번째 수 [11004]

백준 - K번째 수 [11004]

2021년 3월 25일
·
0개의 댓글
post-thumbnail

백준 - 숫자 카드 [10815]

백준 - 숫자 카드 [10815]

2021년 3월 25일
·
0개의 댓글

백준 1939번 - 중량제한(★★★ / ▲▲ / 2) : Python

풀이 시간 : 30~40분시간 제한 : 1초메모리 제한 : 128 MB기출 : backjoon링크 : https://www.acmicpc.net/problem/1939N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리

2021년 3월 23일
·
0개의 댓글

프로그래머스 - 가장 긴 팰린드롬

https://programmers.co.kr/learn/courses/30/lessons/12904팰린드롬은 앞뒤가 뒤집혀도 똑같은 문자열을 말합니다.따라서 "aa" "aba" 와 같은 문자를 팰린드롬이라 합니다.특정 문자열이 주어졌을때 이 문자열이 팰린드롬

2021년 3월 12일
·
0개의 댓글
post-thumbnail

TIL #09 - 3.09

Sort 함수: Sorted 혹은 a.sorted를 활용하여 리스트를 정렬하는 방식Default값은 오름차순 형식으로 반환내림차순으로 값을 보고싶은 경우는 a.sort(reverse = True) or sorted(a, reverse = True)해주면 된다.또한, l

2021년 3월 10일
·
0개의 댓글

[알고리즘] 선형탐색과 이진탐색

저장된 정보들 중에서 원하는 값을 찾는 것찾고자 하는 값을 리스트의 맨 앞에서부터 끝까지 차례대로 찾아 나가는 방식장점: 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있음단점: 검색할 리스트의 길이가 길면 비효율적예 실행결과0None2

2021년 2월 21일
·
0개의 댓글