본문 바로가기
반응형

파이썬 이진 탐색4

[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미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱.. 2022. 11. 3.
[Python] 백준 1920번 - 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에.. 2022. 10. 20.
[Python][이코테] 부품 찾기 입력 조건 첫째 줄에 정수 N이 주어진. (1 ≤ N ≤ 1,000,000) 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000이하이다. 셋째 줄에는 정수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000이하이다. 출력 조건 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다. 입력 예시 5 8 3 7 9 2 3 5 7 9 출력 예시 no yes yes 앞선 이진탐색 알고리즘을 연습하기위해 재귀와 반복문 두가지 방법을 사용했고 추가적으로 만약 이걸 상관없이 풀었을 경우 코드 또한 풀었다. 1. 이진탐색 재귀 # 7-3 이진 탐색 부품.. 2022. 10. 14.
[Python][이코테] 이진 탐색 이진 탐색 Binary Search 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 방법이다. 이진 탐색은 변수 3개를 사용한다. 시작점, 끝점 그리고 중간점 예를들어 0 2 4 6 8 10 12 14 16 18 의 배열에서 4를 찾는다고 가정하자 0 2 4 6 8 10 12 14 16 18 우선 시작점은 [0], 끝점은 [9] 중간점은 9/2 = 4.5 에서 소수점은 버려서 [4]로 지정한다. [0] = 0, [9] = 18, [4] = 8 [4]의 데이터와 찾으려는 값 4를 비교한다. [4]의 값이 더 크므로 중간점 이후의 값은 확인할 필요.. 2022. 10. 13.
반응형

티스토리툴바