Algorithm & Problem Solving/투 포인터(Two Pointer)
-
[백준 20181] 꿈틀꿈틀 호석 애벌레 - 효율성 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 9. 01:41
www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 문제풀이 N, K, arr : 입력값 dp : i번째 까지의 최대 탈피 에너지 lmax : 애벌레가 먹기 시작하는 구간에서 지금까지 얻었던 최대 탈피 에너지 tmp : 현재 만족도 left, right : 투 포인터 굉장히 까다로운 문제였다. 현재 만족도에 대해서 투포인터를 진행하면서 탈피에너지에 대한 정보도 저장해야 한다. 따라서 투포인터(Two-Pointer)와 DP(Dynamic Pr..
-
[백준 3151] 합이 0 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 8. 15:36
www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 문제풀이 N, arr : 입력값 left, right : 투 포인터 goal : 특정 1개의 원소를 선택하고, 그 수의 음수값 mx_idx : 정렬 후 arr[right]와 동일한 수를 가진 원소의 최소 인덱스 세 용액 문제의 응용이라고 생각한다. 알고나면 어렵지 않은 문제인데, 저 알기까지의 과정이 너무 고통스러웠다 ㅠㅠ.. 특정 1개의 원소를 선택 후, 투 포인터(Two-Pointer)를 통해서 세 원소의 합이 ..
-
[백준 10025] 게으른 백곰 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 6. 13:28
www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 문제풀이 N, K, arr : 입력값 left, right : 양동이가 위치한 가장 좌측과 우측 start, end : 투 포인터 now : 현재 얼음의 양 양동이의 가장 좌측과 우측을 미리 구하여 해당 범위 안에서 투 포인터(Two-Pointer)를 통해 얼음의 최대 양을 구하는 방식으로 해결하였다. 1. 입력을 받으면서 양동이의 가장 좌측과 우측(left, right)을 구한다. 2. 투 포인터를 통해 얼음의 양을 갱신한다. - ..
-
[백준 1253] 좋다 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 5. 15:52
www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제풀이 N, arr : 입력값 left, right : 투 포인터 tmp : i 번째 원소를 제외한 arr 리스트 괜히 어렵게 생각하려다 해결하는데 오래걸렸다. 단순하게 특정한 1개의 원소를 골라서, 해당 원소를 제외한 리스트에서 투 포인터(Two-Pointer)를 통해 두 원소의 합이 선택한 원소와 같은지 비교하는 방식으로 해결할 수 있다. 1. arr 리스트를 정렬한다. 2. 0부터 N - 1 까지 반복문을 통해 특정 원소(arr[i..
-
[백준 15831] 준표의 조약돌 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 5. 10:52
www.acmicpc.net/problem/15831 15831번: 준표의 조약돌 첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조 www.acmicpc.net 문제풀이 N, B, W, arr : 입력값 w_cnt, b_cnt : 현재 수열에서 W와 B의 개수 q : 현재 수열 다른 투 포인터(Two-Pointer) 문제와 큰 차이 없는 문제였지만, 예외 케이스를 처리해줘야 하는 문제였다. 6 0 0 BBBBBB 위와 같은 테스트케이스에서 q(현재 수열)에 들어갈 수 있는 값이 존재하지 않는데, q.popleft() 하기 떄문에 런타임 에러가 났다. 1. ..
-
[백준 20366] 같이 눈사람 만들래? (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 5. 09:56
www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 문제풀이 N, arr : 입력값 left, right : 투 포인터 tmp : 두 눈사람의 키 차이 세 용액 문제에서 조금 더 나아가서 네 용액(?) 문제인 것 같다. 미리 두개의 원소를 지정하고, 해당 두 원소 사이에서 투 포인터(Two-Pointer)를 통해 두 눈사람의 키 차이의 최소값을 구하는 것을 반복하면서 해결할 수 있다. 1. 배열 arr를 정렬해준다. (원본 배열의 ..
-
[백준 13422] 도둑 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 5. 01:40
www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 문제풀이 N, M, K, arr : 입력값 left, right : 투 포인터 tmp : 현재 훔친 돈의 합 q : 현재 수열 투 포인터(Two-Pointer) 를 이용하여 쉽게 해결할 수 있다. 정확히는 투 포인터보다는 슬라이딩 윈도우 문제라고 생각한다. N == M 일때 예외가 존재하므로 이를 처리해줘야 한다. ex ) 1 3 3 5 1 1 1 이 경우 정답은 1이 나와야 한다. (어느 인덱스를 선택하든 모두 같은..
-
[백준 13144] List of Unique Numbers (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2021. 1. 5. 01:27
www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 문제풀이 N, arr : 입력값 check : 특정 원소 방문 여부 체크 start, end : 투 포인터 dp : i번째 인덱스에서 가능한 경우의 수 q : 현재 수열 tmp : 현재 수열에서 새롭게 탐색한 원소의 개수 투 포인터(Two-Pointer)와 DP를 이용해 해결할 수 있었다. 조금 더 효율적인 방법이 있지 않을까 라고 생각이 든다. DP에 대해서 아래의 테스트케이스를 예로 들면 5 1 2 3 3 2 st..