이진탐색

    백준 1654: 랜선자르기 해설- python
    프로그래밍/백준

    백준 1654: 랜선자르기 해설- python

    ✏️ 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ✏️ 풀이 이진탐색을 이용하는 문제다. 이진탐색에 대한 내용은 여기에서 랜선의 길이에 대해서 이진탐색을 시행한다. k,n= map(int, input().split()) line = [] for _ in range(k): line.append(int(input())) start = 1 end = max(line) while(start=n: start=mid+..

    [알고리즘] Lower Bound와 Upper Bound
    프로그래밍/자료구조 & 알고리즘

    [알고리즘] Lower Bound와 Upper Bound

    ✏️ 무엇인가? Lower Bound와 Upper Bound는 모두 경계값을 찾는 과정이다. 이진탐색(Binary Search)가 '원하는 값을 찾는 과정' 이었다면 Lower Bound는 '원하는 값이 처음 나오는 위치'를 찾는 과정이고, Upper Bound는 '원하는 값이 나오는 마지막 위치를 찾는 과정'이다. Array = [1, 1, 2, 2, 3, 4, 4, 4, 6] 이런 리스트가 있에서 Lower Bound로 4를 찾는다면 4가 처음 나오는 인덱스인 5가 Output이 될 것이고, Upper Bound로 찾는다면 4가 마지막으로 나오는 인덱스인 7이 Output이 될 것이다. ✏️ 구현과정의 고민 사실 선형 탐색으로 구현하면 바로 해결되지만 기왕이면 O(N)보다는 O(lgN)이 좋지 않겠나..

    백준 10816: 숫자카드 2 해설- python
    프로그래밍/백준

    백준 10816: 숫자카드 2 해설- python

    ✏️ 문제 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 풀이 아래는 10815에서 만들어쓴 이진탐색 함수이다. def BS(array, target, start, end): if start > end: return 0 mid=(start+end)//2 if array[mid]==target: return 1 elif array[mid]>target: return BS(array, target, start, mid-1) else: return BS(array, targe..

    백준 10815: 숫자카드 해설- python
    프로그래밍/백준

    백준 10815: 숫자카드 해설- python

    ✏️ 문제 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 풀이 1920 수찾기 문제와 완전하게 동일한 문제였다. 해당 문제의 해설과 이진탐색에 대한 설명은 여기를 참고 (Python) N=int(input()) card=list(map(int,input().split())) card=sorted(card) M=int(input()) target_list=list(map(int,input().split())) def BS(array, target, start, end): if..

    Binary Search (이진탐색) 알고리즘
    프로그래밍/자료구조 & 알고리즘

    Binary Search (이진탐색) 알고리즘

    ✏️ 이진탐색알고리즘의 작동방식 이진탐색은 정렬된 리스트에서 특정 요소를 찾는 알고리즘이다. 분할(Devide) 리스트를 중간값을 기준으로 두개의 리스트로 분할한다. 정복(Conquer) - 검색할 숫자 중간값 이면 중간값 뒤의 리스트에서 검색할 요소를 찾는다. - 검색할 숫자 == 중간값 이면 값을 리턴한다. ✏️ 이진탐색알고리즘 구현 (Python) 재귀적 구현 def BS(array, target, start, end): if start>end: return None mid=(start+end)//2 if array[mid]==target: return mid elif array[mid]>target: return B..

    백준 12015: 가장 긴 증가하는 부분 수열 2- python
    카테고리 없음

    백준 12015: 가장 긴 증가하는 부분 수열 2- python

    ✏️ 문제 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ✏️ 풀이 11053 가장 긴 증가하는 부분 수열 1과 뭐가 다를까? 다른 것은 단 하나. N의 조건 범위이다. 11053에서는 1

티스토리툴바