DevBoi

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 쉽게 생각할수 있는 이분탐색 풀이이다. 이분탐색의 유형은 크게 두가지 풀이이다. 특정 배열이 있고, 해당 배열 내에서, 이분탐색으로 중간값을 구해서 값을 탐색하는 방법이 있고 특정 조건에 대한 리스트들을 생각해서, 만든뒤에 해당 조건들의 범위에서 이분탐색을 하는 경우가 있다. 해당 문제는 두번째 케이스이다. 각 레슨의 길이를 생각해서 최대의 길이를 계산, 그리고 cnt 를 증가 시키면서 세는 방법이다. ..

이분탐색 ? 정렬이 보장되어있는 배열에서, 이분을 하면서 탐색하는기법 이분탐색은 전형적인 변수 세팅을 사용한다. 왼쪽, 오른쪽의 포인터 두개를 가지고 시작한다. 항상 가운데의 인덱스를 보고, 해당 인덱스와 , 타겟을 비교하고, 해당 비교를 통해 포인터 L 혹은 R을 비교하면서 포인터를 이동시킨다. https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 이분탐색에 대한 예제이다. 쉽게말하면, 한 집합을..

이진탐색에 대한 공부를 시작한다. 이진탐색을 왜쓸까? 일단 이것부터 파악을 해야한다. 사실 순차 탐색 = 이진탐색 값을 구하는 건 동일하다. 결국 둘다 탐색을 해서 답을 도출해내는 건 동일하게 성공적으로 실행된다. 근데, 탐색해야되는 량이 엄청 많다면? 그때는 이진탐색을 실행한다. 우선 이진탐색에 대한 기초적인 구현을 시작한다. 아주 간단하게, 5개의 숫자를 입력받고, 그중에 target인 15를 찾는것이다. mid를 시작과 끝점을 합한 /2 를 하고, 만약의 mid index가 타겟보다 크면, 최고를 mid -1 로 이동 반대라면 low를 mid +1로하게된다. 물론 이 것은 입력값이 순차적은 정렬 형태를 띈다는 가정이다. 이렇게 되면 순차 탐색 보다 훨씩 빠른 탐색을 할수있다. 탐색 대상이 많은 경우..