투 포인터

[백준] 1644. 소수의 연속합 (Java)

문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 알고리즘 에라토스테네스의 체, 투 포인터 풀이 에라토스테네스의 체를 이용해 N 이하의 소수를 리스트에 삽입하고, 투 포인터를 이용해 O(N) 의 시간복잡도로 경우의 수를 구한다. 에라토스테네스의 체를 이용한 소수 판별 소수인지 저장할 N+1 크기의 boolean형 변수 prime을 선언한다. prime은 2부터 N까지 모두 true로 초기화한 상태로, 즉 모두 소수라고 가정한 상태로 시작한다. i를 2부터 N의 제곱근까지 1씩 증가시키며 만약 i가 소수라면 i의 배수는 i를 약수로 가지기 때문에 모두 합성수로 변경한다. N의 제곱근까지 수행하는 이유는 N의 약수 중 하나는 반..

[프로그래머스] 숫자의 표현 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 누적합, 투 포인터 풀이 누적합을 이용해 i 부터 j 까지 합을 한번에 계산할 수 있다. 예를 들어 0부터 15까지 누적합 배열은 다음과 같다. 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120 4부터 6까지 합은 6번째 원소인 21 에서 (4-1)번째 원소인 6을 뺀 15가 된다. 6번째 원소인 21이 1+2+3+4+5+6 이고, 3번째 원소인 6이 1+2+3 이기 때문에 두 원소를 빼면 4+5+6만 남기 때문이다. 또한 누적합 배열은..

[프로그래머스] 구명보트 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 그리디, 투 포인터 풀이 몸무게가 가장 큰 사람을 항상 구명보트에 태우면서 몸무게가 가장 작은 사람을 같이 태울 수 있다면 같이 태우는 방법이 항상 구명보트를 제일 적게 쓸 수 있다. 따라서 몸무게를 오름차순으로 정렬한 후 남아있는 사람의 몸무게 중 가장 낮은 몸무게의 인덱스를 가리키는 left 와 남아있는 사람의 몸무게 중 가장 큰 몸무게의 인덱스를 가리키는 right 를 정하고, 모든 사람을 다 태울때까지 (left > right) 구명보트를 하나 사용(answer++)하면서 몸무게가 가장 ..

[백준] 7795. 먹을 것인가 먹힐 것인가 (Java)

문제 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 알고리즘 투 포인터 풀이 1. A와 B를 오름차순 정렬한다. 2. A의 포인터와 B의 포인터를 0으로 초기화한다. (첫 번째 원소부터 비교) 3. A의 포인터의 원소와 B의 포인터의 원소를 비교한다. 3-1. B의 원소가 더 크거나 같다면 A의 포인터를 1 증가시킨다. 3-2. A의 원소가 더 크다면 그 이후 수는 전부 B의 원소를 먹을 수 있는 수이므로 그만큼 sum에 더하고, B의 포인터를 1 증가시킨..

[백준] 20366. 같이 눈사람 만들래? (Java)

문제 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 알고리즘 투 포인터 풀이 4개의 눈덩이를 골라야하므로 완전 탐색을 할 경우 O(n4) 의 시간 복잡도를 가질 것이고 n이 최대 600이므로 시간 초과가 날 것이다. 따라서 투 포인터를 이용하여 O(n3)의 시간 복잡도로 해결한다. 4개의 눈덩이가 크기 순으로 나열되어있다면 1, 4 번째 눈덩이를 합치고, 2, 3 번째 눈덩이를 합쳐야 두 눈사람의 키 차이가 가장 작을 것이다. 따라서 [0~N-1] 범위의 엘사의 첫번째 눈덩이 i..

[백준] 1253. 좋다 (Java)

문제 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 알고리즘 해시맵, 투 포인터 풀이 해시맵을 이용해서 해결할 수도 있고, 투 포인터를 이용해서 해결할 수도 있다. 투 포인터를 이용한 방식이 시간 및 메모리 모두 나은 결과가 나왔다. 1. 해시맵을 이용한 풀이 이중 포문을 통해 모든 수에 대해 해당 수 i와 그 뒤에 있는 수 j의 합을 계산해 해시맵에 합을 key로, 그 합을 만드는 i와 j 리스트를 value로 저장한다. i와 j를 저장하는 이유는 다른 수 두 개의 합으로 나타낼 수 있어야한다는 조건이 있기 때문이다. 만약 i와 j를..

[백준] 15961. 회전 초밥 (Java)

문제 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 알고리즘 투 포인터, 슬라이딩 윈도우 풀이 2531. 회전 초밥 문제에서 N의 개수가 300만으로 100배 늘었다. 따라서 이전 문제를 브루트포스 방식으로 풀었다면 이번 문제에서는 시간 초과가 날 것이다. 연속된 k 개의 값들을 한칸씩 전진하며 탐색하는 문제이기 때문에 슬라이딩 윈도우로 문제를 해결한다. 1. 초밥의 번호를 인덱스로 해당 초밥 번호의 먹은 개수를 저장할 크기 d+1의 int형 배열을 만든다. 2. ..

[백준] 1806. 부분합 (Java)

문제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 알고리즘 누적 합(Prefix Sum), 투 포인터 풀이 연속된 수들의 부분합을 구하기 때문에 누적 합을 사용하면 빠르게 부분합을 구할 수 있다. a번째 원소부터 b번째 원소까지의 합 = [b번째까지의 누적합] - [a-1번째까지의 누적합] 이다. sumAtoB = prefixSum[B] - prefixSum[A-1] 부분합 중 합이 S가 되는 것을 구하기 위해서 투 포인터를 사용한다. 시작 포인터를 start, 끝 포인터를 end라고 한다면..

[백준] 2003. 수들의 합2 (Java)

🔒 문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 🔑 알고리즘 투 포인터 💡 풀이 투 포인터를 이용하여 O(N)의 시간 복잡도로 해결할 수 있다. 범위의 시작을 의미하는 포인터 S와 끝을 의미하는 포인터 E를 모두 배열의 맨 앞에 두고 두 포인터 사이의 배열 값의 합이 M보다 작다면 값을 늘려야하므로 E를 오른쪽으로 한 칸 움직이고, M보다 크다면 값을 줄여야하므로 S를 오른쪽으로 한 칸 움직이고, M과 같다면 count를 1 증가시키고 S를 오른쪽으로 한 칸 ..

[백준] 2461. 대표 선수 (Java)

🔒 문제 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 🔑 알고리즘 투 포인터 💡 풀이 대표 학생을 선택하는 모든 경우의 수는 MN 이고 N과 M 모두 최대 1000 이기 때문에 시간 초과가 발생할 것이다. 따라서 각 학급마다 모든 학생들을 능력치 순으로 정렬하고, 각 학급의 후보 학생의 최소값을 각 학급마다 현재 뽑힌 학생들과 능력치가 유사한 학생의 포인터를 두어 비교하는 방법을 사용하였다. 해당 방법을 사용하면 이미 지나간 학생들(능력치가 낮은 학생들)의 중복 확인을 막을 수 있어 시간이..