[Python] 백준 알고리즘 2805번 : 나무 자르기
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 👩💻문제 이해 항상 그렇듯 이분탐색 알고리즘에서는 무엇을 변수로 둘지와 조건을 어떻게 줄지가 가장 중요하다. (조건) 위 문제에서는 가지고 가려 하는 나무의 길이가 M으로 정해져 있기 때문에 이걸 조건으로 두면 된다. 즉, 주어진 배열 각각의 원소들을 구하고자 하는 값(target)으로 뺀 값의 합이 M이 되는 것이 조건이다. 그리고 이 때 절단기 높이의 ..
[Python] 백준 알고리즘 2776번 : 암기왕
https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 👩💻문제 이해 이해하기에 어려운 문제는 아니다. N개의 정수가 주어진 '수첩1'의 배열을 정렬한 후 '수첩2'에 들어있는 각각의 정수들을 이분탐색 알고리즘으로 '수첩1'에도 있는지 없는지를 판단하면 된다. 👩💻반복문을 사용해 이분탐색 알고리즘 구현 (함수 별도 구현) : 성공🌈 def binary(arr, target): start = 0 end = len(arr) - 1 while start
[Algorithm] 이분 탐색 / 이진 탐색 (Binary Search) 알고리즘
🌵이분 탐색(Binary Search) 이란? - 정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 원하는 값(target)을 탐색하는 방법 - 이 때 리스트(배열)는 항상 정렬되어 있어야 한다 시간 복잡도 : O(log n) 🌵문제 해결 방법 이분 탐색 알고리즘은 변수 3개 (start, mid, end)를 사용해 값을 탐색 간단하게 말하면 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이분 탐색의 과정 변수 이름에서도 알 수 있듯, start의 초기 값은 리스트(배열) 시작 위치 (0) mid 는 start와 end의 중간 지점 ((start + end) // 2) end 는 리스트(배열) 마지막 위치 (len(list) - 1) 1. 리스트(..