본문 바로가기

Algorithm/이분탐색12

[백준] 10815번 숫자 카드 사용 언어 - Python3 문제 - 10815번 숫자 카드 이분탐색 : 업다운 게임. 절반부터 시작해서 효과적으로 범위를 줄인다. https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답 이분탐색 - 절반부터 값과 같은지, 큰지, 작은지 확인 후 포인터 수정 s = 0, e = n-1, mid = (s+e)//2 1. 정렬 시키기 이분탐색은 기준 숫자카드가 정렬되어 있어야 중간값보다 크고/작다 대소비교가 가능하다. .. 2023. 11. 3.
[Python3] 백준 1166번 선물 사용 언어 - Python3 문제 - 선물 1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 정답 이분 탐색 문제 (정답 맞춘 여부 X) 1. L, W, H를 구하려는 값 A로 나누었을 때 N보다 작거나 같아야하므로 A를 구하기 위한 이분탐색을 사용한다. A는 최소 0개 부터 쵀대 max(L,W,H)개 까지 있을 수 있으므로, left = 0, right = max(L,W,H), mid = (left+right)//2 이다. 만약 N개의 상자를 모두 넣을 수 있다면(= N보다 작거나 같으면), left =.. 2023. 4. 4.
[Python3] 백준 1072번 게임 사용 언어 - Python3 문제 - 게임 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 정답 이분 탐색 문제 (정답 맞춘 여부 X) 1. 파이썬에서 소숫점 버린 승률 구하기 (Y//X)*100 파이썬에서 부동소숫점 오차로 오류! Z = (Y*100)//X 사용! 2. 예외 처리 형택이는 앞으로의 모든 게임에서 지지 않기 때문에 x+1, y+1이다. 만약 x==y 라면, x//y=100이고 x+1==y+1이라 Z값이 항상 같다. 절대 변하지 않는다. z가 99 이상이면 print(-1)을 출력해준다... 2023. 4. 4.
[프로그래머스 lv 4] 징검다리 사용 언어 - Python3 문제 - 징검다리 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 징검다리를 하나씩 건너면서 두 돌 사이의 거리를 찾는 이분 탐색 문제 (정답 맞춘 여부 X) 정답 풀이 1. start,end 정의 돌 사이의 최소 거리는 1, 최대 거리는 distance 2. rocks 오름차순 정렬 마지막 돌과 도착지점 사이의 거리도 있으므로, rocks 리스트에 distance를 추가해준다. 3. start n인 경우, mid 값이 크기 때문이라 end = mid-1 아닌 경우, answer에 mid 값 입력한다. mid 값이 작기 때.. 2023. 2. 7.
[프로그래머스 lv 3] 입국심사 사용 언어 - Python3 문제 - 입국심사 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 심사한 수가 n이 될 때의 특정 시간을 찾는 이분탐색 문제 (정답 맞춘 여부 X / 코드 풀이) 어떤 값(mid)을 입국심사에 걸리는 times로 나눈 몫이 총 명수가 되어야 한다. mid//time == n 구하려는 시간을 기준으로 이분탐색을 진행한다. 최소 시간(start)은 min(times), 최대시간(end)은 max(times)*n로, start와 end 중간값인 mid 부터 검사를 시작하면서 mid//time == n 이 될때까지 while 반복.. 2023. 2. 6.
[백준] 12015번 가장 긴 증가하는 부분 수열 2 사용 언어 - Python3 120154번: 덱 (골드5, 큐) 문제 ★이분 탐색 문제★ 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 정답 이분탐색으로 시간복잡도 O(nlogn) 개선 (코드 풀이) ans=[0] 리스트에 값 비교하면서 append 해주기 ans[-1] ans의 가장 마지막 값이 i보다 작으면 ans에 append해준다. 그렇지 않다면, 이분탐색으로 인덱스 mid값을 조정해준다. ans[mid]가 i보다 작으면 start = mid+1, i보다 크면 end = mid로 범위를 업데이트해준다... 2023. 1. 23.
[백준] 1300번 K번째 수 사용 언어 - Python3 1300번: K번째 수 (골드2, 이분 탐색) 문제 ★이분 탐색 문제★ 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 정답 i*j 배열의 규칙을 알아내는 이분탐색 문제!! 1~k 범위를 줄여가며 검색한다. (코드 풀이) 1. 변수 선언 n 배열의 크기 k b의 인덱스 2. 이분 탐색 정의 몇 번째인지 인덱스를 구해야하므로 k의 범위를 이분 탐색한다. 배열은 항상 1*1로 시작하기 때문에, start =1로 한다. end = k까지만 진행해서 더이상의.. 2023. 1. 21.
[백준] 2110번 공유기 설치 사용 언어 - PyPy3 2110번: 공유기 설치 (골드4, 이분 탐색) 문제 ★이분 탐색 문제★ 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net python3으로는 시간 초과로 오답이지만, pypy3으로는 정답! 이분탐색은 while문으로 돌아가서 python보다 빠른 pypy3으로 했을 때만 정답이 나올 수 있다. 정답 집 좌표값의 차이를 start/end/mid 값을 지정하는 이분탐색 문제 !! (코드 풀이) 1. 변수 선언 n 집의 개수 c 공유기의 .. 2023. 1. 21.
[백준] 2805번 나무 자르기 사용 언어 - Python3 2805번: 나무 자르기 (실버2, 이분 탐색) 문제 ★이분 탐색 문제★ 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 1. 변수 선언 나무의 수 n개 나무의 길이 m개 tree는 정렬된 상태로 입력받기 2. 이분 탐색 정의 높이가 1 이상, max(tree) 이하 여야 자를 수 있기 때문에, 시작점은 1 , 끝점은 max(tree)로 선언한.. 2023. 1. 21.
[백준] 10816번 숫자 카드 2 사용 언어 - Python3 10816번: 숫자 카드 2 (실버4, 이분 탐색) 문제 ★이분 탐색 문제★ 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 1. 리스트 원소별 개수 구하기 mycard를 sorted 정렬하여 입력받는다. 정렬한 내카드를 한개씩 확인하면서 개수를 센다. count = {} 딕셔너리를 만들어서 여러개일 경우 중복 개수를 세준다. list_1 = [1, .. 2023. 1. 21.

티스토리툴바