Algorithm & Problem Solving/투 포인터(Two Pointer)
-
[백준 16472] 고냥이 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 5. 00:53
www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제풀이 N, S : 입력값 check : 알파벳 개수 left, right : 투 포인터 tmp : 인식한 문자 개수 q : 현재 인식한 문자열 투 포인터(Two-Pointer) 를 이용하여 새로 인식한 글자와 문자열의 길이를 계산해 문자열의 최대 길이를 구할 수 있다. 1. 투 포인터를 이용해 왼쪽부터 오른쪽 방향으로 하나씩 글자를 인식한다. - 인식한 문자 개수(tmp) 가 N 인데, 새로운 글자가 나타나면 ans..
-
[백준 15565] 귀여운 라이언 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 30. 16:11
www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 문제풀이 N, K, arr : 입력값 left, right : 투 포인터 q : 집합을 담는 deque cnt : 1의 개수 ans : 1이 K개 일때의 집합의 최소 길이 기초 투 포인터(Two-Pointer) 문제였다. 쉬운 문제였는데, 처음에 left, right 만으로 집합의 길이 계산하려다가 계속 에러나서 문제 푸는데 오래걸려서, 그냥 deque 사용해서 해결하였다. 이 정도의 문제는 정말 빠르게 ..
-
[백준 14921] 용액 합성하기 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 30. 14:52
www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당 www.acmicpc.net 문제풀이 N, arr : 입력값 left, right : 투 포인터 ans : 결과값 입력 배열이 정렬되어 있기 때문에 따로 정렬이 필요하지 않고, 곧바로 투 포인터(Two-Pointer)를 진행해서 탐색하면 쉽게 해결할 수 있다. 1. left, right 를 통해 배열의 양쪽 끝에서부터 각 원소를 더해가며(tmp) 최소값을 찾는다. - tmp의 값이 음수이면 절대값을 줄이기 위해 ..
-
[백준 2842] 집배원 한상덕 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 29. 22:00
www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 문제풀이 N : 입력값 board : 입력값(마을을 나타내는 행렬) tiredness : 입력값(지역의 고도) houses : 전체 K의 개수 fatigue : 중복 제거 후 정렬된 tiredness left, right : 투 포인터 ans : 결과값(가장 작은 피로도) BFS와 투 포인터(Two-Pointer) 를 결합한 문제이다. 굉장히 까다롭고 어려운 문제라고 생각한다... 핵심은 입력..
-
[백준 1484] 다이어트 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 29. 18:02
www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 문제풀이 G : 입력값 P : 현재 몸무게 Q : 성원이가 기억하고 있던 몸무게 left, right : 투 포인터 변수 ans : 결과값 (가능한 현재 몸무게를 담고 있는 리스트) 처음에 투 포인터 탐색을 위한 제한(N, M) 을 1000으로 해서 틀렸습니다를 받았다. 이후 G 가 99999 일때 50000^2 - 49999^2 = 99999 이 가능하다는 것을 알게 되었고, N, M 을 100000 까지 늘렸더니 ..
-
[백준 14746] Closest Pair (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 29. 16:37
www.acmicpc.net/problem/14746 14746번: Closest Pair Your program is to read from standard input. The input consists of four lines. The first line contains two integers, n (1 ≤ n ≤ 500,000) and m (1 ≤ m ≤ 500,000), where n is the number of points in set P and m is the number of points in set Q. In th www.acmicpc.net 문제풀이 N, M : 입력값 c1, c2 : 입력값 => 두 점의 X 좌표 P, Q : 입력 배열 left, right : 투 포인터 변수 ans ..
-
[백준 7795] 먹을 것인가 먹힐 것인가 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 27. 00:32
www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제풀이 N, M : 배열 A, B의 크기 A, B : 입력 배열 A_idx, B_idx : 투 포인터 count : A의 원소가 B의 원소보다 큰 경우의 갯수를 메모라이제이션 ans : 결과값 tmp : A_idx 번째의 A 원소에서, 현재 B_idx 부터 A[A_idx] > B[B_idx] 를 만족하는 B_idx 의 갯수 N, M 조건이 20000 밖에 되..
-
[백준 3273] 두 수의 합 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 26. 23:19
www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제풀이 N, arr, X : 입력값 투 포인터(left, right)를 이용하여 해결할 수 있다. 1. 배열(arr)을 입력받고 정렬을 해준다. - 정렬을 하지 않으면 투 포인터를 정상적으로 사용할 수 없다. 2. left, right 를 이용하여 arr[left]와 arr[right]를 더해준다. (이 값을 tmp 변수에 저장) - tmp가 X보다 작을..