# binary_search
이진탐색(재귀)
정렬된 리스트와 찾고자 하는 숫자 리스트가 입력되었을 때, 찾고자 하는 숫자가 각각 리스트에서 몇 번째에 위치한 숫자인지 출력하는 프로그램을 작성하세요.Hint리스트의 각 원소를 한 줄에 출력하기 위해서는 다음과 같이 실행하면 됩니다.l = 1,2,3,4print(\*
최장 공통 부분 수열 LCS
참고 링크LCS(Longest Common Subsequence)는 주로 최장 공통 부분수열을 나타내지만 최장 공통 문자열을 말하기도 한다. 최장 공통 문자열은 반드시 부분 문자열이 연결된 형태여야 한다. banana, vbankn최장 공통 부분 수열은 떨어져 있어도
[c/c++] 백준 1764(Silver 4)
https://www.acmicpc.net/problem/1764김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이
[c/c++] 백준 1269(Silver 4)
https://www.acmicpc.net/problem/1269자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의
[python] 이분 탐색(Binary Search)_백준10815번, 10816
첫번째 솔루션은 간단하게 두 배열을 생성한 후,있는지 없는지 체크하는 로직이었다.배열의 크기가 너무 커지면, time limit 에 걸리는 문제가 발생한다. 그래서 순차 탐색이 아닌 이분 탐색의 방법으로 풀어야 한다.
[Python] 이진/이분 탐색(Binary Search)
오름차순으로 정렬된 배열에서 찾고자 하는 수(target)를 두 부분으로 나눠서 찾는 알고리즘 기법순차 탐색(Linear Search)보다 더 빠른 성능을 보인다.탐색 리스트가 정렬되어 있지 않으면 정렬left(리스트 첫번째), right(리스트 마지막), mid(리스
백준 10815 [c++] 숫자 카드
c++에서는 binary search를 직접 구현하지 않아도 된다. binary_search() 함수 사용법을 알아보자. 아래 사진은 binary_search() 함수의 정의이며 3개의 매개변수에 맞는 인수들을 넣어 주면 된다. 벡터에서 원하는값 x를 찾아주고 싶으
Softeer - 인사고과
인사고과 : https://softeer.ai/practice/info.do?idx=1&eid=630문제를 처음 보았을때 각 난이도에 하나씩 값을 넣어보는 완전탐색밖에 생각이 나지 않았습니다. 하지만 제약조건에서 ci, di가 10^12인것을 보고 완전탐색은
백준 2343 기타 레슨
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번
백준 1253 좋다
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.수의 위치가 다르면 값이 같아도 다른 수이다.O(N^2 \* log N)으로 가능하다. 0번
백준 2470 두 용액
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터
[알고리즘] 이진 탐색(Binary Search)
이진 탐색이란 데이터가 반드시 정렬되어 있는 상태에서 특정한 값을 찾아내는 알고리즘입니다.정렬된 배열에서 x값을 찾고자 할 때정렬된 배열의 중간값과 x를 비교하고 일치한다면 해당 인덱스 값을 반환하고 일치하지 않다면 2번과정으로 넘어갑니다.중간값과 같으면 해당 값을 반
[Java] 정렬된 리스트에서 근사값 구하기
회사에서 마우스 좌표를 기준으로 X값을 받아와 차트 그려진 그래프의 Y값을 도출하는 기능을 구현해야 하는 경우가 생겼다. 문제는 받아오는 X의 값은 연속적인 값인데, 도출해야하는 Y좌표를 담고 있는 데이터는 <key(x좌표), value> 형식이라 마우스 좌표의
이진탐색(Binary Search) [TIL / 알고리즘]
algorithm banner이진탐색, 알고리즘을 공부하면서 한 번은 거쳐가야 하는 관문이다.이진탐색은 배열에 찾고자 하는 값이 있는지 빠르게 찾을 수 있다. 어떻게 이를 가능하게 하는지 살펴보도록 하겠다.base priciple이진탐색은 우선 오름차순이든 내림차순이든
백준2805
이진탐색으로 접근하는 문제이다. 처음 생각한 접근 방법은 예제를 입력받은 부분을 소팅한다음 이진탐색을 실행하려 했지만시간 제한 때문에 이 방법이 불가능할 것이라 생각했다.따라서 새로운 접근법이 필요했다.나무를 자를 때, 최대 값만 알고 있다면 중간 값을 구할 수 있기
