이분 탐색

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해당 문제는 이분 탐색으로 해결했습니다. 주어진 N만큼 반복문을 시행합니다. arr의 맨 뒤 값보다 현재 주어진 값보다 작을 경우 arr의 맨 뒤에 해당 값으로 업데이트 해줍니다. 그 반대일 경우 이분 탐색으로 주어진 값의 인덱스를 찾아줍니다. 파이썬 풀이 [Python][백준 12015][이분 탐색] 가장 긴 증가하는 부분 수열 2 - 컴도리돌이 풀이 과정 해당 문제는 bisect 라이브러리를 사용해서 해결하였다. bisect에 대해서는 아래 링크를 참조하면 좋..

풀이 과정 해당 문제는 bisect 라이브러리를 사용해서 해결하였다. bisect에 대해서는 아래 링크를 참조하면 좋다. [Python] bisect - 컴도리돌이 알고리즘 문제를 해결하다가 다른 분의 블로그에서 제가 푼 알고리즘 문제를 파이썬에서 제공하는 표준 라이브러리인 bisect를 이용해서 간단하게 문제를 해결한 것을 보고, 요번 기회에 bisect 라 comdolidol-i.tistory.com 1. 입력받은 배열의 0번째 인덱스 값부터 순차적으로 반복문을 시행한다. 2. arr가 비어있으면 x 값을 arr에 insert 한다. 3. 현재 x 값이 arr의 마지막 인덱스 값보다 크면 insert 시킨다. 4. 마지막 인덱스 값보다 크지 않으면 bisect_left 함수를 이용해서 x값보다 같거나..

16161번: 가장 긴 증가하는 팰린드롬 부분수열 팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드 www.acmicpc.net 풀이과정 해당 문제를 푸는데 거의 1시간 반을 써서 해결했다. 🤣🤣 그것도 아이디어가 생각나지 않아서 다른 분의 코드를 확인하면서 해결했다. 이 문제의 핵심은 "투 포인터"로 문제를 해결해야 한다. 1. 기준점 인덱스로부터 증가하는 팰린드롬의 길이를 구해야 한다. 2. 팰린드롬의 길이는 최소 1이 될 수도 있다. 3. start, end라는 배열의 인덱..

6209번: 제자리 멀리뛰기 첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 작은 돌섬의 수 n(0 ≤ n ≤ 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 ≤ m ≤ n)이 공백으로 구분되어 주어진다. 두 www.acmicpc.net 풀이 과정 해당 문제는 저어어어어엉말 어려웠다.. 👏👏 해당 문제의 알고리즘 분류는 이분 탐색으로 표기되어 있었고, 그것은 나에게 도움이 되지 않았다...😂😂 결국 이분 탐색의 target을 바위 간에 거리로 잡아야 하는데, 바위를 제거를 어떤 식으로 구현해야 할지 감이 잡히지 않아서 매우 고생했던 문제였다.. 1. 입력받은 돌섬(rocks)들의 거리를 오름차순 정렬을 하고, 주어진 거리도 rocks에 appen..

16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 풀이 과정 1. 알고리즘 분류로 이분 탐색으로 되었지만 단순 구현으로 풀 수 있다. 하지만 오랜만에 이분 탐색으로 문제를 해결하였다. 2. 보통 이분 탐색에서는 target을 뭐로 정해야하는지 감을 잡기 힘들 때가 많다. 그럴 때는 물어보는 것(HmaxHp)을 target으로 잡아주면 좋다. 아님 말고 😊 3. 필자는 최소 hp 값을 찾기 위하여 hp을 target으로 잡았다. left = 0,..