백준/증가수열 & 투포인터12

• 

  [백준 14719번 / C++] 빗물 투 포인터를 활용해서 풀었다. 간단하게 그림을 그려서 설명하겠다. 위의 그림처럼 Start 인덱스에서 물이 채워지는 양은 Start 인덱스 기준으로 왼쪽 블락과 오른쪽 블락을 확인해야 한다. 즉, 현재 블럭의 높이보다 큰 값중에 왼쪽에서의 블락의 최댓값과 오른쪽에서의 블락의 최댓값을 구해서 빼주면 되는것이다. result += min(L_max, R_max) - v[Start] * 물이 넘치게 되면 작은 블락을 넘기기 때문에 양쪽 블락 중 작은 값을 구한다. #include #include #include using namespace std; int main() { int m, n; cin >> m >> n; vector v; for (int i = 0; i >.. 백준/증가수열 & 투포인터 2022. 3. 10.

• 

  [백준 2631번 / C++] 줄세우기 LIS 문제이다. 수열이 만약 "3, 5, 8, 10, 1, 4" 으로 주어졌다면 직관적으로 1과 4를 앞에다가 놓으면 되는거 아닌가? 라는 생각이 들면 된다. 그렇다면 그 기준이 뭘까? 위의 수열에서 보면 3 1 > n; vector v(n+1); for (int i = 1.. 백준/증가수열 & 투포인터 2022. 3. 7.

• 

  [백준 1806번 / C++] 부분합 투포인터 문제이다. #접근방법 start, end, sum 변수 생성 start 포인터가 end 포인터 이하일 때 동안 while문을 반복 sum값이 s값보다 이상이면 현재 길이의 최솟값 갱신 sum값이 s값보다 이상일 때 start 포인터 증가 ( sum 값 감소) sum값이 s값보다 미만일 때 end 포인터 증가 ( sum 값 증가) #include #include #include using namespace std; int main() { int n, s; cin >> n >> s; vector v; for (int i = 0; i > a; v.push_back(a); } int start = 0; int end = 0; int sum = 0; int re.. 백준/증가수열 & 투포인터 2022. 3. 2.

• 

  [백준 2230번 / C++] 수 고르기 투포인터 문제이다. 접근 방법 1. 벡터 오름차순 정렬 및 start, end 포인터 생성 후 0으로 초기화 2. result 값은 벡터 원소중 최솟값과 최댓값의 차이값으로 저장 3. end포인터의 벡터 원소값이 m보다 작으면 end 포인터 증가 4. end포인터의 벡터 원소값이 m보다 크거나 같다면 result 최솟값 갱신 (차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램) #include #include #include using namespace std; int main() { int n, m; cin >> n >> m; vector v(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); int s, e; s = 0; .. 백준/증가수열 & 투포인터 2022. 2. 16.

• 

  [백준 2003번 / C++ / 투포인터] 수들의 합2 투포인터를 활용한 문제이다. 1. s, e 포인터를 생성하여 벡터의 첫번째 원소를 가리킨다. 2. e 포인터가 벡터의 사이즈보다 작을때 동안 반복문을 돌린다. 3. 만약 sum값이 m보다 작다면 s포인터가 가리키고 있는 원소의 값을 sum값에 빼주면서 포인터의 위치를 하나 증가 4. sum값이 m가 같다면 result 값 증가 5. s 포인터가 증가 시켜야하는 조건문에 부합되지 않으면 continue에 걸리지 않는다. 그러므로 end 포인터를 증가시켜야하는 코드부분에 도달하게 된다. 여기서 주의할 점은 증가된 e포인터가 원소의 값을 갖고 있을때만 sum에 더해준다. #include #include using namespace std; int main() { int n, m; cin >> n >> m; v.. 백준/증가수열 & 투포인터 2022. 2. 16.

• 

  [백준 1940번 / C++] 주몽 투포인터를 활용한 문제이다. 두개의 재료가 합쳐져서 M이라는 값과 일치해야만 갑옷이 만들어진다는 점을 고려해서 풀어보자. 1. 벡터에 재료들의 고유번호를 오름차순으로 정렬해서 저장한다. 2. 첫번째 원소와 마지막번째 원소를 S와 E라는 변수에 각각 저장한다. 3. 벡터의 S 포인터의 원소와 E 포인터의 원소를 더했을 때 M인지를 확인한다. - M보다 작다면 S의 값을 올려준다 (원소의 값을 증가시키는 역할) - M보다 크다면 E의 값을 내려준다 (원소의 값을 감소시키는 역할) - M가 일치하면 RESULT 값을 증가시켜 준다. #include #include #include using namespace std; int main() { int n, m; vector v; cin >> n >> m; for .. 백준/증가수열 & 투포인터 2022. 2. 10.

• 

  [백준 1911번 / C++] 흙길 보수하기 [백준 2170번 / C++] 선 긋기 투포인터를 활용한 문제이다. 1. pair 구조를 가진 벡터를 오름차순으로 정렬하자. 2. 첫번째 벡터 쌍의 원소 값 두개(X, Y)를 start 와 end 라는 변수에 각각 저장하자. 3. 벡터 사이즈만큼 반복문을 돌 baebalja.tistory.com 위의 문제와 유사하니 풀어보길 권한다. 투포인터를 활용한 문제이다. 1. pair 구조를 가진 벡터를 오름차순으로 정렬. 2. 첫번째 벡터 쌍의 시작위치값을 start에 저장하고 end 라는 변수에는 시작위치값 + 물웅덩이 길이를 저장. 3. 벡터 사이즈만큼 반복문을 돌린다. 이때, 벡터 쌍의 원소 중 시작 위치 값이 start 변수의 값보다 크다면 이전 웅덩이에서 활용했던 널빤지가 현재 웅덩이에 영향을 주지 않.. 백준/증가수열 & 투포인터 2022. 2. 9.

• 

  [백준 2170번 / C++] 선 긋기 투포인터를 활용한 문제이다. 1. pair 구조를 가진 벡터를 오름차순으로 정렬하자. 2. 첫번째 벡터 쌍의 원소 값 두개(X, Y)를 start 와 end 라는 변수에 각각 저장하자. 3. 벡터 사이즈만큼 반복문을 돌린다. 이때, 벡터의 첫번째 원소의 값(X)이 end 변수의 값보다 작거나 같으면 선이 이어진다는 의미이므로, 벡터의 두번째 원소의 값과 end 변수에 저장된 값 중 큰 값으로 end 변수를 갱신해나간다. 만약, 벡터의 첫번째 원소의 값(X)이 end 변수의 값보다 크다면 선이 겹치지 않았다는 의미이므로 start, end 변수에는 해당 벡터의 원소의 값들로 새로 저장해준다. #include #include #include using namespace std; int main() { ios.. 백준/증가수열 & 투포인터 2022. 2. 9.

• 

  [백준 2670번 / C++ ] 연속부분최대곱 1. double 타입의 벡터 배열 생성. 2. 벡터 첫번째 원소를 가지고 있는 b라는 변수 생성. 3. 벡터의 사이즈만큼 반복문 돌리면서 연속된 값의 곱셈이 현재 위치의 벡터 원소보다 작으면 b 변수에 현재 벡터 원소 값 저장. 그렇지 않다면 연속된 값 곱하기. 4. reuslt 값이 최대값인 것을 계속 갱신하기. #include #include #include using namespace std; int main() { int n; cin >> n; vector v(n,0); for (int i = 0; i > v[i]; } double b = v[0]; double result = 0; for (int i = 1; i v[i]*.. 백준/증가수열 & 투포인터 2022. 2. 8.

• [백준 3273번 / C++] 두 수의 합 투포인터 문제다. 1. 입력된 모든 값을 벡터에 저장한 후 오름차순으로 정렬시킨다. 2. 인덱스의 시작점, 인덱스의 끝점을 저장 시킨다. - 시작점과 끝점에 해당하는 원소가 같으면 시작점만 오른쪽으로 이동 - 시작점과 끝점에 해당하는 원소의 합이 X의 값과 같으면 카운트 및 시작점 오른쪽으로 이동. - 시작점과 끝점에 해당하는 원소의 합이 X의 값보다 작으면 끝점 왼쪽으로 이동. - 시작점과 끝점에 해당하는 원소의 합이 X의 값보다 크면 시작점 오른쪽으로 이동. #include #include #include using namespace std; vector v; int s, e; int main() { int n; cin >> n; v.resize(n, 0); for (int i = 0; i < n; .. 백준/증가수열 & 투포인터 2022. 1. 27.