helloahram

1. 문제나무의 수 n, 필요한 길이 m, 나무들의 높이 배열이 주어졌을 때,최소 m 미터를 가지고 가기 위해 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램 2. 알고리즘 분류* 이분 탐색* 매개 변수 탐색  3. 접근 방식매개 변수 탐색와 이분 탐색을 통해서 접근했다수 찾기 문제에서는 x == A[mid] 로 특정 숫자의 존재 여부를 확인했지만 나무 자르기 문제에서는 gets >= m 을 기준으로 필요한 최소 길이를 얻을 수 있는지 확인했다  4. 전체 코드 # 나무의 수 n, 필요한 길이 m, 나무들의 높이 배열이 주어졌을 때 # 적어도 m 미터를 가지고 가기 위해 절단기의 최대 높이를 구하는 문제n, m = map(int, input().split())trees = list(map(int..

2805 나무 자르기 문제에서 매개 변수 탐색을 이용해서 풀었기에 정리해본다 매개 변수 탐색 Parametric Search최적화 문제를 결정 문제로 풀 수 있는 알고리즘으로,조건을 만족하는 최소값 또는 최대값을 찾는 방법  * 최적화 문제 - 어떤 알고리즘의 최적 솔루션을 찾는 문제 * 결정 문제 - 답이 이미 결정되어 있다고 보고 문제를 푸는 방식  이분 탐색과의 차이점이분 탐색 공부 자료 이분 탐색은 배열에서 Target 과 일치하는 값을 찾으면 바로 함수를 종료한다반면, 매개 변수 탐색은 함수를 종료하지 않고 모든 배열을 탐색하며조건을 만족하는 가장 크거나 작은 값을 찾는다 1. 어떤 시점까지 조건을 만족하지만 그 후로 만족하지 않는 경우, 조건을 만족하는 최대값 찾기 2. 어떤 시점까지 조건을 ..

1920 수 찾기 문제를 풀다가 이분 탐색이 분류에 있길래 정리해본다 이분 탐색 Binary Search 정렬되어 있는 리스트 또는 배열에서 탐색 범위를 절반씩 좁혀가며원하는 값 Target 의 존재 위치/ 존재 여부를 찾는 알고리즘  이분 탐색 특징 단계마다 탐색 범위를 반으로 나누기 때문에 시간 복잡도는 O(logN) 이다 단, 배열이 정렬되어 있어야만 사용 가능하다는 단점이 있다  Quick Sort 와 유사한 접근 방법을 사용해서, Pivot 대신 mid 값을 계산하여left 로 탐색 범위의 왼쪽 경계, right 로 탐색 범위의 오른쪽 경계를 설정하고찾는 대상과 mid 값을 비교하여 left, right, mid 값을 변경하며 범위를 줄인다 * Quick Sort 공부 자료 이분 탐색 코드백준 ..

1. 문제 n 개의 정수 a[] 와 m 개의 정수 arr[] 가 주어졌을 때,arr[] 의 각 정수 X 가 a[] 안에 존재하는지 찾는 프로그램 2. 알고리즘 분류* 자료 구조 * 정렬 * 이분 탐색 * 해시를 사용한 집합과 맵  3. 접근 방식얼마 전에 ㅅㅎ님과 스터디하면서 같이 공부했던 이분 탐색과Quick Sort, Merge Sort 에서 배운 left, right 를 활용해 보기로 했다이분 탐색을 진행하기 전에 순서 정렬 먼저 하기! sort() sorted() 공부 자료 https://helloahram.tistory.com/entry/TIL-sorted 4. 전체 코드# m 개의 정수 X 가 n 개의 정수 a [] 안에 존재하는지 찾는 프로그램 # n, a, m, arr 입력 받기 N = ..