본문 바로가기

분류 전체보기67

[백준/C++] #2473 세 용액 (Two Pointer) 문제https://www.acmicpc.net/problem/2473 구상세 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어야 하고, 이때의 세 용액을 출력해야 하는 문제였다. 두 용액 일 때는 아래와 같이 두개의 포인터를 이용해서 풀었었다. https://persi0815.tistory.com/entry/%EB%B0%B1%EC%A4%80C-2467-%EC%9A%A9%EC%95%A1-Two-Pointer 세 용액이면 어떡할까? 고민을 해봤는데, 한 용액을 고정한 뒤 나머지 두 용액을 투 포인터로 찾는 방법이 떠올랐다.  알고리즘: two pointer 풀이 + 코드용액 특성값들을 배열에 넣고 투포인터 사용을 위해 정렬을 했다. 그리고, 한 용액을 선택한 뒤, 나머지 두 용액을 결정하자. brut.. 2024. 7. 3.
[백준/C++] #2467 용액 (Two Pointer) 문제https://www.acmicpc.net/problem/2467   알고리즘: two pointer 풀이 + 코드가장 기초적인 투포인터 문제다.(정렬된) 용액 특성들을 배열에 넣고, 두개의 포인터를 이용하여 배열 값들의 합을 구하며 0과 가장 가까운 값이 나타나면 답을 갱신한다.  #include #include #include #include #define MAX 100001#define INF 987654321#define endl "\n"using namespace std;/*2467번 용액산성 용액: 1부터 1,000,000,000, 알칼리성 용액: -1부터 -1,000,000,000같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합같은 양의 두 용액을 혼합하여.. 2024. 7. 3.
[백준/C++] #1484 다이어트 (Two Pointer) 문제https://www.acmicpc.net/problem/1484   구상두 제곱수의 차가 G가 되는 경우를 출력하는 문제였다. 제곱수로 이루어진 배열 만들고, 투 포인터로 두 수 찾아서 출력하면 되는 간단한 문제였다.  풀이 + 코드G는 100,000보다 작거나 같은 수이기에 두 제곱수의 차가 100,000보다 큰 최대한 작은 제곱수를 구해보면 대략 51,000 이 나온다. (51,000^2 - 50,999^2 = 101,999) 제곱수로 이루어진 배열 (1^2 ~ 51000^2) 만들고 투 포인터 이용해서 제곱수의 차 구하면 된다.  int형의 크기는 4 byte / -2,147,483,648 ~ 2,147,483,647 인데, 51000^2는 2,601,000,000로 int 범위를 넘어섰다. .. 2024. 7. 3.
[백준/C++] #1644 소수의 연속합 (Two Pointer) 문제https://www.acmicpc.net/problem/1644 구상"연속된" 소수의 합으로 나타낼 수 있는 경우를 구하라길래 바로 two pointer를 사용한 prefix sum 형태의 배열이 떠올랐다. 그러면 소수로 이루어진 배열이 필요한데, 어떻게 소수를 판별해서 소수로만 이루어진 배열을 만들까? 라는 생각이 들었다. 실제로 해당 부분을  오랜 시간 고민했고, 가장 구현이 빡셌다. 소수 판별은 N까지만 되면 되었고, 4부터 판별 시작하면 되었다. 4부터 해당 수에 대한 배수들을 구해서 false로 판별하면 되겠다는 생각이 들었다. 배수는 2의 배수부터 sqrt(N)의 배수까지 확인하면 되었고, 배수라는게 겹치는 건 생각안해도 되기에 제곱수부터 고려하면 되었다.  표로 설명하는게 이해하기 쉬워.. 2024. 7. 3.

티스토리툴바