# two pointer
백준 1806 부분합 (C++)
1806번: 부분합 투포인터를 활용한 문제이다. start를 기준으로 반복문을 돌며 내부 반복문에서 end를 옮기며 S보다 합이 큰 연속된 부분합의 길이를 구했다. 그 후 더 짧은 길이의 부분합을 구하기 위해 end까지 start를 옮기고 발견하면 그 길이를 구하고
[백준] 두 용액 - 골드 5
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터
[백준] 수들의 합2 - 실버 4
N개의 수로 된 수열 A1, A2, …, AN 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 Ai + Ai+1 + … + Aj-1 + Aj가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 30
Leetcode - 3. Longest Substring Without Repeating Characters
문자열이 주어질때, 반복된 문자가 없는 가장 긴 substring의 길이를 구하라.sliding window 로 해결. (discussion참고) left/right 두개의 포인터를 이동하면서 window의 사이즈를 변경하여 체크.해시테이블에 빈도수를 저장. tabl
Leetcode - 11. Container With Most Water
수조와 칸막이가 주어지고 두개를 선택한다고할때 가장 많은 물을 담을 수 있는 경우, 얼만큼의 양을 담을 수 있는가? 가령 아래의 경우, 최대인경우 높이 7 너비 7로 49만큼의 양을 담을 수 있다.between height1 ~ height7 -> 7 \* 7 = 49
[3273번] 두 수의 합
백준 3273번 두 수의 합투 포인터를 이용하여 문제를 해결할 수 있습니다.주어진 수열을 오름차순 정렬한 뒤 양끝에서부터 더하면서 기준값(x)과 비교합니다.기준값보다 두 수의 합이 클 경우 오른쪽 끝 포인터가 -1, 작을 경우 왼쪽 끝 포인터가 +1이 되면서 두 포인터
[백준] 20922번 - 겹치는 건 싫어 Python
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. $100\\,000$ 이하의 양의 정수로 이루어진 길
[백준] 21921번 - 블로그 Python
찬솔이는 블로그를 시작한 지 벌써 $N$일이 지났다.요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.찬솔이는 $X$일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.찬솔이를 대신해서 $X$일 동안 가장 많이 들어온 방문
Remove Nth Node From End of List
문제 링크주어진 단일 연결리스트에서 마지막에서 N번째 노드를 제거하는 문제이다.처음 문제를 접근했을 때는 2개의 변수를 통해 한 변수가 n번 이동할 때 마다 다른 변수가 1번 이동하여 n의 간격을 유지하게 하려 했다.1칸씩 이동할 때 마다 cnt를 1씩 증가시켜 n으로
두 리스트 합치기
오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.첫 번째 줄에 첫 번째 리스트의 크기 N(1<=N<=100)이 주어집니다.두 번째 줄에 N개의 리스트 원소가 오름차순으로 주어집니다.세 번째 줄에 두 번
[JavaScript] 5. Longest Palindromic Substring
dp로 풀수있고, dp의 공간복잡도 개선을 위해 투포인터로 풀수있다.2d 배열을 DP 저장소로 사용한다.다만, 대각선 오른쪽만 사용한다. 공간절반이 버려지는 셈이라 비효율적이다.모두 초기값 0으로 설정해두고 오른쪽 아래부터 왼쪽위로 순회한다.현재 인덱스 i와 j에 대해
[581] Shortest Unsorted Continuous Subarray | LeetCode Medium
Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array wil
[baekjoon] #1253: 좋다
Problem linkSort number list in ascending order.Iterate 0, n - 1 with index i.Iterate 0, n - 1 with index j except (i == j) to avoid duplicate positio
[ leetcode ] Longest Substring with At Most Two Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/요즘 알고리즘은 통 안풀다가 오랜만에 리트코드를 켰다.그리고 만난 문제 문제 설명은 다음과 같다.오직 두
[BOJ] 1644 소수의 연속합
https://www.acmicpc.net/problem/1644아이디어Two-pointer를 연습하기 위해 풀었다. (알고리즘 알고 시작)처음에 소수만 모아둔 primes를 만들지 않고 메인 로직에서 소수 판별까지 같이 했는데 너무 복잡해져서 리스트를 따로
[BOJ] 1806 부분합
🔗 Problem https://www.acmicpc.net/problem/1806 problem 👩💻 Code - Two-pointer package baekjoon; import java.io.BufferedReader; import java.io.Input
[Algorithm]투 포인터(Two Pointer)
투 포인터 > RGB거리 - 1149, DP, 실버 RGB 거리 🧐 알고리즘[접근방법] 각각의 집의 빨강, 초록, 파란으로 칠하는 비용을 나타내는 Price 2차 배열 선언 각각의 집까지 빨강, 초록, 파란색으로 칠하는 칠하는 최소 비용을 저장하는 DP 2차 배
백준 20922, 겹치는 건 싫어 - 투 포인터
https://www.acmicpc.net/problem/20922n 최대값: 2 x 10^5=> 시간 복잡도 O(n^2) 미만이어야 함 (n x n 의 2중 for 문 사용 X)"연속" 부분 수열=> 연속하다는 특징 이용가능하므로, 투 포인터 사용2개의 포인