이분 탐색
-
백준 2143 두 배열의 합Algorithm/BOJ 2021. 3. 5. 13:44
출처: www.acmicpc.net/problem/2143 분류: 이분 탐색, 투 포인터 접근방식 합이 0인 네 정수 문제와 비슷했던 문제였습니다. 주어진 각 배열에서 나올 수 있는 부분합을 모두 구해준 뒤 정렬해서 투 포인터로 해결했습니다. 마찬가지로 T인 케이스를 찾았을 때 중복인 수의 개수를 세서 쌍을 찾아줘야 합니다 :) 해결방법 let t = Int(readLine()!)! let n = Int(readLine()!)! let a = readLine()!.split(separator: " ").map { Int(String($0))! } let m = Int(readLine()!)! let b = readLine()!.split(separator: " ").map { Int(String($0))..
-
백준 7453 합이 0인 네 정수Algorithm/BOJ 2021. 3. 4. 14:53
출처: www.acmicpc.net/problem/7453 분류: 투 포인터, 이분 탐색 접근방식 4개의 배열이 주어지고 각 원소의 합이 0이되는 쌍이 몇 개인지 찾는 문제입니다. 이 문제의 첫 번째 아이디어는 4개의 배열을 각각 생각하려고 하면 힘드니 2개씩 묶어서 합쳐주는 것입니다. a b 의 합이 될 수 있는 모든 경우를 담은 배열 ab, c d 의 합이 될 수 있는 모든 경우를 담은 배열 cd 를 만들고 둘 모두 오름차순으로 정렬해줍니다. 다음으로 ab는 작은 수부터, cd는 큰 수부터 포인터를 움직여 0이 되는 경우를 찾는 것입니다. ab, cd 원소의 합이 0보다 작으면 low를 증가시키고 0보다 크면 high를 줄여줍니다. sum이 0일 때 주의해야할 건 중복을 찾아서 쌍을 계산해줘야 합니다..
-
백준 2110 공유기 설치Algorithm/BOJ 2021. 3. 3. 20:52
출처: www.acmicpc.net/problem/2110 분류: 이분 탐색 접근방식 이분 탐색 문제인 걸 알고 접근했는데도 접근이 어려웠던 문제였습니다. ㅠㅠ 이녀석 쉬워지질 않네요... 공유기들의 위치가 주어지기 때문에 이걸 가지고 어떻게 이분탐색을 해야하나 싶지만, 저희는 공유기 사이의 거리가 가장 큰 경우를 찾아야 합니다. 따라서 공유기 사이의 거리를 가지고 이분 탐색을 돌려야 합니다. 따라서 저희는 최소 설치 거리를 low 최대 설치 거리를 high 정해서 이분탐색을 해야합니다. 다음에는 해당 거리를 최소 간격으로 해서 공유기를 설치할 수 있는지 없는지만 체크해주면 됩니다. 이건 일단 나중에 생각해보죠 :( 자 그럼 공유기 사이의 거리가 가장 짧은 경우는 어떤 경우일까요? 바로 옆집에 공유기를 ..