본문 바로가기
728x90

이분탐색18

[python] 백준 7453 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 해결 먼저 n행이면 배열의 크기가 n이라는 것이고 열은 각각 A,B,C,D를 나타낸다는 것을 알아야한다. A,B,C,D를 각각 원소를 찾기에는 (O($n^{4}$))의 시간복잡도가 나오기 때문에 가급적 줄여야한다. 따라서 AB원소의 합을 ab에 CD원소의 합을 cd에 넣어서 줄일려고 하였다.(O($n^{2}$)) 그리고 원소를 각각 오름차순으로 배열을 하고 ab는 인덱스0부.. 2023. 4. 25.
[python] 백준 2473 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제 해결 전형적인 이분탐색 문제 (세 원소의 합이 C(상수) 일때 세 원소를 구하는 문제) 가장 작은 수를 고정시키고 나머지 두 수를 이분탐색으로 구하는 문제 그런데 python3에서는 시간초과가 난다...ㅜㅜ(pypy3에서는 잘 풀림) 근데 다른 분들도 이렇게 많이 푼듯? CODE import sys input = sys.stdin.readline INF =sys.maxs.. 2023. 4. 24.
[python] 백준 3151 합이 0 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 문제 해결 3개의 수를 고르는 문제는 전형적으로 A[i] + A[j] + A[k] = c 에서 A[j] + A[k] = c - A[i]로 바꾼다. c= 0이므로 A[j]+A[k] = -A[i]를 찾는 문제 그러면 A[i]를 고정시키고 j와 k를 찾는 것이 편하다. 처음에 j= i+1 k=n-1으로 정하고 A[j]+A[k] >A[i]면 k를 내리고 A[j] + A[k] < A[i]이면 j를 올리는 식으로.. 2023. 4. 24.
[python] 백준 16401 과자 나눠주기 https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 문제 해결 과자의 길이를 이분탐색으로 구하는 전형적인 이분탐색 문제 다만 길이를 구했다고 끝이 아니라 최대 길이를 구하는 것이므로 start 2023. 4. 23.
728x90