본문 바로가기

투포인터

 (10)
[백준] 2473번 : 세 용액 🤔 문제분석📝 문제요약3개이상의 용액이 주어졌을때 3개를 뽑아서 합이 0에 가장 가까운 용액을 찾는 문제이다.🎯 필요한 개념투포인터✅ 알고리즘용액을 오름차순으로 정렬한다.2중 for문으로 2가지의 용액을 뽑는다.남은 하나의 용액을 투포인터를 활용하여 찾는다.합이 0보다 작은경우 Left를 증가 시킨다.합이 0보다 큰경우 Right를 증가 시킨다.모든 경우를 탐색하면서 가장 0에 가까운 용액을 찾아서 오름차순 정렬하여 리턴한다.💻 코드#include #include #include #include using namespace std;int main() { int N; cin >> N; vector A(N); for (int i = 0; i > A[i]; } sort(..
[프로그래머스] 쿠키 구입 https://school.programmers.co.kr/learn/courses/30/lessons/49995 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr🤔 문제분석연속된 배열이 주어졌을때, A[l] + … A[m] = A[m+1] + .. + A[r] 을 만족하는 A[i] + .. A[m]의 최대값을 구해야한다.주어진 배열의 크기가 2000 이하이니 N의 제곱으로 문제를 접근하였습니다. 모든 경우의수를 다 탐색해보고 가장 최대값을 갱신하면되는데 두 가지의 조건으로 이중 반복문을 구성하여 문제를 해결 하였습니다.i번째 인덱스로부터 배열을 나눈다.투포인..
[백준] 3649번 : 로봇 프로젝트 3649번: 로봇 프로젝트 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 🤔 문제분석 이분탐색 혹은 투포인터로 문제를 해결 할 수 있으나 이분탐색 풀이법으로 문제를 해결하였습니다. 레고를 사이즈 오름차순으로 정렬한뒤에 순회하는데 i번째를 순회할때 (i+1, N)까지 이분탐색을 통하여 (arr[i] + arr[mid])값이 블록의 사이즈랑 맞을경우는 후보에 두고, 블록 사이즈보다 작다면 start를 mid+1로 크다면 end를 mid-1로 두어 좁혀가며 탐색을 한다. 후보들을 모두 구..
[백준] 2230번 : 수 고르기 2230번: 수 고르기 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 🤔 문제분석 이분탐색을 이용하여 문제를 해결하였습니다. 내림차순으로 정렬한뒤에 원소를 순회하는데 순회 하고자 하는 위치 +1 부터 마지막 원소까지 이분탐색으로 mid 값을 조정하여 최소 M값을 찾아냅니다. M값보다 크거나 같을경우 최소값을 갱신하고 end 값을 mid - 1로 지정하여 더 작은 값을 찾아냅니다. 반대로 M보다 작을경우 start를 mid +1로 지정하여 M보다 큰 값을 찾게 만듭니다. 💻 코드 impor..
[백준] 2473번 : 세 용액 2473번: 세 용액 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 🤔 문제분석 한 용액을 선택한뒤에 투포인터를 활용하여 해당 용액과 더했을때 0과 가까운 수를 찾으면된다. 이것도 마찬가지로 더했을때 0보다 크다면 right값을 감소시키고 0보다 작다면 left값을 증가시키면서 값을 찾아나아가면 된다. 아래의 두 용액 문제를 풀면 세 용액도 위의 설명한대로 문제를 해결 할 수 있다. 2470번: 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 1..
[백준] 2470번 : 두 용액 2470번: 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 🤔 문제분석 정렬 + 투포인터 문제로 pleft, pright를 두고 data[pleft] + data[pright]를 더한 값이 0보다 클경우 pright값을 줄이고 0보다 작을 경우 pleft값을 줄여가며 최대한 0에 가까운 수를 찾는다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) data = list(map(int, input().spli..
[백준] 7453번 : 합이 0인 네 정수 7453번: 합이 0인 네 정수 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 🤔 문제분석 투포인터 및 정렬문제로, A,B,C,D를 입력받고, A배열과 B배열을 합하여 AB배열을 만들고, C배열과 D배열을 합하여 CD배열을 만듭니다. 만든 배열을 정렬을하고, AB는 왼쪽으로부터 오른쪽으로 CD는 오른쪽으로부터 왼쪽으로 순회해 가면서 두개의 값이 0보다 클경우, 작을경우, 0과 같을 경우로 분기하여 문제를 해결합니다. 여기서 중요한점은 0이 되었을때 AB 혹은 CD값이 중복된 값을 카운팅 해..
[백준] 1253번 : 좋다 1253번: 좋다 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 🤔 문제분석 N이 2000보다 작거나 같기때문에 시간복잡도는 O(n^2)으로 생각 할 수 있고 정렬 + 투포인터로 문제를 해결 할 수 있다. 입력받은 배열을 정렬한뒤 배열을 오름차순으로 순회하면서 해당수가 좋은 수인지 아닌지 판단한다. 좋은 수 인지 아닌지 판단하는 방법을 투포인터를 활용하여 해결한다. left = 0, right = len(arr)- 1로 둔다. arr[left]와 arr[right]를 더하여 현재 값과 비교를하고, 만약 값이 더 크다면 right값을 감..

티스토리툴바