알고리즘/이분탐색2 23032 - 서프라이즈~ with Python 주저리 주저리 맞춘 사람 43명 안에 든 행복이 든다? 문제는 두 그룹을 만들고, 그 그룹들의 무게 합의 차가 제일 작게한다. 대신 그룹원들은 서로 번호가 연속되어야한다... 고민이 많이 필요한 문제였다. 문제 해결 일단 이 문제에선 중요한 것은 그룹을 만들고, 그 들의 스테이크의 합의 차가 제일 작게 만들어야 한다. 따라서 그룹을 만드는 것이 제일 중요하다 볼 수 있다. 생각해보자 그룹을 만드는데 겨우 2그룹만 만들것이다. 그럼 간단하게 중간을 기준으로 삼아 그룹을 나누면 된다. 즉 mid값으로 시작해 1~n까지 돌면서 mid의 왼쪽과 오른쪽으로 그룹을 나누어 주면 된다. 여기서 중요한 점이 누적합 개념이다. 만약 그냥 저 그룹만 나누고 sum이런 것을 이용해 합을 구하면 시간 초과이다. (당연히도) .. 2023. 3. 30. [이분탐색][해시] 1920 수 찾기 (실버4) with Python 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 주저리 설명 문제는 간단하다. A라는 배열을 주고 M이라는 배열을 주어 M의 배열 숫자 중 A의 배열에 들어가 있는것이 있는가? 이것이 문제이다. 문제는 시간 초이다. N이 십만, M이 십만 순전히 이를 다 찾는 다면 걸리는 시간은 O(n^2) 이러면 1초내로 실행이 될 거라 판단 되지 않는다. 따라서 문제에서 요구하는 것은 시간을 어떻게 줄일 것인.. 2023. 2. 18. 이전 1 다음 728x90
