https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 꽤 어려운 이분 탐색 문제이다,, 우선 첫번째 의문! 이게 왜 이분탐색이지? -> 사실 이것만 해결되면 금방 풀린다. 문제의 조건을 보면 범위가 10억(?맞나 암튼)이므로 완전탐색으론 풀 수 없다. 보통 조건의 범위가 어마무시하면 이분탐색인 경우가 많다! 이건 소소한 꿀팁 여기서 중요한 것은 '도대체 뭘 탐색할 것인가?' 이다. 이 문제에서는 돌을 n개 제거했을 때의 최소 거리들 중 최대 거리를 ..
https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분탐색 문제이다. 다만 이 문제가 좀 까다로운 점은, 도대체 뭘 탐색해야 할까? 에 대한 물음일 것이다. 최악의 경우를 따져보았을 때, 걸리는 시간이 너무 커서 탐색할 엄두도 안나겠지만, 이분탐색은 log n의 시간 복잡도를 가지므로 충분히 해결할 수 있다. 다른 이분탐색 코드와 다른 점이 있다면, 1. 개인의 심사원이 주어진 시간(mid)동안 처리할 수 있는 손님의 수를 구하는 코드 2. 예를..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2467번 용액, 2470번 두 용액, 2473번 세 용액으로 이어지는 시리즈 문제이다. 전체적인 맥락은 비슷하므로 한 문제만 포스팅하겠다. 투포인터, 이분탐색의 활용문제이다. 총 3개의 포인터가 필요한데 약간의 테크닉이 필요하다. 우선 개략적인 방법은 흔한 투포인터를 이용한 이분탐색과 동일하다. 여기에 하나의 포인터를 추가하는데, 포인터 하나를 고정해서 이용한다! 맨 앞을 ..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net N이 최대 100,000까지 입력이다. 하나하나씩 다 계산해가며 비교하면 100,000 x 100,000으로 1초안에 절대 풀 수 없게 된다. 그래서 이 문제는 이분탐색의 개념과 투 포인터를 활용한다. 우선, 배열을 쭉 오름차순으로 정렬한 뒤 (오름차순으로 정렬하면 음수는 절댓값이 큰 것이 앞에 오고, 양수는 절댓값이 큰 것이 뒤로 간다.) 두 개를 더 했을 때 ..
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 각 배열을 처음부터 끝까지 탐색하면 시간초과가 나도록 유도하는 문제이다. O(log n)의 시간복잡도를 가지는 이분탐색을 활용해야한다. 상근이가 가지고 있는 숫자카드가 비교할 배열보다 작으니까, 숫자카드에서 수를 하나 뽑아서 상근이의 숫자카드 목록에 있는지 찾아주면 된다. import sys def binary_search(arr, num,left,right): wh..
https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 가장 공평한 곳에 우체국을 설치한다..! 라고 문제를 이해한다면 풀이법에 접근하기 훨씬 간단해진다. 보통 친구들과 약속 장소를 정할 때, 중간 지점일 수록 그리고 친구의 수가 많은 곳일 수록! 위 2가지로 정할 것이다. 우리는 이러한 룰을 문제에 적용시켜볼 것이다. 먼저 마을 번호를 기준으로 오름차순 정렬한다. ..
